Paper 2020/682
Succinct Diophantine-Satisfiability Arguments
Patrick Towa and Damien Vergnaud
Abstract
A Diophantine equation is a multi-variate polynomial equation with integer coefficients, and it is satisfiable if it has a solution with all unknowns taking integer values. Davis, Putnam, Robinson and Matiyasevich showed that the general Diophantine satisfiability problem is undecidable (giving a negative answer to Hilbert’s tenth problem) but it is nevertheless possible to argue in zero-knowledge the knowledge of a solution, if a solution is known to a prover. We provide the first succinct honest-verifier zero-knowledge argument for the satisfiability of Diophantine equations with a communication complexity and a round complexity that grows logarithmically in the size of the polynomial equation. The security of our argument relies on standard assumptions on hidden-order groups. As the argument requires to commit to integers, we introduce a new integer-commitment scheme that has much smaller parameters than Damgard and Fujisaki’s scheme. We finally show how to succinctly argue knowledge of solutions to several NP-complete problems and cryptographic problems by encoding them as Diophantine equations.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2020
- Keywords
- Zero KnowledgeDiophantine Equations
- Contact author(s)
-
patrick towa @ gmail com
damien vergnaud @ lip6 fr - History
- 2020-09-29: last of 3 revisions
- 2020-06-09: received
- See all versions
- Short URL
- https://ia.cr/2020/682
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/682,
author = {Patrick Towa and Damien Vergnaud},
title = {Succinct Diophantine-Satisfiability Arguments},
howpublished = {Cryptology ePrint Archive, Paper 2020/682},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/682}},
url = {https://eprint.iacr.org/2020/682}
}
