Commitments and efficient zero knowledge proofs from learning parity with noise

A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680.

Download
OA 482.57 KB

Conference Paper | Published | English
Author
Editor
;
Department
Series Title
LNCS
Abstract
We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C. To get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.
Publishing Year
Date Published
2012-12-01
Acknowledgement
We are grateful to Petros Mol for helpful discussions on the reduction for the hardness of the xLPN problem.
Volume
7658
Page
663 - 680
Conference
ASIACRYPT: Theory and Application of Cryptology and Information Security
Conference Location
Beijing, China
Conference Date
2012-12-02 – 2012-12-06
IST-REx-ID

Cite this

Jain A, Krenn S, Pietrzak KZ, Tentes A. Commitments and efficient zero knowledge proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer; 2012:663-680. doi:10.1007/978-3-642-34961-4_40
Jain, A., Krenn, S., Pietrzak, K. Z., & Tentes, A. (2012). Commitments and efficient zero knowledge proofs from learning parity with noise. In X. Wang & K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China: Springer. https://doi.org/10.1007/978-3-642-34961-4_40
Jain, Abhishek, Stephan Krenn, Krzysztof Z Pietrzak, and Aris Tentes. “Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise.” edited by Xiaoyun Wang and Kazue Sako, 7658:663–80. Springer, 2012. https://doi.org/10.1007/978-3-642-34961-4_40.
A. Jain, S. Krenn, K. Z. Pietrzak, and A. Tentes, “Commitments and efficient zero knowledge proofs from learning parity with noise,” presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China, 2012, vol. 7658, pp. 663–680.
Jain A, Krenn S, Pietrzak KZ, Tentes A. 2012. Commitments and efficient zero knowledge proofs from learning parity with noise. ASIACRYPT: Theory and Application of Cryptology and Information Security, LNCS, vol. 7658. 663–680.
Jain, Abhishek, et al. Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658, Springer, 2012, pp. 663–80, doi:10.1007/978-3-642-34961-4_40.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:14:00Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar