Non-malleable zero-knowledge (NMZK), originally introduced in the seminal work of Dolev, Dwork, and Naor (STOC 91), is a fundamental concept for modeling the security of proof systems against man-in-the-middle attacks. Recently, Kim, Liang, and Pandey (CRYPTO 2022) presented the first efficient constant-round NMZK argument system based solely on symmetric-key cryptography. Their construction relies on a non-black-box use of the involved cryptographic primitives and on multiple executions of Ligero (CCS 2017) that affect both the round complexity and the computational efficiency of their protocol. Their work left open the natural important challenge of achieving NMZK using the underlying primitives only in a black-box fashion (regardless of the number of rounds and actual efficiency). In this paper, we solve the aforementioned open problem by presenting the first NMZK argument system based on the black-box use of cryptographic primitives. Our work is optimal in the use of primitives since we only need one-way functions, and asymptotically optimal in the number of rounds since we only require a constant number of rounds. Our argument system is non-malleable with respect to the strong “simulation-extractability” flavor of non-malleability. Furthermore, we also show that our construction can be efficiently instantiated in Minicrypt, significantly improving upon the work of Kim et al., both in terms of round complexity and computational efficiency.

Black-Box (and Fast) Non-malleable Zero Knowledge / Botta, V.; Ciampi, M.; Orsini, E.; Siniscalchi, L.; Visconti, I.. - 14928:(2024), pp. 458-490. (Intervento presentato al convegno Advances in Cryptology tenutosi a Santa Barbara; USA) [10.1007/978-3-031-68400-5_14].

Black-Box (and Fast) Non-malleable Zero Knowledge

Botta V.
;
Visconti I.
2024

Abstract

Non-malleable zero-knowledge (NMZK), originally introduced in the seminal work of Dolev, Dwork, and Naor (STOC 91), is a fundamental concept for modeling the security of proof systems against man-in-the-middle attacks. Recently, Kim, Liang, and Pandey (CRYPTO 2022) presented the first efficient constant-round NMZK argument system based solely on symmetric-key cryptography. Their construction relies on a non-black-box use of the involved cryptographic primitives and on multiple executions of Ligero (CCS 2017) that affect both the round complexity and the computational efficiency of their protocol. Their work left open the natural important challenge of achieving NMZK using the underlying primitives only in a black-box fashion (regardless of the number of rounds and actual efficiency). In this paper, we solve the aforementioned open problem by presenting the first NMZK argument system based on the black-box use of cryptographic primitives. Our work is optimal in the use of primitives since we only need one-way functions, and asymptotically optimal in the number of rounds since we only require a constant number of rounds. Our argument system is non-malleable with respect to the strong “simulation-extractability” flavor of non-malleability. Furthermore, we also show that our construction can be efficiently instantiated in Minicrypt, significantly improving upon the work of Kim et al., both in terms of round complexity and computational efficiency.
2024
Advances in Cryptology
NMZK; Argument systems; Black boxes; Cryptographic primitives; Fundamental concepts; Man in the middle; Non black boxes; Non-malleable zero knowledge; Proof system; Round complexity; Symmetric key cryptography; Cryptography; Computational complexity
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Black-Box (and Fast) Non-malleable Zero Knowledge / Botta, V.; Ciampi, M.; Orsini, E.; Siniscalchi, L.; Visconti, I.. - 14928:(2024), pp. 458-490. (Intervento presentato al convegno Advances in Cryptology tenutosi a Santa Barbara; USA) [10.1007/978-3-031-68400-5_14].
File allegati a questo prodotto
File Dimensione Formato  
Botta_ Black-Box_2024.pdf

solo gestori archivio

Note: https://iacr.org/cryptodb/data/paper.php?pubkey=34393 - DOI: 10.1007/978-3-031-68400-5_14
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.01 MB
Formato Adobe PDF
2.01 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1721685
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact