conference paper published Abhishek Jain author Stephan Krenn author 329FCCF0-F248-11E8-B48F-1D18A9856A870000-0003-2835-9093 Krzysztof Z Pietrzak author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654 Aris Tentes author XiaoyunWang editor KazueSako editor KrPi department ASIACRYPT: Theory and Application of Cryptology and Information Security Provable Security for Physical Cryptography project 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. https://research-explorer.ista.ac.at/download/2974/5048/IST-2016-721-v1+1_513.pdf application/pdfno Springer2012Beijing, China eng 10.1007/978-3-642-34961-4_40 7658663 - 680 Jain, A., Krenn, S., Pietrzak, K. Z., &#38; Tentes, A. (2012). Commitments and efficient zero knowledge proofs from learning parity with noise. In X. Wang &#38; K. Sako (Eds.) (Vol. 7658, pp. 663–680). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Beijing, China: Springer. <a href="https://doi.org/10.1007/978-3-642-34961-4_40">https://doi.org/10.1007/978-3-642-34961-4_40</a> 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. Commitments and efficient zero knowledge proofs from learning parity with noise. In: Wang X, Sako K, eds. Vol 7658. Springer; 2012:663-680. doi:<a href="https://doi.org/10.1007/978-3-642-34961-4_40">10.1007/978-3-642-34961-4_40</a> A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680. Jain, Abhishek, et al. <i>Commitments and Efficient Zero Knowledge Proofs from Learning Parity with Noise</i>. Edited by Xiaoyun Wang and Kazue Sako, vol. 7658, Springer, 2012, pp. 663–80, doi:<a href="https://doi.org/10.1007/978-3-642-34961-4_40">10.1007/978-3-642-34961-4_40</a>. 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. <a href="https://doi.org/10.1007/978-3-642-34961-4_40">https://doi.org/10.1007/978-3-642-34961-4_40</a>. 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. 29742018-12-11T12:00:38Z2021-01-12T07:40:11Z