Paper 2018/716
LatticeBased ZeroKnowledge Arguments for Integer Relations
Benoît Libert, San Ling, Khoa Nguyen, and Huaxiong Wang
Abstract
We provide latticebased protocols allowing to prove relations among committed integers. While the most general zeroknowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is nontrivial, at least if we want to handle exponentially large integers while working with a polynomialsize modulus $q$. For a polynomial $L$, we provide zeroknowledge arguments allowing a prover to convince a verifier that committed $L$bit bitstrings $x$, $y$ and $z$ are the binary representations of integers $X$, $Y$ and $Z$ satisfying $Z=X+Y$ over $\mathbb{Z}$. The complexity of our arguments is only linear in $L$. Using them, we construct arguments allowing to prove inequalities $X<Z$ among committed integers, as well as arguments showing that a committed $X$ belongs to a public interval $[\alpha,\beta]$, where $\alpha$ and $\beta$ can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in $L$) in the maximal range magnitude. Using these tools, we obtain zeroknowledge arguments showing that a committed element $X$ does not belong to a public set $S$ using $\widetilde{\mathcal{O}}(n \cdot \log S)$ bits of communication, where $n$ is the security parameter. We finally give a protocol allowing to argue that committed $L$bit integers $X$, $Y$ and $Z$ satisfy multiplicative relations $Z=XY$ over the integers, with communication cost subquadratic in $L$. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in CRYPTO 2018
 Keywords
 Latticebased cryptographyzeroknowledge argumentsinteger relationsrange proofsnonmembership proofs
 Contact author(s)
 khoantt @ ntu edu sg
 History
 20180801: received
 Short URL
 https://ia.cr/2018/716
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/716, author = {Benoît Libert and San Ling and Khoa Nguyen and Huaxiong Wang}, title = {LatticeBased ZeroKnowledge Arguments for Integer Relations}, howpublished = {Cryptology ePrint Archive, Paper 2018/716}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/716}}, url = {https://eprint.iacr.org/2018/716} }