Abstract
We construct, under standard hardness assumptions, the first non-malleable commitments secure against quantum attacks. Our commitments are statistically binding and satisfy the standard notion of non-malleability with respect to commitment. We obtain a \(\log ^\star (\lambda )\)-round classical protocol, assuming the existence of post-quantum one-way functions.
Previously, non-malleable commitments with quantum security were only known against a restricted class of adversaries known as synchronizing adversaries. At the heart of our results is a new general technique that allows to modularly obtain non-malleable commitments from any extractable commitment protocol, obliviously of the underlying extraction strategy (black-box or non-black-box) or round complexity. The transformation may also be of interest in the classical setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Recall that non-malleability requires that the joint distribution of the output state of the adversary and the committed value are indistinguishable regardless of the committed value on the left. Hence the reduction needs to extract the committed value without disturbing the state of the quantum adversary.
- 2.
In the body, we observe that Naor commitments [Nao91], which can be obtained from (post-quantum) one-way functions, and thus also from any commitment, are in fact sufficient.
- 3.
Recall that currently, if \(w = \mathtt {IP}_2\), we extract \(\tilde{v}_1\) inefficiently using the sequential committed-value oracle \({\mathcal {O}} ^{\infty }= {\mathcal {O}} ^{\infty }[\mathsf {ExCom}.\mathsf {Sen},\mathsf {ExCom}.\mathsf {Rec}]\). If \(w = \mathtt {P}_2\mathtt {I}\) we don’t have this problem, as the ideally scheduled right block commitment i starts after the beginning of Phase 2 on the left.
References
Agarwal, A., Bartusek, J., Goyal, V., Khurana, D., Malavolta, G.: Post-quantum multi-party computation in constant rounds. CoRR, abs/2005.12904 (2020)
Ananth, P., La Placa, R.L.: Secure quantum extraction protocols. IACR Cryptol. ePrint Arch. 2019, 1323 (2019)
Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model, pp. 345–355 (2002)
Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661–1694 (2008)
Bitansky, N., Lin, H.: One-message zero knowledge and non-malleable commitments. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part I. LNCS, vol. 11239, pp. 209–234. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_8
Bitansky, N., Shmueli, O.: Post-quantum zero knowledge in constant rounds. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, 22–26 June 2020, pp. 269–279. ACM (2020)
Chia, N.-H., Chung, K.-M., Liang, X., Yamakawa, T.: Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round. arXiv preprint arXiv:2111.08665 (2021)
Chia, N.-H., Chung, K.-M., Yamakawa, T.: Black-box approach to post-quantum zero-knowledge in constant round. arXiv preprint arXiv:2011.02670 (2020)
Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. SIAM J. Comput. 45(5), 1793–1834 (2016)
Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments. arXiv preprint arXiv:2103.08140 (2021)
Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Concurrent non-malleable commitments (and more) in 3 rounds. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 270–299. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_10
Chor, B., Rabin, M.O.: Achieving independence in logarithmic number of rounds. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, 10–12 August 1987, pp. 260–268 (1987)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Rev. 45(4), 727–784 (2003)
Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)
Fuchs, C.A., Peres, A.: Quantum-state disturbance versus information gain: uncertainty relations for quantum information. Phys. Rev. A 53, 2038–2045 (1996)
Garg, R., Khurana, D., Lu, G., Waters, B.: Black-box non-interactive non-malleable commitments. Cryptology ePrint Archive, Report 2020/1197 (2020). https://eprint.iacr.org/2020/1197
Goyal, V., Khurana, D., Sahai, A.: Breaking the three round barrier for non-malleable commitments, pp. 21–30 (2016)
Goyal, V., Lee, C.-K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach, pp. 51–60 (2012)
Goyal, V.: Constant round non-malleable protocols using one way functions, pp. 695–704 (2011)
Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18–21 June 2016, pp. 1128–1141 (2016)
Goyal, V., Richelson, S.: Non-malleable commitments using Goldreich-Levin list decoding. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, 9–12 November 2019, pp. 686–699 (2019)
Hallgren, S., Smith, A., Song, F.: Classical cryptographic protocols in a quantum world. Int. J. Quant. Inf. 13(04), 1550028 (2015). Preliminary version appeared in IACR Crypto 2011
Khurana, D.: Round optimal concurrent non-malleability from polynomial hardness. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 139–171. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_5
Kalai, Y.T., Khurana, D.: Non-interactive non-malleability from quantum supremacy. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 552–582. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_18
Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15–17 October 2017, pp. 564–575 (2017)
Lombardi, A., Ma, F., Spooner, N.: Post-quantum zero knowledge, revisited (or: How to do quantum rewinding undetectably). arXiv preprint arXiv:2111.12257 (2021)
Lunemann, C., Nielsen, J.B.: Fully simulatable quantum-secure coin-flipping and applications. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 21–40. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21969-6_2
Lin, H., Pass, R.: Non-malleability amplification, pp. 189–198 (2009)
Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function, pp. 705–714 (2011)
Lin, H., Pass, R.: Black-box constructions of composable protocols without set-up. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 461–478. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_27
Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles, pp. 576–587 (2017)
Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571–588. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_31
Lin, H., Pass, R., Venkitasubramaniam, M.: A unified framework for concurrent security: universal composability from stand-alone non-malleability. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31–June 2 2009, pp. 179–188. ACM (2009)
Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991). https://doi.org/10.1007/BF00196774
Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive one-way functions and applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 57–74. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_4
Pass, R., Rosen, A.: Concurrent non-malleable commitments, pp. 563–572 (2005)
Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols, pp. 533–542 (2005)
Pass, R., Wee, H.: Constant-round non-malleable commitments from sub-exponential one-way functions. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 638–655. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_32
Rosen, A.: A note on constant-round zero-knowledge proofs for NP. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 191–202. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_11
Unruh, D.: Quantum proofs of knowledge. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 135–152. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_10
Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009)
Wee, H.: Efficient chosen-ciphertext security via extractable hash proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 314–332. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_17
Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802–803 (1982)
Acknowledgements
Nir Bitansky is a Member of the Check Point Institute of Information Security, supported by ISF grants 18/484 and 19/2137, by Len Blavatnik and the Blavatnik Family Foundation, by the Blavatnik Interdisciplinary Cyber Research Center at Tel Aviv University, and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482). Huijia is supported by NSF grant CNS-1936825 (CAREER), CNS-2026774, a Hellman Fellowship, a JP Morgan AI Research Award, a Simons Collaboration grant on the Theory of Algorithmic Fairness. Omri Shmueli is supported by a Clore Fellowship, ISF grants 18/484 and 19/2137, by Len Blavatnik and the Blavatnik Family Foundation, and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482).
The authors are grateful to Fang Song for valuable discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Bitansky, N., Lin, H., Shmueli, O. (2022). Non-malleable Commitments Against Quantum Attacks. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13277. Springer, Cham. https://doi.org/10.1007/978-3-031-07082-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-031-07082-2_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-07081-5
Online ISBN: 978-3-031-07082-2
eBook Packages: Computer ScienceComputer Science (R0)