Cryptology ePrint Archive: Report 2012/239

Zero-Knowledge for Multivariate Polynomials

Valerie Nachef and Jacques Patarin and Emmanuel Volte

Abstract: In~\cite{SSH} a Zero-Knowledge scheme $ZK(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 $ZK(d)$ and $\tilde {ZK}(d)$ from a set of polynomial equations of degree $d$. We will show that $\tilde {ZK} (d)$ is optimal in term of the number of computations to be performed and that $ZK(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.

Category / Keywords: cryptographic protocols / Authentication scheme, Zero-Knowledge, Multivariate polynomials.

Date: received 29 Apr 2012

Contact author: valerie nachef at u-cergy fr

Available formats: PDF | BibTeX Citation

Version: 20120430:154312 (All versions of this report)

Discussion forum: Show discussion | Start new discussion