Abstract
We show how to construct practical honest-verifier statistical zero-knowledge Diophantine arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi (b+1)st-price auction scheme that work in this model.
Chapter PDF
Similar content being viewed by others
Keywords
References
Adleman, L.M., Manders, K.L.: Diophantine Complexity. In: 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, October 25-27, pp. 81–88. IEEE Computer Society Press, Los Alamitos (1976)
Boudot, F.: Efficient Proofs that a Committed Number Lies in an Interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000) ISBN 3-540-67517-5
Brands, S.: Rapid Demonstration of Linear Relations Connected by Boolean Operators. In: Fumy [Fum97], pp. 318–333
Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally Efficient Multi-Authority Election Scheme. In: Fumy [Fum97], pp. 103–118
Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138. Springer, Heidelberg (1995)
Davis, M.: Hilbert’s Tenth Problem is Unsolvable. American Mathematical Monthly 80(3), 233–269 (1973)
Damgård, I., Fujisaki, E.: An Integer Commitment Scheme Based on Groups with Hidden Order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 1–26. Springer, Heidelberg (2002)
Damgård, I., Jurik, M.: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
Fujisaki, E., Okamoto, T.: Statistical Zero-Knowledge Protocols to Prove Modular Polynomial Relations. IEICE Transaction of Fundamentals of Electronic Communications and Computer Science E82-A(1), 81–92 (1999)
Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Fumy, W. (ed.): EUROCRYPT 1997. LNCS, vol. 1233. Springer, Heidelberg (1997)
Jones, J.P., Matiyasevich, Y.: Register Machine Proof of the Theorem on Exponential Diophantine Representation of Enumerable Sets. Journal of Symbolic Logic 49, 818–829 (1984)
Joye, M., Quisquater, J.-J.: Efficient Computation of Full Lucas Sequences. Electronics Letters 32(6), 537–538 (1996)
Jones, J.P., Sato, D., Wada, H., Wiens, D.: Diophantine Representation of the Set of Prime Numbers. American Mathematical Monthly 83(6), 449–464 (1976)
Lipmaa, H., Asokan, N., Niemi, V.: Secure Vickrey Auctions without Threshold Trust. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 87–101. Springer, Heidelberg (2003)
Lipmaa, H.: Statistical Zero-Knowledge Proofs from Diophantine Equations. Cryptology ePrint Archive, Report 2001/086, November 20 (2001), http://eprint.iacr.org/
Matiyasevich, Y.: Enumerable Sets are Diophantine. Soviet Math., Doklady 11, 354–358 (1970) (English translation)
Matiyasevich, Y.: Hilbert’s Tenth Problem. Foundations of Computing. MIT Press, Cambridge (1993) ISBN 0-262-13295-8
Matiyasevich, Y., Robinson, J.: Reduction of an Arbitrary Diophantine Equation to One in 13 Unknowns. Acta Arithmetica 27, 521–553 (1975)
Pollett, C.: On the Bounded Version of Hilbert’s Tenth Problem. Archive for Mathematical Logic 42(5), 469–488 (2003)
Poupard, G., Stern, J.: Short Proofs of Knowledge for Factoring. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 147–166. Springer, Heidelberg (2000)
Robinson, J.: Existential Definability in Arithmetic. Transactions of the American Mathematical Society 72(3), 437–449 (1952)
Rabin, M.O., Shallit, J.O.: Randomized Algorithms in Number Theory. Communications in Pure and Applied Mathematics 39, 239–256 (1986)
Williams, H.C.: A p + 1 Method of Factoring. Mathematics of Computation 39, 225–234 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lipmaa, H. (2003). On Diophantine Complexity and Statistical Zero-Knowledge Arguments. In: Laih, CS. (eds) Advances in Cryptology - ASIACRYPT 2003. ASIACRYPT 2003. Lecture Notes in Computer Science, vol 2894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-40061-5_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-40061-5_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20592-0
Online ISBN: 978-3-540-40061-5
eBook Packages: Springer Book Archive