Zero-Knowledge for  Multivariate Polynomials

Valerie Nachef; Jacques Patarin; Emmanuel Volte

Paper 2012/239

Zero-Knowledge for Multivariate Polynomials

Valerie Nachef, Jacques Patarin, and Emmanuel Volte

Abstract

In~\cite{SSH} a Zero-Knowledge scheme $Z K (2)$ was designed from a solution of a set of multivariate quadratic equations over a finite field. In this paper we will give two methods to generalize this construction for polynomials of any degree $d$ , i.e. we will design two Zero-Knowledge schemes $Z K (d)$ and $\tilde{Z K} (d)$ from a set of polynomial equations of degree $d$ . We will show that $\tilde{Z K} (d)$ is optimal in term of the number of computations to be performed and that $Z K (d)$ is optimal in term of the number of bits to be send. Moreover this property is 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: Authentication scheme Zero-Knowledge Multivariate polynomials.
Contact author(s): valerie nachef @ u-cergy fr
History: 2012-04-30: received
Short URL: https://ia.cr/2012/239
License: CC BY

BibTeX

@misc{cryptoeprint:2012/239,
      author = {Valerie Nachef and Jacques Patarin and Emmanuel Volte},
      title = {Zero-Knowledge for  Multivariate Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/239},
      year = {2012},
      url = {https://eprint.iacr.org/2012/239}
}