nach oben

Designs, Codes and Cryptography

Erschienen in:

01.12.2015

Zero-knowledge proofs of knowledge for group homomorphisms

verfasst von: Ueli Maurer

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2-3/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A simple zero-knowledge proof of knowledge protocol is presented of which many known protocols are instantiations. These include Schnorr’s protocol for proving knowledge of a discrete logarithm, the Fiat–Shamir and Guillou–Quisquater protocols for proving knowledge of a modular root, protocols for proving knowledge of representations (like Okamoto’s protocol), protocols for proving equality of secret values, a protocol for proving the correctness of a Diffie–Hellman key, protocols for proving the multiplicative relation of three commitments (as required in secure multi-party computation), and protocols used in credential systems. This unifies a substantial body of work and can also lead to instantiations of the protocol for new applications.

Vorheriger Artikel Further results on the number of rational points of hyperelliptic supersingular curves in characteristic 2

Nächster Artikel Normal forms of hyperelliptic curves of genus 3

A correct argument is more involved; one has to argue that there exists an efficient knowledge extractor (see Sect. 3).

Equivalently, one can consider a relation on \(\{0,1\}^*\).

K must be able to choose the randomness of \(\hat{P}\) and to reset \(\hat{P}\).

It is also often called special soundness [6, 7] when the challenge space is large.

The last point implies that every particular challenge sequence \(c_1,\ldots ,c_s\) has negligible probability of being selected by an honest verifier.

The indistinguishability could also be statistical or computational.

This is sometimes also called special honest-verifier zero-knowledge [6, 7].

This requires access to the strategy of \(\hat{V}\), or \(\hat{V}\) must be rewindable.

Note, however, that our treatment and claims do not depend on the one-way property. Should f not be one-way, then the protocols are perhaps less useful, but they still have the claimed properties.

When we define a group homomorphism in terms of a given group homomorphism (denoted \([\cdot ]\)), then we write \([\![\cdot ]\!]\) to avoid overloading the symbol \([\cdot ]\).

There can be at least two reasons for choosing a small challenge space. First, a larger space may not work, for example if e is small in the GQ protocol. Second, one may want the protocol to be zero-knowledge, which generally does not hold for large (per-round) challenge space.

The group operations in \(G_1\times \cdots \times G_n\) and \(H_1\times \cdots \times H_n\) are defined component-wise.

Note that if the homomorphisms are bijective, then this protocol not only proves knowledge of x, but actually that all embedded values are identical.

One commits to a value x by choosing a random r and sending \(h_1^x h_2^{\rho }\) as the commitment (see also Sect. 6.7). This commitment scheme is information-theoretically hiding (but only computationally binding).

Aggarwal D., Maurer U.: Breaking RSA generically is equivalent to factoring. In: Advances in Cryptology—EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 36–53. Springer, Berlin (2009).

Bangerter E.: Efficient zero knowledge proofs of knowledge for homomorphisms. Ph.D. Thesis, Ruhr University Bochum (2005).

Bangerter E., Camenisch J., Maurer U.: Efficient proofs of knowledge of discrete logarithms and representations in groups with hidden order. In: Public Key Cryptography—PKC 2005. Lecture Notes in Computer Science, vol. 3386, pp. 154–171. Springer, Berlin (2005).

Bangerter E., Camenisch J., Krenn S.: Efficiency limitations for \(\varSigma \)-protocols for group homomorphisms. In: Theory of Cryptography TCC. Lecture Notes in Computer Science, vol. 5978, pp. 553–571. Springer, Berlin (2010).

Camenisch J., Kiayias A., Yung M.: On the portability of generalized Schnorr proofs. In: Advances in Cryptology—EUROCRYPT 2009. Lecture Notes in Computer Science, vol. 5479, pp. 425–442. Springer, Berlin (2009).

Cramer R.: Modular design of secure, yet practical cryptographic protocols. Ph.D. Thesis, University of Amsterdam (1996).

Damgård I.: On \(\varSigma \)-Protocols. Course Notes. Århus University, Denmark (2002).

Diffie W., Hellman M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976).

Feige U., Fiat A., Shamir A.: Zero-knowledge proofs of identity. J. Cryptol. 1, 77–94 (1988).

10.

Fiat A., Shamir A.: How to prove yourself: practical solution to identification and signature problems. In: Advances in Cryptology—CRYPTO ’86. Lecture Notes in Computer Science, vol. 263, pp. 186–194. Springer, Berlin (1987).

11.

Goldwasser S., Micali S., Rackoff C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186–208 (1989).

12.

Guillou L.C., Quisquater J.-J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Advances in Cryptology—EUROCRYPT ’88. Lecture Notes in Computer Science, vol. 330, pp. 123–128. Springer, Berlin (1988).

13.

Koyama K., Maurer U., Okamoto T., Vanstone S.A.: New public-key schemes based on elliptic curves over \(Z_n\). In: Advances in Cryptology—CRYPTO ’91. Lecture Notes in Computer Science, vol. 576, pp. 252–266. Springer, Berlin (1992).

14.

Maurer U.: Unifying zero-knowledge proofs of knowledge. In: Preneel, B. (ed.) Advances in Cryptology—AFRICACRYPT 2009. Lecture Notes in Computer Science, vol. 5580, pp. 272–286. Springer, Berlin (2009).

15.

Okamoto T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Advances in Cryptology—CRYPTO ’92. Lecture Notes in Computer Science, vol. 740, pp. 31–53. Springer, Berlin (1992).

16.

Pedersen T.: Non-interactive and information-theoretical secure verifiable secret sharing. In: Advances in Cryptology—CRYPTO ’91. Lecture Notes in Computer Science, vol. 576, pp. 129–140. Springer, Berlin (1991).

17.

Rivest R.L., Shamir A., Adleman L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978).

18.

Schnorr C.P.: Efficient identification and signatures for smart cards. In: Advances in Cryptology—CRYPTO ’89. Lecture Notes in Computer Science, vol. 435, pp. 239–252. Springer, Berlin (1990).

Titel: Zero-knowledge proofs of knowledge for group homomorphisms
verfasst von: Ueli Maurer
Publikationsdatum: 01.12.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2-3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-015-0103-5

Springer Professional

Zero-knowledge proofs of knowledge for group homomorphisms

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2-3/2015

Normal forms of hyperelliptic curves of genus 3

Optimal low-power coding for error correction and crosstalk avoidance in on-chip data buses

Maximal arcs and quasi-symmetric designs

Square integer Heffter arrays with empty cells

PASS-Encrypt: a public key cryptosystem based on partial evaluation of polynomials

Open problems in hash function security

Premium Partner