Structured data is well handled by gradient-boosted decision trees (GBDT), which are usually trained on vertically partitioned features across mutually distrustful parties. High speed and interpretability make GBDTs popular in finance and healthcare, where neural networks may fall short. Enabling secure computation for GBDTs poses unique challenges, requiring secure record alignment for comparison. Relying on private set intersection (PSI) is a de facto approach. Mistaking PSI for a safety measure actually exposes which record identifiers (IDs) are shared between the datasets. Although circuit-PSI could help, it is costly for generic uses. New ideas are needed to efficiently train in a "dark forest". Aiming to hide the IDs, we initiate the study of anonymous GBDT training on split data held by two parties. Dual circuit-PSI in our design lets the parties alternate as receiver to run pick-then-sum over local features. Via oblivious programmable pseudorandom functions, we propagate circuit-PSI outputs as shared state across runs. Avoiding universal alignment, we resolve the neglected dilemma that ID hiding incurs a cost that scales with domain size. Next, we halve the cost of ciphertext packing used to convert single-instruction multiple-data homomorphic encryption from (ring) learning with errors in prior secure GBDT (Usenix Security' 23) and related secure machine-learning computations. Comparative experiments show our protocol remains competitive with leaky approaches in efficiency. Enabling ID-hiding aggregation, our techniques can extend to other vertically partitioned analytics.

Zero-knowledge range proof (ZKRP) asserts that a committed integerVlies in a given range like$[{0, 2^{n}-1}]$without other leakages ofV. It is vital in various privacy-preserving systems. Moving forward, the quest for post-quantum security is still in its infancy; the proof size of state-of-the-art lattice-based ZKRP (Lyubashevsky et al., CCS 20 and Couteau et al., Eurocrypt 21) remains linear inn, directly impacting the long-term sustainability in applications such as immutable ledgers. Confronting this unresolved impasse, we propose SHARP-PQ,i.e., succinct hash-based arbitrary-range proof with post-quantum security. SHARP-PQ offers proof size poly-logarithmic ton, optimized batch proofs, and versatile (new) capabilities. Its success stems from the improved inner product argument and exploitation of homomorphism. Empirically, SHARP-PQ features at least$10\times $smaller proof size for multiple ranges over lattice-based ZKRPs while maintaining competitive prover and verifier times. SHARP-PQ also outperforms ZKRPs directly constructed from hash-based generic zero-knowledge proofs at most$10 \times $.

Secure aggregation protocols ensure the privacy of users’ data in federated learning by preventing the disclosure of local gradients. Many existing protocols impose significant communication and computational burdens on participants and may not efficiently handle the large update vectors typical of machine learning models. Correspondingly, we present e-SeaFL, an efficient verifiable secure aggregation protocol taking only one communication round during the aggregation phase. e-SeaFL allows the aggregation server to generate proof of honest aggregation to participants via authenticated homomorphic vector commitments. Our core idea is the use of assisting nodes to help the aggregation server, under similar trust assumptions existing works place upon the participating users. Our experiments show that the user enjoys an order of magnitude efficiency improvement over the state-of-the-art (IEEE S&P 2023) for large gradient vectors with thousands of parameters. Our open-source implementation is available at https://github.com/vt-asaplab/e-SeaFL.

Batched sparse (BATS) code is a network coding solution for multi-hop wireless networks with packet loss. Achieving a close-to-optimal rate relies on an optimal degree distribution. Technical challenges arise from the sensitivity of this distribution to the often empirically obtained rank distribution at the destination node. Specifically, if the empirical distribution overestimates the channel, BATS codes experience a significant rate degradation, leading to unstable rates across different runs and hence unpredictable transmission costs. Confronting this unresolved obstacle, we introduce a formulation for distributionally robust optimization in degree optimization. Deploying the resulting degree distribution resolves the instability of empirical rank distributions, ensuring a close-to-optimal rate, and unleashing the potential of applying BATS codes in real-world scenarios.

Softmax and sigmoid, composing exponential functions (ex) and division (1/x), are activation functions often required in training. Secure computation on non-linear, unbounded 1/x and ex is already challenging, let alone their composition. Prior works aim to compute softmax by its exact formula via iteration (CrypTen, NeurIPS ’21) or with ASM approximation (Falcon, PoPETS ’21). They fall short in efficiency and/or accuracy. For sigmoid, existing solutions such as ABY2.0 (Usenix Security ’21) compute it via piecewise functions, incurring logarithmic communication rounds.

Differentially private stochastic gradient descent (DP-SGD) adds noise to gradients in back-propagation, safeguarding training data from privacy leakage, particularly membership inference. It fails to cover (inference-time) threats like embedding inversion and sensitive attribute inference. It is also costly in storage and computation when used to fine-tune large pre-trained language models (LMs).

Anonymous systems (e.g. anonymous cryptocurrencies and updatable anonymous credentials) often follow a construction template where an account can only perform a single anonymous action, which in turn potentially spawns new (and still single-use) accounts (e.g. UTXO with a balance to spend or session with a score to claim). Due to the anonymous nature of the action, no party can be sure which account has taken part in an action and, therefore, must maintain an ever-growing list of potentially unused accounts to ensure that the system keeps running correctly. Consequently, anonymous systems constructed based on this common template are seemingly not sustainable. In this work, we study the sustainability of ring-based anonymous systems, where a user performing an anonymous action is hidden within a set of decoy users, traditionally called a “ring”. On the positive side, we propose a general technique for ring-based anonymous systems to achieve sustainability. Along the way, we define a general model of decentralised anonymous systems (DAS) for arbitrary anonymous actions, and provide a generic construction which provably achieves sustainability. As a special case, we obtain the first construction of anonymous cryptocurrencies achieving sustainability without compromising availability. We also demonstrate the generality of our model by constructing sustainable decentralised anonymous social networks. On the negative side, we show empirically that Monero, one of the most popular anonymous cryptocurrencies, is unlikely to be sustainable without altering its current ring sampling strategy. The main subroutine is a sub-quadratic-time algorithm for detecting used accounts in a ring-based anonymous system.

Anonymous credentials encourage online communication without fear of surveillance, but may invite misbehavior like hate speech. Previous updatable anonymous credentials keep a chronological queue of authenticated sessions and a global pointer to the last chunk of judged sessions. This design allows efficient authentication for proving over only a subset of sessions. However, complications in subjective evaluation often introduce hard-to-judge sessions, which halt all users since sessions that come after the global pointer cannot be redeemed, eventually exceeding the queue size that limits the creation of bad sessions. Such a global-halting loophole may also make judgments overly harsh and hasty.We propose SMART (slack management of anonymous reputation traits), maintaining multiple queues so the server could issue interim judgments many times before finalization. Such slackness removes the binary judgment of old methods and mitigates the global-halting issue. Prior schemes only allow score upgrades (WPES ’14) or require proving against a global session list since the last checkpoint (S&P ’22). Our authentication time is linear in the number of queues or sessions in a designated queue for immediate revocation.

Sustainable cryptocurrency systems need to address the challenge of continuous inflation. Systematically maintaining stability during market turbulence can be challenging when token minting rates are predetermined and do not account for actual liquidity demand. Mindful of the critical role played by monetary policy, we propose a decentralized, truthful auction approach for tuning the currency system toward self-stabilization in volatile markets. Concretely, when severe inflation or market overheating occurs, the system enforces a contractionary monetary policy to restrain the market liquidity and avoid potential economic disasters. Should severe deflation and market stagnancy occur, more tokens will be minted than burnt to stimulate the market. Through this approach, our studies aim to provide a tool to help sustain the long-term existence of decentralized commodities.

Access control encryption (ACE) enforces, through a sanitizer as the mediator, that only legitimate sender-receiver pairs can communicate, without the sanitizer knowing the communication metadata, including its sender and recipient identity, the policy over them, and the underlying plaintext. Any illegitimate transmission is indistinguishable from pure noise. Existing works focused on computational security and require trapdoor functions and possibly other heavyweight primitives. We present the first ACE scheme with information-theoretic security (unconditionally against unbounded adversaries). Our novel randomization techniques over matrices realize sanitization (traditionally via homomorphism over a fixed randomness space) such that the secret message in the hidden message subspace remains intact if and only if there is no illegitimate transmission.

Edwards-curve digital signature algorithm (EdDSA) is a highly efficient scheme with a short key size. It is derived from the threshold-friendly Schnorr signatures and is covered by the NIST standardization efforts of threshold cryptographic primitives. Nevertheless, extending its deterministic nonce generation to the threshold setting requires heavyweight cryptographic techniques, even when the hash function is replaced with one optimized for secure multi-party computation. Indeed, an efficient extension to the threshold setting is considered a major challenge by NIST and academia.

We studied 53 privacy-preserving neural-network papers in 2016-2022 based on cryptography (without trusted processors or differential privacy), 16 of which only use homomorphic encryption, 19 use secure computation for inference, and 18 use non-colluding servers (among which 12 support training), solving a wide variety of research problems. We dissect their cryptographic techniques and "love-hate relationships" with machine learning alongside a genealogy highlighting noteworthy developments. We also re-evaluate the state of the art under WAN. We hope this can serve as a go-to guide connecting different experts in related fields.

Differentially private (DP) learning, notably DP stochastic gradient descent (DP-SGD), has limited applicability in fine-tuning gigantic pre-trained language models (LMs) for natural language processing tasks. The culprit is the perturbation of gradients (as gigantic as entire models), leading to significant efficiency and accuracy drops.

Graphs nicely capture data from various domains, allowing the computations of many analytic tasks via graph queries. Graphs of real-world data are often large, albeit useful, and the involved computation can be too heavyweight for commodity computers. For secure outsourcing, we propose (SGX)$^{2}$, a forward-secure structured encryption scheme for graph data, which uses lightweight cryptographic techniques with a trusted execution environment such as SGX. To process million-scale graphs by the limited memory of SGX, we load data on-demand using Dijkstra's algorithm and Fibonacci heap. Compared with most prior graph encryption schemes, (SGX)$^{2}$supports exact shortest-distance queries instead of approximation and can be easily extended to other graph-based analytics.

Private set intersection (PSI) is a secure two-party computation ($2$PC) protocol that reveals only the intersection of two private sets. Driven by different applications, various works devise specific protocols for private computation on the intersection (PCI), e.g., summation of the values labeled with each element in the intersection. Upgrading a PSI protocol to PCI for generic computations while maintaining efficiency and preventing leakage is known to be not straightforward (e.g., the intersection set size could be leaked).

Abstract Dynamic searchable symmetric encryption (DSSE) allows a client to query or update an outsourced encrypted database. Range queries are commonly needed. Previous range-searchable schemes either do not support updates natively (SIGMOD’16) or use file indexes of many long bit-vectors for distinct keywords, which only support toggling updates via homomorphically flipping the presence bit. (ESORICS’18). We propose a generic upgrade of any (inverted-index) DSSE to support range queries (a.k.a. range DSSE), without homomorphic encryption, and a specific instantiation with a new trade-off reducing client-side storage. Our schemes achieve forward security, an important property that mitigates file injection attacks. Moreover, we identify a variant of injection attacks against the first somewhat dynamic scheme (ESORICS’18). We also extend the definition of backward security to range DSSE and show that our schemes are compatible with a generic upgrade of backward security (CCS’17). We comprehensively analyze the computation and communication overheads, including implementation details of client-side index-related operations omitted by prior schemes. We show high empirical efficiency for million-scale databases over a million-scale keyword space.

Convolutional neural networks (CNN) is a popular architecture in machine learning for its predictive power, notably in computer vision and medical image analysis. Its great predictive power requires extensive computation, which encourages model owners to host the prediction service in a cloud platform. This article proposes a CNN prediction scheme that preserves privacy in the outsourced setting, i.e., the model-hosting server cannot learn the query, (intermediate) results, and the model. Similar to SecureML (S&P’17), a representative work that provides model privacy, we employ two non-colluding servers with secret sharing and triplet generation to minimize the usage of heavyweight cryptography. We made the following optimizations for both overall latency and accuracy. 1) We adopt asynchronous computation and SIMD for offline triplet generation and parallelizable online computation. 2) As MiniONN (CCS’17) and its improvement by the generic EzPC compiler (EuroS&P’19), we use a garbled circuit for the non-polynomial ReLU activation to keep the same accuracy as the underlying network (instead of approximating it in SecureML prediction). 3) For the pooling in CNN, we employ (linear) average-pooling, which achieves almost the same accuracy as the (non-linear, and hence less efficient) max-pooling exhibited by MiniONN and EzPC. Considering both offline and online costs, our experiments on the MNIST dataset show a latency reduction of$122\times$,$14.63\times$, and$36.69\times$compared to SecureML, MiniONN, and EzPC; and a reduction of communication costs by$1.09\times$,$36.69\times$, and$31.32\times$, respectively. On the CIFAR dataset, our scheme achieves a lower latency by$7.14\times$and$3.48\times$and lower communication costs by$13.88\times$and$77.46\times$when compared with MiniONN and EzPC, respectively.

Deep learning unlocks applications with societal impacts, e.g., detecting child exploitation imagery and genomic analysis of rare diseases. Deployment, however, needs compliance with stringent privacy regulations. Training algorithms that preserve the privacy of training data are in pressing need. Purely cryptographic approaches can protect privacy, but they are still costly, even when they rely on two or more non-colluding servers. Seemingly-"trivial" operations in plaintext quickly become prohibitively inefficient when a series of them are "crypto-processed," e.g., (dynamic) quantization for ensuring the intermediate values would not overflow. Slalom, recently proposed by Tramer and Boneh, is the first solution that leverages both GPU (for efficient batch computation) and a trusted execution environment (TEE) (for minimizing the use of cryptography). Roughly, it works by a lot of pre-computation over known and fixed weights, and hence it only supports private inference. Five related problems for private training are left unaddressed. Goten, our privacy-preserving training and prediction framework, tackles all five problems simultaneously via our careful design over the "mismatched" cryptographic and GPU data types (due to the tension between precision and efficiency) and our round-optimal GPU-outsourcing protocol (hence minimizing the communication cost between servers). It 1) stochastically trains a low-bitwidth yet accurate model, 2) supports dynamic quantization (a challenge left by Slalom), 3) minimizes the memory-swapping overhead of the memory-limited TEE and its communication with GPU, 4) crypto-protects the (dynamic) model weight from untrusted GPU, and 5) outperforms a pure-TEE system, even without pre-computation (needed by Slalom). As a baseline, we build CaffeScone that secures Caffe using TEE but not GPU; Goten shows a 6.84x speed-up of the whole VGG-11. Goten also outperforms Falcon proposed by Wagh et al., the latest secure multi-server cryptographic solution, by 132.64x using VGG-11. Lastly, we demonstrate Goten's efficacy in training models for breast cancer diagnosis over sensitive images.

Cyber-physical systems revolutionize how we interact with physical systems. Smart grid is a prominent example. With new features such as fine-grained billing, user privacy is at a greater risk than before. For instance, a utility company () can infer users’ (fine-grained) usage patterns from their payment. The literature only focuses on hiding individual meter readings in bill calculation. It is unclear how to preserve amount privacy when the needs to assert that each user has settled the amount as calculated in the bill.

LDSP is a layer-2 cryptocurrency payment system that supports a dynamic and distributed setup with scalability and payer privacy. Different from the statekeeping merchant consortium assumed by a recent layer-2 solution Snappy (NDSS 2020), its core idea is to rely on leaders selected from the merchants to lead a mini-consortium and ensure the fungibility of the LDSP coins. Similar to Snappy, payers can transfer coins off-chain, enjoying low-latency transactions, while the merchants are assured that they will receive the coins. Privacy-wise, Snappy requires all merchants to check the whole customer transaction history, which is not necessary for LDSP.

Access control is a fundamental keystone in security. Damgard, Haagh, and Orlandi (TCC 2016) introduced access˚ control encryption (ACE) that enforces no-read and no-write rules without revealing the senders, receivers, or the content of the encrypted traffic. Existing designs of ACE for arbitrary policy (covering all possibilities of read/write relationship) rely on indistinguishability obfuscation or lattice-based assumptions, with either exponential-size ciphertexts or circuit realization of policy. Also, their designs mandate a private sanitizer key to remain perpetually online for sanitization. The only existing scheme that can afford a public sanitizer key supports only simple policies. To summarize, state-of-the-art ACE schemes only feature at most two of the following desirable properties: arbitrarypolicy, constant-size (ciphertext), and efficient (sanitization). This paper introduces an ACE scheme for arbitrary policy without sanitizer key, which solves the open question posed by Kim and Wu (Asiacrypt 2017). We also put forth the notion of cross-domain ACE, separating the key generator into the sender-authority and receiver-authority. Our scheme requires structure-preserving signatures, non-interactive zero-knowledge proof, and sanitizable identity-based broadcast encryption as the building blocks. It can be instantiated directly from pairing-based assumptions and features constant ciphertext size. We also prototyped our scheme and demonstrated its practical efficiency.

Decision tree and its generalization of random forests are a simple yet powerful machine learning model for many classification and regression problems. Recent works propose how to privately evaluate a decision tree in a two-party setting where the feature vector of the client or the decision tree model (such as the threshold values of its nodes) is kept secret from another party. However, these works cannot be extended trivially to support the outsourcing setting where a third-party who should not have access to the model or the query. Furthermore, their use of aninteractivecomparison protocol does not support branching program, hence requires interactions with the client to determine the comparison result before resuming the evaluation task. In this paper, we propose the first secure protocol for collaborative evaluation of random forests contributed by multiple owners. They outsource evaluation tasks to a third-party evaluator. Upon receiving the client's encrypted inputs, the cloud evaluates obliviously on individually encrypted random forest models and calculates the aggregated result. The system is based on our new secure comparison protocol, secure counting protocol, and a multi-key somewhat homomorphic encryption on top of symmetric-key encryption. This allows us to reduce communication overheads while achieving round complexity lower than existing work.

Deduplication is widely used for reducing the storage requirement for storage service providers. Nevertheless, it is unclear how to support deduplication of encrypted data securely until the study of Bellare et al. on message-locked encryption (MLE, Eurocrypt 2013). While updating (shared) files is natural, existing MLE solutions do not allow efficient update of encrypted files stored remotely. Even modifying a single bit requires the expensive way of downloading and decrypting a large ciphertext (then re-uploading). This paper initiates the study of updatable block-level MLE, a new primitive in incremental cryptography and cloud cryptography. Our proposed provably-secure construction is updatable with computation cost logarithmic in the file size. It naturally supports block-level deduplication. It also supports proof-of-ownership which protects storage providers from being abused as a free content distribution network. Our experiments show its practical performance relative to the original MLE and existing non-updatable block-level MLE.

Privacy-preserving deep neural network (DNN) inference remains an intriguing problem even after the rapid developments of different communities. One challenge is that cryptographic techniques such as homomorphic encryption (HE) do not natively support non-linear computations (e.g., sigmoid). A recent work, BAYHENN (Xie et al., IJCAI'19), considers HE over the Bayesian neural network (BNN). The novelty lies in "meta-prediction" over a few noisy DNNs. The claim was that the clients can get intermediate outputs (to apply non-linear function) but are still prevented from learning the exact model parameters, which was justified via the widely-used learning-with-error (LWE) assumption (with Gaussian noises as the error). This paper refutes the security claim of BAYHENN via both theoretical and empirical analyses. We formally define a security game with different oracle queries capturing two realistic threat models. Our attack assuming a semi-honest adversary reveals all the parameters of single-layer BAYHENN, which generalizes to recovering the whole model that is "as good as" the BNN approximation of the original DNN, either under the malicious adversary model or with an increased number of oracle queries. This shows the need for rigorous security analysis ("the noise introduced by BNN can obfuscate the model" fails -- it is beyond what LWE guarantees) and calls for the collaboration between cryptographers and machine-learning experts to devise practical yet provably-secure solutions.

Anonymous communication is desirable for personal, financial, and political reasons. Despite the abundance of frameworks and constructions, anonymity definitions are usually either not well defined or too complicated to use. In between are ad-hoc definitions for specific protocols which sometimes only provide weakened anonymity guarantees. This paper addresses this situation from the perspectives of syntax, security definition, and construction. We propose simple yet expressive syntax and security definition for anonymous communication. Our syntax covers protocols with different operational characteristics. We give a hierarchy of anonymity definitions, starting from the strongest possible to several relaxations. We also propose a modular construction from any key-private public-key encryption scheme, and a new primitive-oblivious forwarding protocols, of which we give two constructions. The first is a generic construction from any random walk over graphs, while the second is optimized for the probability of successful delivery, with experimental validation for our optimization. Anonymity is guaranteed even when the adversary can observe and control all traffic in the network and corrupt most nodes, in contrast to some efficient yet not-so-anonymous protocols. We hope this work suggests an easier way to design and analyze efficient anonymous communication protocols in the future.

\n Contains fulltext :\n 204495.pdf (Publisher’s version ) (Open Access)\n

Image retrieval is crucial for social media sites such as Instagram to identify similar images and make recommendations for users who share similar interests. To get rid of the storage burden and computation for image retrieval, outsourcing to a remote cloud is now a trend. Yet, privacy concerns mandate the use of encryption before outsourcing the images. We need a secure way for retrieving images from a not-fully-trusted server. This paper proposes InstantCryptoGram, a secure image retrieval service. We first design a new data structure called sub-simhash, which fits for the inverted index used by many searchable symmetric encryption schemes. It leads to our modular solution that supports efficient similarity queries and updates over encrypted images. Our experiments on Amazon AWS EC2 over representative datasets show that our scheme is efficient and accurate in finding similar images while preserving privacy.

Storage services allow data owners to store their huge amount of potentially sensitive data, such as audios, images, and videos, on remote cloud servers in encrypted form. To enable retrieval of encrypted files of interest, searchable symmetric encryption (SSE) schemes have been proposed. However, many schemes construct indexes based on keyword-file pairs and focus on boolean expressions of exact keyword matches. Moreover, most dynamic SSE schemes cannot achieve forward privacy and reveal unnecessary information when updating the encrypted databases. We tackle the challenge of supporting large-scale similarity search over encrypted feature-rich multimedia data, by considering the search criteria as a high-dimensional feature vector instead of a keyword. Our solutions are built on carefully-designed fuzzy Bloom filters which utilize locality sensitive hashing (LSH) to encode an index associating the file identifiers and feature vectors. Our schemes are proven to be secure against adaptively chosen query attack and forward private in the standard model. We have evaluated the performance of our scheme on real-world high-dimensional datasets, and achieved a search quality of 99 percent recall with only a few number of hash tables for LSH. This shows that our index is compact and searching is not only efficient but also accurate.

Biometric identification typically scans a large-scale database of biometric records for finding a close enough match of an individual. This paper investigates how to outsource this computationally expensive scanning while protecting the privacy of both the database and the computation. Exploiting the inherent structures of biometric data and the properties of identification operations, we first present a privacy-preserving biometric identification scheme which uses a single server. We then consider its extensions in the two-server model. It achieves a higher level of privacy than our single-server solution assuming two servers are not colluding. Apart from somewhat homomorphic encryption, our second scheme uses batched protocols for secure shuffling and minimum selection. Our experiments on both synthetic and real data sets show that our solutions outperform existing schemes while preserving privacy.

Deduplication is a widely used technique for reducing storage space of cloud service providers. Yet, it is unclear how to support deduplication of encrypted data securely until the study of Bellareetal on message-locked encryption (Eurocrypt 2013). Since then, there are many improvements such as strengthening its security, reducing client storage, etc. While updating a (shared) file is common, there is little attention on how to efficiently update large encrypted files in a remote storage with deduplication. To modify even a single bit, existing solutions require the trivial and expensive way of downloading and decrypting the large ciphertext.

Geosocial applications collect (and record) users' precise location data to perform proximity computations, such as notifying a user or triggering a service when a friend is within geographic proximity. With the growing popularity of mobile devices that have sophisticated localization capability it becomes more convenient and tempting to share location data. But the precise location data in plaintext not only exposes user's whereabouts but also mobility patterns that are sensitive and cannot be changed easily. This paper proposes cryptographic protocols on top of spatial cloaking to reduce the resolution of location and balance between data utility and privacy. Specifically we interest in the setting that allows users to send periodic updates of precise coordinates and define privacy preferences to control the granularity of the location, both in an encrypted format. Our system supports three kinds of user queries --- "Where is this user?", "Who is nearby?", and "How close is this user from another user?". Also, we develop a new algorithm to improve the multidimensional data access by reducing significant masking error. Our prototype and various performance evaluations on different platforms demonstrated that our system is practical.

Abstract Sharing information to others is common nowadays, but the question is with whom to share. To address this problem, we propose the notion of secret transfer with access structure (STAS). STAS is a twoparty computation protocol that enables the server to transfer a secret to a client who satisfies the prescribed access structure. In this paper, we focus on threshold secret transfer (TST), which is STAS for threshold policy and can be made more expressive by using linear secret sharing. TST enables a number of applications including a simple construction of oblivious transfer (OT) with threshold access control, and (a variant of) threshold private set intersection (t-PSI), which are the first of their kinds in the literature to the best of our knowledge. The underlying primitive of STAS is a variant of OT, which we call OT for a sparse array. We provide two constructions which are inspired by state-of-the-art PSI techniques including oblivious polynomial evaluation (OPE) and garbled Bloom filter (GBF). The OPEbased construction is secure in the malicious model, while the GBF-based one is more efficient. We implemented the latter one and showed its performance in applications such as privacy-preserving matchmaking.

We propose the notion of password-controlled encryption, a two-factor scheme involving a user-chosen password and the master public/secret key pair. The data owner obtains a secret key generated from a password and the master secret key of a key generation center (KGC) after authentication, and shares this password with encryptors and an emergency contact. In normal circumstances, the data owners can enforce access control by themselves. In emergency when the data owner is unavailable, any one with the same password can request for the decryption key from a KGC, without letting the KGC to know the password. At the same time, the KGC is held accountable if the key generation process is abused. Password-controlled encryption is especially applicable for protecting electronic medical record, which provides confidentiality with break-glass access, without relying on a key-escrow server or trusted hardware.

Multi-pattern matching compares a large set of patterns against a given query string, which has wide application in various domains such as bio-informatics and intrusion detection. This paper shows how to authenticate the classic Aho-Corasick multi-pattern matching automation, without requiring the verifier to store the whole pattern set, nor downloading a proof for every single matching step. The storage complexity for the authentication metadata at the server side is the same as that of the unauthenticated version. The communication overhead is minimal since the proof size is linear in the query length and does not grow with the sizes of query result nor the pattern set. Our evaluation has shown that the query and verification times are practical.

Since many cryptographic schemes are about performing computation on data, it is important to consider a computation model which captures the prominent features of modern system architecture. Parallel random access machine (PRAM) is such an abstraction which not only models multiprocessor platforms, but also new frameworks supporting massive parallel computation such as MapReduce.

Attribute-based encryption (ABE) is a cryptographic tool for fine-grained data access control. For practical needs, an ABE scheme should support multiple authority and revocation. Furthermore, decryption should also be outsourced for higher efficiency. Researchers have been extending existing ABE schemes for these goals. Yet, the rationales are often hidden behind tailor-made number-theoretic constructions.

In this paper, we point out some faulty instantiations of threshold ring signatures (TRS) based on the threshold proof-of-knowledge (TPoK) protocol. Although a TRS can be regarded as the non-interactive version of the TPoK, the computational domains of the variables should be carefully chosen. We show that by choosing some inappropriate domains, two such instantiations suffer from forgery and anonymity attacks. Our attacks rely on algebraic techniques which involve solving some particular instances of the well-known subset sum problem. While we focus our attacks on two particular instantiations of the TRS, they are generic and are applicable to other schemes with the same choice of domains or a similar structure. We believe this paper can act as an important security remark on the design of future TRS schemes.

This paper reveals an intrinsic relationship between secure cloud storage and secure network coding for the first time. Secure cloud storage was proposed only recently while secure network coding has been studied for more than ten years. Although the two areas are quite different in their nature and are studied independently, we show how to construct a secure cloud storage protocol given any secure network coding protocol. This gives rise to a systematic way to construct secure cloud storage protocols. Our construction is secure under a definition which captures the real world usage of the cloud storage. Furthermore, we propose two specific secure cloud storage protocols based on two recent secure network coding protocols. In particular, we obtain the first publicly verifiable secure cloud storage protocol in the standard model. We also enhance the proposed generic construction to support user anonymity and third-party public auditing, which both have received considerable attention recently. Finally, we prototype the newly proposed protocol and evaluate its performance. Experimental results validate the effectiveness of the protocol.

We initiate the study of related randomness attack in the face of a number of practical attacks in public key cryptography, ranges from active attacks like fault-injection, to passive attacks like software (mis)implementation on choosing random numbers. Our new definitions cover the well-known related-key attacks (RKA) where secret keys are related, and a number of new attacks, namely, related encryption randomness attacks, related signing randomness attacks, and related public key attacks. We provide generic constructions for security against these attacks, which are efficiently built upon normal encryption and signature schemes, leveraging RKA-secure pseudorandom function and generator.

Searchable Symmetric Encryption (SSE) encrypts data in such a way that they can be searched efficiently. Some recent SSE schemes allow modification of data, yet they may incur storage overhead to support parallelism in searching, or additional computation to minimize the potential leakage incurred by the update, both penalize the performance. Moreover, most of them consider only keyword search and not applicable to arbitrary structured data. In this work, we propose the first parallel and dynamic symmetric-key structured encryption, which supports query of encrypted data structure. Our scheme leverages the rather simple randomized binary search tree to achieve non-interactive queries and updates.

Certificateless encryption (CLE) can be used to prevent the key generation centre from decrypting ciphertexts (which addresses the key escrow problem of identity-based encryption), but it cannot provide user revocation mechanism by default. A revocable CLE scheme was proposed by Shen et al. (2014. Efficient revocable certificateless encryption secure in the standard model. Comput. J., 57, 592–601) which realizes the revocation by requiring a time key in the decryption process. Despite of their security proofs, this paper shows an attack of their revocation mechanism.

We propose an anonymous authentication protocol that supports time-bound credentials for an efficient revocation. It is especially suitable for large-scale network in roaming scenario. With our newly designed group signature scheme as a building block, a timestamp can be embedded to user secret key. No expired key can be used to authenticate, and hence naturally revoked users (e.g., due to contract expiration) are not required to be put into the revocation list. This makes our protocol much faster than previous roaming protocols in terms of revocation checking, which is a main part in verification.

Most existing proposals for access control over outsourced data mainly aim at guaranteeing that the data are only accessible to authorized requestors who have the access credentials. This paper proposes TRLAC, an a posteriori approach for tracing and revoking leaked credentials, to complement existing a priori solutions. The tracing procedure of TRLAC can trace, in a black-box manner, at least one traitor who illegally distributed a credential, without any help from the cloud service provider. Once the dishonest users have been found, a revocation mechanism can be called to deprive them of access rights. We formally prove the security of TRLAC, and empirically shows that the introduction of the tracing feature incurs little costs to outsourcing.

This paper investigates the intrinsic relationship between secure cloud storage and secure network coding for the first time. Secure cloud storage was proposed only recently while secure network coding has been studied for more than ten years. We show in general how to construct a secure cloud storage protocol given any secure network coding protocol. Our construction suggests a systematic way to construct various secure cloud storage protocols. We also show that it is secure under a definition which captures the real world uses of the cloud storage. From our general construction, we propose a secure cloud storage protocol based on a recent secure network coding protocol. The protocol is the first publicly verifiable secure cloud storage protocol in the standard model, while the previous work is either not publicly verifiable, or security argument is only argued heuristically in the random oracle model. We also enhance the proposed protocol to support third-party public auditing, which has received considerable attention recently. Finally, we prototype the proposed protocol and evaluate its performance. Experimental results validate the effectiveness of the protocol.

Motivated by the privacy issues, curbing the adoption of electronic healthcare systems and the wild success of cloud service models, we propose to build privacy into mobile healthcare systems with the help of the private cloud. Our system offers salient features including efficient key management, privacy-preserving data storage, and retrieval, especially for retrieval at emergencies, and auditability for misusing health data. Specifically, we propose to integrate key management from pseudorandom number generator for unlinkability, a secure indexing method for privacy-preserving keyword search which hides both search and access patterns based on redundancy, and integrate the concept of attribute-based encryption with threshold signing for providing role-based access control with auditability to prevent potential misbehavior, in both normal and emergency cases.

Data sharing is an important functionality in cloud storage. In this paper, we show how to securely, efficiently, and flexibly share data with others in cloud storage. We describe new public-key cryptosystems that produce constant-size ciphertexts such that efficient delegation of decryption rights for any set of ciphertexts are possible. The novelty is that one can aggregate any set of secret keys and make them as compact as a single key, but encompassing the power of all the keys being aggregated. In other words, the secret key holder can release a constant-size aggregate key for flexible choices of ciphertext set in cloud storage, but the other encrypted files outside the set remain confidential. This compact aggregate key can be conveniently sent to others or be stored in a smart card with very limited secure storage. We provide formal security analysis of our schemes in the standard model. We also describe other application of our schemes. In particular, our schemes give the first public-key patient-controlled encryption for flexible hierarchy, which was yet to be known.

With the goal of ensuring availability of security services such as encryption and authentication, we initiate the study of leakage-resilient threshold cryptography, for achieving formal security guarantee under various key-exposure attacks. A distinctive property of threshold cryptosystems is that a threshold number of secret keys are used in the main cryptographic function such as decryption or signing. Even though some existing security models allow leakages of multiple keys of different users, these keys are not used simultaneously to decrypt a ciphertext or sign a message.

Nowadays, many organizations outsource data storage to the cloud such that a member (owner) of an organization can easily share data with other members (users). Due to the existence of security concerns in the cloud, both owners and users are suggested to verify the integrity of cloud data with Provable Data Possession (PDP) before further utilization on data. However, previous methods either unnecessarily reveal the identity of a data owner to the untrusted cloud or any public verifiers, or introduce significant overheads on verification metadata to preserve anonymity. In this paper, we propose a simple and efficient publicly verifiable approach to ensure cloud data integrity without sacrificing the anonymity of data owners nor requiring significant verification metadata. Specifically, we introduce a security-mediator (SEM), which is able to generate verification metadata (i.e., signatures) on outsourced data for data owners. Our approach decouples the anonymity protection mechanism from the PDP. Thus, an organization can employ its own anonymous authentication mechanism, and the cloud is oblivious to that since it only deals with typical PDP-metadata, Consequently, there is no extra storage overhead when compared with existing non-anonymous PDP solutions. The distinctive features of our scheme also include data privacy, such that the SEM does not learn anything about the data to be uploaded to the cloud at all, which is able to minimize the requirement of trust on the SEM. In addition, we can also extend our scheme to work with the multi-SEM model, which can avoid the potential single point of failure existing in the single-SEM scenario. Security analyses prove our scheme is secure, and experiment results demonstrate our scheme is efficient.

Using cloud storage, users can remotely store their data and enjoy the on-demand high-quality applications and services from a shared pool of configurable computing resources, without the burden of local data storage and maintenance. However, the fact that users no longer have physical possession of the outsourced data makes the data integrity protection in cloud computing a formidable task, especially for users with constrained computing resources. Moreover, users should be able to just use the cloud storage as if it is local, without worrying about the need to verify its integrity. Thus, enabling public auditability for cloud storage is of critical importance so that users can resort to a third-party auditor (TPA) to check the integrity of outsourced data and be worry free. To securely introduce an effective TPA, the auditing process should bring in no new vulnerabilities toward user data privacy, and introduce no additional online burden to user. In this paper, we propose a secure cloud storage system supporting privacy-preserving public auditing. We further extend our result to enable the TPA to perform audits for multiple users simultaneously and efficiently. Extensive security and performance analysis show the proposed schemes are provably secure and highly efficient. Our preliminary experiment conducted on Amazon EC2 instance further demonstrates the fast performance of the design.

Wireless handheld devices which support e-mail and web browsing are increasingly popular. The authenticity of the information received is important, especially for business uses. In server-aided verification (SAV), a substantial part of the verification computation can be offloaded to a powerful but possibly untrusted server. This allows resource-constrained devices to enjoy the security guarantees provided by cryptographic schemes, such as pairing-based signatures, which may be too heavyweight to verify otherwise.

An identity-based online/offline encryption (IBOOE) scheme splits the encryption process into two phases. The first phase performs most of the heavy computations, such as modular exponentiation or pairing over points on elliptic curve. The knowledge of the plaintext or the receiver's identity is not required until the second phase, where the ciphertext is produced by only light computations, such as integer addition/multiplication or hashing. This division of computations makes encryption affordable by devices with limited computation power since the preparation works can be executed "offline" or possibly by some powerful devices. The identity-based (ID-based) nature of the scheme also allows the preparation of ciphertext without certificate verification.

In an end-to-end encryption model for a wireless sensor network (WSN), the network control center preloads encryption and decryption keys to the sensor nodes and the subscribers respectively, such that a subscriber can use a mobile device in the deployment field to decrypt the sensed data encrypted by the more resource-constrained sensor nodes. This paper proposes SMS-SED, a provably secure yet practically efficient key assignment system featuring a discrete time-based access control, to better support a business model where the sensors deployer rents the WSN to customers who desires a higher flexibility beyond subscribing to strictly consecutive periods. In SMS-SED, a node or a mobile device stores a secret key of size independent of the total number of sensor nodes and time periods. We evaluated the feasibility of deploying 2000 nodes for 4096 time periods at 1024-bit of security as a case study, studied the trade off of increasing the storage requirement of a node to significantly reduce its computation time, and provided formal security argument in the random oracle model.

Attribute-based encryption (ABE) is a promising tool for implementing fine-grained cryptographic access control. Very recently, motivated by reducing the trust assumption on the authority, and enhancing the privacy of users, a multiple-authority key-policy ABE system, together with a semi-generic anonymous key-issuing protocol, have been proposed by Chase and Chow in CCS 2009. Since ABE allows encryption for multiple users with attributes satisfying the same policy, it may not be always possible to associate a decryption key to a particular individual. A misbehaving user could abuse the anonymity by leaking the key to someone else, without worrying of being traced. In this paper, we propose a multi-authority ciphertext-policy (AND gates with wildcard) ABE scheme with accountability, which allows tracing the identity of a misbehaving user who leaked the decryption key to others, and thus reduces the trust assumptions not only on the authorities but also the users. The tracing process is efficient and its computational overhead is only proportional to the length of the identity.

Most existing large-scale networked systems on the Internet such as peer-to-peer systems are vulnerable to Sybil attacks where a single adversary can introduce many bogus identities. One promising defense of Sybil attacks is to perform social-network based admission control to bound the number of Sybil identities admitted. SybilLimit, the best known Sybil admission control mechanism, can restrict the number of Sybil identities admitted per attack edge to O(log n) with high probability assuming O(n/ log n) attack edges. In this paper, we propose Gatekeeper, a decentralized Sybil-resilient admission control protocol that significantly improves over SybilLimit. Gatekeeper is optimal for the case of O(1) attack edges and admits only O(1) Sybil identities (with high probability) in a random expander social networks (real-world social networks exhibit expander properties). In the face of O(k) attack edges (for any k ∈ O(n/ log n)), Gatekeeper admits O(log k) Sybils per attack edge. This result provides a graceful continuum across the spectrum of attack edges. We demonstrate the effectiveness of Gatekeeper experimentally on real-world social networks and synthetic topologies.

We design the first Leakage-Resilient Identity-Based Encryption (LR-IBE) systems from static assumptions in the standard model. We derive these schemes by applying a hash proof technique from Alwen et.al. (Eurocrypt '10) to variants of the existing IBE schemes of Boneh-Boyen, Waters, and Lewko-Waters. As a result, we achieve leakage-resilience under the respective static assumptions of the original systems in the standard model, while also preserving the efficiency of the original schemes. Moreover, our results extend to the Bounded Retrieval Model (BRM), yielding the first regular and identity-based BRM encryption schemes from static assumptions in the standard model.

We present Gatekeeper, a decentralized protocol that performs Sybil-resilient node admission control based on a social network. Gatekeeper can admit most honest nodes while limiting the number of Sybils admitted per attack edge to O(log k), where k is the number of attack edges. Our result improves over SybilLimit [3] by a factor of log n in the face of O(1) attack edges. Even when the number of attack edges reaches O(n/ log n), Gatekeeper only admits O(log n) Sybils per attack edge, similar to that achieved by SybilLimit.

In Information Processing Letters (2006), Tan pointed out that the anonymous signcryption scheme proposed by Yang, Wong and Deng (YWD) in ISC 2005 provides neither confidentiality nor anonymity. However, no discussion has been made on how a secure scheme can be made and there is no secure scheme available to date. In this paper, we propose a modification of YWD scheme which resolves the security issues of the original scheme without sacrificing its high efficiency and simple design. Indeed, we show that our scheme achieves confidentiality, existential unforgeability and anonymity with more precise reduction bounds. We also give a variation of our scheme and extend it to a ring signcryption scheme by using the technique due to Boneh, Gentry, Lynn and Shacham.

Attribute based encryption (ABE) [13] determines decryption ability based on a user's attributes. In a multi-authority ABE scheme, multiple attribute-authorities monitor different sets of attributes and issue corresponding decryption keys to users, and encryptors can require that a user obtain keys for appropriate attributes from each authority before decrypting a message. Chase [5] gave a multi-authority ABE scheme using the concepts of a trusted central authority (CA) and global identifiers (GID). However, the CA in that construction has the power to decrypt every ciphertext, which seems somehow contradictory to the original goal of distributing control over many potentially untrusted authorities. Moreover, in that construction, the use of a consistent GID allowed the authorities to combine their information to build a full profile with all of a user's attributes, which unnecessarily compromises the privacy of the user. In this paper, we propose a solution which removes the trusted central authority, and protects the users' privacy by preventing the authorities from pooling their information on particular users, thus making ABE more usable in practice.

Certificateless encryption refers to public key encryption with implicit certification. Security-mediated certificateless (SMC) encryption takes one-step further, such that every decryption requires a security-mediator (SEM) to partially decrypt the ciphertext. One major benefit is that instant revocation can be done by simply instructing the SEM to reject any further decryption request. Similar to the conventional chosen-ciphertext attack, it is reasonable to assume that an adversary can obtain the partial decryption of many ciphertexts. The authors show that the schemes proposed by Yang-Wang-Wang in AINAW 2007, Lo-Hwang-Li in IET Information Security, 1(3) and Yang-Xiong-Su in Computer Applications, 28(11) are insecure against partial decryption attacks, and hence cannot be classified as SMC encryption according to the original Chow–Boyd–González Nieto's formulation in PKC 2006.

Since the formalization of ring signature by Rivest, Shamir and Tauman in 2001, there are lots of variations appeared in the literature. Almost all of the variations rely on the random oracle model for security proof. In this paper, we propose a ring signature scheme based on bilinear pairings, which is proven to be secure against adaptive chosen message attack without using the random oracle model. It is one of the first in the literature to achieve this security level.