Nesrine Kaaniche, Ethmane El Moustaine, Maryline Laurent
Recent technological advances have given rise to the popularity and success of cloud storage. However, the prospect of outsourcing an increasing amount of data to a third party and the abstract nature of the cloud foster the proliferation of security and privacy challenges, namely, the remote data possession checking. This paper addresses this critical security concern, when storing sensitive data in a cloud storage service, and the need for users to trust commercial cloud providers. It proposes a deterministic Proof of Data Possession (PDP) scheme based on Interactive Proof System(IPS) and an original usage of the GPS scheme. Our approach has several advantages. First, it supports public verifiability which releases data owners from the burden of a periodical verification. Second, it provides constant communication complexity, where the exchanged messages between the storage server and the client are composed of constant number of group elements. Third, our solution is efficient and provably secure, as it is resistant to the fraudulence of the prover and the leakage of verified data.
We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As op-posed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to fur-ther trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups.
One of important issues of information security in the interaction of users is the use of methods and tools, allowing one party to make sure of the authenticity of another party. The proof of knowledge protocols which have the additional property of zero-knowledge are applied to solve this problem. The protocols based on asymmetric encryption have received wide acceptance, such as the Fiat-Shamir, Schnorr, Okamoto, Guillou-Quisquater, Brickell-McCurley, Feige-Fiat-Shamir protocols. Cryptographic strength of these protocols is defined by discrete logarithms in a finite prime field, as well as an increase in the number of accreditation cycles. As a result of the development of methods and tools of cryptanalysis and rapid development of technologies and power of computing systems, there is a need to increase the sizes of system-wide parameters of the protocol, leading to increased resource intensity and performance complexity of basic operations in the fields.Cryptographic zero-knowledge protocols on elliptic curves are proposed in the paper. The strength of cryptosystems on elliptic curves is based on the difficulty of solving the discrete logarithm problem in the group of elliptic curve points, and is more difficult than the discrete logarithm problem in the finite field. The completeness and soundness of protocols were determined, computation examples were given. The tools of the Strength Protocol Animator package were applied to verify the protocols for resistance to enemy attacks. Consequently, the use of cryptographic protocols on elliptic curves will significantly reduce the sizes of protocol parameters and increase the cryptographic strength
In this paper, through introducing the Williams public-key cryptosystem in detail, the analysis of the characteristics of the system, and the combination with zero knowledge proof, we set up a zero-knowledge proof scheme based on Williams public-key cryptosystem. The scheme will enrich the theory of cryptography, and particularly zero-knowledge proof theory.
In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all N P. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zeroknowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO 1989). Although it is widely believed that there exist constant-round zero-knowledge proofs of knowledge for all N P, to the best of our knowledge, no proof of this fact has been published. 1
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to\nconventional public key cryptography, such as RSA. ECC is an ideal candidate\nfor implementation on constrained devices where the major computational\nresources i.e. speed, memory are limited and low-power wireless communication\nprotocols are employed. That is because it attains the same security levels\nwith traditional cryptosystems using smaller parameter sizes. Moreover, in\nseveral application areas such as person identification and eVoting, it is\nfrequently required of entities to prove knowledge of some fact without\nrevealing this knowledge. Such proofs of knowledge are called Zero Knowledge\nInteractive Proofs (ZKIP) and involve interactions between two communicating\nparties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the\npossesion of some information (e.g. authentication information) to the Verifier\nwithout disclosing it. In this paper, we focus on the application of ZKIP\nprotocols on resource constrained devices. We study well-established ZKIP\nprotocols based on the discrete logarithm problem and we transform them under\nthe ECC setting. Then, we implement the proposed protocols on Wiselib, a\ngeneric and open source algorithmic library. Finally, we present a thorough\nevaluation of the protocols on two popular hardware platforms equipped with low\nend microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers,\nin terms of code size, execution time, message size and energy requirements. To\nthe best of our knowledge, this is the first attempt of implementing and\nevaluating ZKIP protocols with emphasis on low-end devices. This work's results\ncan be used from developers who wish to achieve certain levels of security and\nprivacy in their applications.\n
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources i.e. speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. Moreover, in several application areas such as person identification and eVoting, it is frequently required of entities to prove knowledge of some fact without revealing this knowledge. Such proofs of knowledge are called Zero Knowledge Interactive Proofs (ZKIP) and involve interactions between two communicating parties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the possesion of some information (e.g. authentication information) to the Verifier without disclosing it. In this paper, we focus on the application of ZKIP protocols on resource constrained devices. We study well-established ZKIP protocols based on the discrete logarithm problem and we transform them under the ECC setting. Then, we implement the proposed protocols on Wiselib, a generic and open source algorithmic library. Finally, we present a thorough evaluation of the protocols on two popular hardware platforms equipped with low end microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers, in terms of code size, execution time, message size and energy requirements. To the best of our knowledge, this is the first attempt of implementing and evaluating ZKIP protocols with emphasis on low-end devices. This work's results can be used from developers who wish to achieve certain levels of security and privacy in their applications.
We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of [19]. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.
Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya
Abstract. Efficient non-interactive zero-knowledge proofs are a powerful tool for solving many cryptographic problems. We apply the recent Groth-Sahai (GS) proof system for pairing product equations (Eurocrypt 2008) to two related cryptographic problems: compact e-cash (Eurocrypt 2005) and simulatable verifiable random functions (CRYPTO 2007). We present the first efficient compact e-cash scheme that does not rely on a random oracle. To this end we construct efficient GS proofs for signature possession, pseudo randomness and set membership. The GS proofs for pseudorandom functions give rise to a much cleaner and substantially faster construction of simulatable verifiable random functions (sVRF) under a weaker number theoretic assumption. We obtain the first efficient fully simulatable sVRF with a polynomial sized output domain (in the security parameter). 1
Let n be a large composite number. Without factoring n, the computation of a 2 t (mod n)given a, t with gcd(a# n) = 1 and t!n can be done in t squarings modulo n.For t n (e.g., n?2 1024 and t!2 100 ), no lower complexity than t squarings is known to fulfill this task. Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems. We argue the necessity for a zero-knowledge proof of the correctness of such constructions and propose the first practically efficient protocol for a realisation. Our protocol proves, in log 2 t standard crypto operations, the correctness of (a e ) 2 t (mod n) with respect to a e where e is an RSA encryption exponent. With such a proof, a Timed-release Encryption of a message M can be given as a 2 t M (mod n) with the assertion that the correct decryption of the RSA ciphertext M e (mod n) can be obtained by performing t squarings modulo n starting from a. Timed-release RSA signatures can be constructed analogously. Keywords Timed-release cryptography, Time-lock puzzles, Non-parallelisability, Efficient zero-knowledge protocols. 1
<p>This paper presents the first efficient statistical zero-knowledge protocols to prove statements such as:<br />A committed number is a pseudo-prime.<br />A committed (or revealed) number is the product of two safe primes, i.e., primes p and q such that (p - 1)=2 and (q - 1)=2 are primes as well.<br />A given value is of large order modulo a composite number that consists of two safe prime factors.</p><p>So far, no methods other than inefficient circuit-based proofs are known for proving such properties. Proving the second property is for instance necessary in many recent cryptographic schemes that rely on both the hardness of computing discrete logarithms and of difficulty computing roots modulo a composite.<br />The main building blocks of our protocols are statistical zero-knowledge proofs that are of independent interest. Mainly, we show how to prove the correct computation of a modular addition, a modular multiplication, or a modular exponentiation, where all values including the modulus are committed but not<br />publicly known. Apart from the validity of the computation, no other information about the modulus (e.g., a generator which order equals the modulus) or any other operand is given. Our technique can be generalized to prove in zeroknowledge<br />that any multivariate polynomial equation modulo a certain modulus is satisfied, where only commitments to the variables of the polynomial and a commitment to the modulus must be known. This improves previous results,<br />where the modulus is publicly known.<br />We show how a prover can use these building blocks to convince a verifier that a committed number is prime. This finally leads to efficient protocols for proving that a committed (or revealed) number is the product of two safe primes. As a consequence, it can be shown that a given value is of large order modulo a<br />given number that is a product of two safe primes.</p><p> </p><p>Keywords. RSA-based protocols, zero-knowledge proofs of knowledge, primality tests.</p>
We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, a<br />circuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)<br />interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication<br />of Omega(n^3 log n) bits.<br />Variations of the technique behind these protocols lead to other interesting applications.<br />We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)<br />bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.<br />As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof<br />system with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.
We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that x 2 L with error probability less than 2 \\Gammak using communication corresponding to O(jxj c )+O(k) bit commitments, where c is a constant depending only on L. We also present a 4-move perfect zero knowledge interactive argument for any NP-language L. On input x 2 L, the communication complexity is O(jxj c ) \\Delta max(k; l) bits, where l is the security parameter for the prover 1 . The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: our protocols allows proving/arguing satisfiability of a Boo...