We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field. Our system does not suffer from these limitations.The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values in this setting. We then adapt the approach from Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using 25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is range proof. To prove that each plaintext in 200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.

Outsourcing the decryption of attribute-based encryption (ABE) ciphertext is a promising way to tackle the question of how users can perform decryption efficiently. However, existing solutions require the type of the target ciphertext to be determined at the setup of the outsourcing scheme. As such, making the target cryptosystems (or the clients) to be versatile becomes an issue that warrants investigations. In this paper, the problem we wish to tackle is to transform an ABE ciphertext to any client who is using the same, or possibly different, public-key encryption (PKE) system with the sender. The problem is of practical interest since it is hard to require all clients to use the same PKE, especially in the case of remote and cross-system data sharing. In addition, we also consider whether robust client-side decryption scheme can be adopted. This feature is not supported in the existing ABE with outsourcing.

Abstract Continual memory attacks, inspired by recent realistic physical attacks, have broken many cryptographic schemes that were considered secure in traditional cryptography model. In this paper, we consider the continual memory leakage resilience in public‐key encryption with keyword search scheme (PEKS). We give the definition of continual memory leakage resilience security for PEKS, which allows continual secret key leakage in the trapdoor generation algorithm rather than leakage of trapdoor itself. We believe that the definition is more suitable for practical PEKS scenario. To construct a concrete PEKS scheme secure against continual memory attacks, we firstly obtain a continual master‐key leakage‐resilient anonymous identity‐based encryption (IBE) scheme by applying the generic tool provided by Lewko et al. to a fully secure anonymous IBE scheme that comes from the fully secure anonymous hierarchical identity‐based encryption (HIBE) scheme of De Caro and colleagues. Then, we transform our continual master‐key leakage‐resilient anonymous IBE scheme to a PEKS scheme using the generic Anonymous IBE‐to‐PEKS transformation and prove its continual leakage‐resilient security. Copyright © 2016 John Wiley & Sons, Ltd.

To tackle with physical attacks to real world cryptosystems, leakage resilient cryptography was developed. In this setting, the adversary is allowed to have access to the internal state of a cryptographic system, thus violates the black-box reduction used in cryptography. Especially when considering continual memory leakage (CML), i.e., there is no predetermined bound on the leakage of the internal information, the task is extremely tough. In this paper, we solve this problem by introducing a new primitive called updatable hash proof system (UHPS). A UHPS can be viewed as a special Hash proof system (HPS), which served as a fundamental tool in constructing public key encryption (PKE) schemes in both leakage-free and leaky settings. A remarkable property of UHPS is that by simply substituting the HPS component with a UHPS component in a PKE scheme, one obtains a new PKE scheme secure in the CML setting. Moreover, the resulting PKE scheme enjoys the same advantage of the original HPS-based PKE, for instance, still “compatible” with known transforms [ 8 , 20 , 24 , 32 ]. We then give instantiations of UHPS from widely-accepted assumptions, including the symmetric external Diffie-Hellman assumption and the d-linear assumption. Interestingly, we notice that when instantiated with concrete assumptions, the resulting chosen-ciphertext secure PKE scheme is by far the most efficient.