CryptoDB
Succinct Diophantine-Satisfiability Arguments
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: | |
---|---|
Download: | |
Presentation: | Slides |
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. |
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30721, title={Succinct Diophantine-Satisfiability Arguments}, booktitle={Advances in Cryptology - ASIACRYPT 2020}, publisher={Springer}, doi={10.1007/978-3-030-64840-4_26}, author={Patrick Towa and Damien Vergnaud}, year=2020 }