Abstract
In [15] a protocol ZK(2) using zero-knowledge argument of knowledge was designed from a solution of a set of multivariate quadratic equations over a finite field (i.e. from MQ problem). In this paper, we propose a new scheme ZK(d) which is a generalization of ZK(2), i.e. we consider systems of polynomials of degree d. The key idea of the scheme ZK(d) is to use a polarization identity that allows to get a d-linear function and then use a cut-and-choose technique. We also observe that the scheme \(\tilde{ZK}(d)\), which is the natural generalization of the protocol based on the MQ problem to higher degree, is more efficient in terms of computations whereas the ZK(d) scheme is better in terms of bits to be sent. Moreover these properties are still true for all kinds of polynomials: for example if the polynomials are sparse or dense. Finally, we will present two examples of applications: with Brent equations, or with morphisms of polynomials.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bard, G.V.: New Practical Strassen-like Approximate Matrix-multiplication Algorithms found via solving a system of cubic equations, http://www.users.math.umd.edu/~bardg/
Berbain, C., Gilbert, H., Patarin, J.: QUAD: A Practical Stream Cipher with Provable Security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 109–128. Springer, Heidelberg (2006)
Courtois, N., Bard, G.V., Hulme, D.: A new general-purpose method to multiply 3x3 matrices using only 23 multiplications. CoRR, abs/1108.2830 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completness. W.H. Freeman and Co. (1979)
Goldreich, O.: Foundations of Cryptography: Volume I. Basic Tools. Cambridge University Press, Cambridge (2001)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM 38, 690–728 (1991)
Halevi, S., Micali, S.: Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996)
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar Signature Schemes. In: Reisig, W., Rozenberg, G. (eds.) APN 1998. LNCS, vol. 1492, pp. 206–222. Springer, Heidelberg (1998)
Laderman, J.: A noncomuutative algorithm for multiplying 3 x3 matrices using 23 multiplication. Bulletin of the American Mathematical Society 82, 126–128 (1976)
Matsumoto, T., Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Patarin, J., Goubin, L.: Trapdoor One-Way Permutations and Multivariate Polynomials. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 356–368. Springer, Heidelberg (1997)
Pointcheval, D.: A New Identification Scheme Based on the Perceptrons Problem. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 319–328. Springer, Heidelberg (1995)
Sakumoto, K.: Public-Key Identification Schemes Based on Multivariate Cubic Polynomials. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 172–189. Springer, Heidelberg (2012)
Sakumoto, K., Shirai, T., Hiwatari, H.: Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 706–723. Springer, Heidelberg (2011)
Shamir, A.: An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 606–609. Springer, Heidelberg (1990)
Stern, J.: A New Identification Scheme Based on Syndrome Decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994)
Stern, J.: Designing Identification Schemes with Keys of Short Size. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 164–173. Springer, Heidelberg (1994)
Strassen, V.: Gaussion Elimination is not optimal. Numerische Mathematik 13(3), 354–356 (1969)
Thomas, E.G.F.: A Polarizatin Identity for Multilinear Maps. University of Groningen - Preprint (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nachef, V., Patarin, J., Volte, E. (2012). Zero-Knowledge for Multivariate Polynomials. In: Hevia, A., Neven, G. (eds) Progress in Cryptology – LATINCRYPT 2012. LATINCRYPT 2012. Lecture Notes in Computer Science, vol 7533. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33481-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-33481-8_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33480-1
Online ISBN: 978-3-642-33481-8
eBook Packages: Computer ScienceComputer Science (R0)