Four-Round Black-Box Non-malleable Schemes from One-Way Permutations

Michele Ciampi; Emmanuela Orsini; Luisa Siniscalchi

doi:10.1007/978-3-031-22365-5_11

Four-Round Black-Box Non-malleable Schemes from One-Way Permutations

Michele Ciampi^*, Emmanuela Orsini, Luisa Siniscalchi

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.

Original language	English
Title of host publication	Theory of Cryptography
Subtitle of host publication	20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II
Editors	Eike Kiltz, Vinod Vaikuntanathan
Publisher	Springer
Pages	300-329
Number of pages	30
ISBN (Print)	9783031223648
DOIs	https://doi.org/10.1007/978-3-031-22365-5_11
Publication status	Published - 21 Dec 2022
Event	20th Theory of Cryptography Conference, TCC 2022 - Chicago, United States Duration: 7 Nov 2022 → 10 Nov 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13748 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th Theory of Cryptography Conference, TCC 2022
Country/Territory	United States
City	Chicago
Period	7/11/22 → 10/11/22

Access to Document

10.1007/978-3-031-22365-5_11Licence: All Rights Reserved

Four-Round Black-Box_CIAMPI_DOA28082022_AFV_CC BYAccepted author manuscript, 734 KBLicence: Creative Commons: Attribution (CC-BY)

https://eprint.iacr.org/2022/1543Licence: Creative Commons: Attribution (CC-BY)
https://link.springer.com/chapter/10.1007/978-3-031-22365-5_11Licence: All Rights Reserved

Cite this

Ciampi, M., Orsini, E., & Siniscalchi, L. (2022). Four-Round Black-Box Non-malleable Schemes from One-Way Permutations. In E. Kiltz, & V. Vaikuntanathan (Eds.), Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II (pp. 300-329). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13748 LNCS). Springer. https://doi.org/10.1007/978-3-031-22365-5_11

Ciampi, Michele ; Orsini, Emmanuela ; Siniscalchi, Luisa. / Four-Round Black-Box Non-malleable Schemes from One-Way Permutations. Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II. editor / Eike Kiltz ; Vinod Vaikuntanathan. Springer, 2022. pp. 300-329 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1f03838e8dd448218d3e42b769be71e4,

title = "Four-Round Black-Box Non-malleable Schemes from One-Way Permutations",

abstract = "We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.",

author = "Michele Ciampi and Emmanuela Orsini and Luisa Siniscalchi",

note = "Funding Information: Acknowledgements. We thank Carmit Hazay and Muthuramakrishnan Venkitasub-ramaniam for insightful discussions on the MPC-in-the-head approach. Emmanuela Orsini was supported by the Defense Advanced Research Projects Agency (DARPA) under contract No. HR001120C0085, and by CyberSecurity Research Flanders with reference number VR20192203. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the DARPA, the US Government or Cyber Security Research Flanders. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein. ; 20th Theory of Cryptography Conference, TCC 2022 ; Conference date: 07-11-2022 Through 10-11-2022",

year = "2022",

month = dec,

day = "21",

doi = "10.1007/978-3-031-22365-5_11",

language = "English",

isbn = "9783031223648",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "300--329",

editor = "Eike Kiltz and Vinod Vaikuntanathan",

booktitle = "Theory of Cryptography",

address = "United Kingdom",

}

Ciampi, M, Orsini, E & Siniscalchi, L 2022, Four-Round Black-Box Non-malleable Schemes from One-Way Permutations. in E Kiltz & V Vaikuntanathan (eds), Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13748 LNCS, Springer, pp. 300-329, 20th Theory of Cryptography Conference, TCC 2022, Chicago, United States, 7/11/22. https://doi.org/10.1007/978-3-031-22365-5_11

Four-Round Black-Box Non-malleable Schemes from One-Way Permutations. / Ciampi, Michele; Orsini, Emmanuela; Siniscalchi, Luisa.
Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II. ed. / Eike Kiltz; Vinod Vaikuntanathan. Springer, 2022. p. 300-329 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13748 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Four-Round Black-Box Non-malleable Schemes from One-Way Permutations

AU - Ciampi, Michele

AU - Orsini, Emmanuela

AU - Siniscalchi, Luisa

N1 - Funding Information: Acknowledgements. We thank Carmit Hazay and Muthuramakrishnan Venkitasub-ramaniam for insightful discussions on the MPC-in-the-head approach. Emmanuela Orsini was supported by the Defense Advanced Research Projects Agency (DARPA) under contract No. HR001120C0085, and by CyberSecurity Research Flanders with reference number VR20192203. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the DARPA, the US Government or Cyber Security Research Flanders. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.

PY - 2022/12/21

Y1 - 2022/12/21

N2 - We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.

AB - We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than 16 rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with any (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.

UR - http://www.scopus.com/inward/record.url?scp=85146665014&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-22365-5_11

DO - 10.1007/978-3-031-22365-5_11

M3 - Conference contribution

AN - SCOPUS:85146665014

SN - 9783031223648

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 300

EP - 329

BT - Theory of Cryptography

A2 - Kiltz, Eike

A2 - Vaikuntanathan, Vinod

PB - Springer

T2 - 20th Theory of Cryptography Conference, TCC 2022

Y2 - 7 November 2022 through 10 November 2022

ER -

Ciampi M, Orsini E, Siniscalchi L. Four-Round Black-Box Non-malleable Schemes from One-Way Permutations. In Kiltz E, Vaikuntanathan V, editors, Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II. Springer. 2022. p. 300-329. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22365-5_11