Paper 2012/239 Original: eprint.iacr.org/2012/239 ↗
Zero-Knowledge for Multivariate Polynomials
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2012-04-30: last updated
- 2012-04-30: published
- Short URL
- https://ia.cr/2012/239
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}