Four-Round Concurrent Non-Malleable Commitments from One-Way Functions

Michele Ciampi; Rafail Ostrovsky; Luisa Siniscalchi; Ivan Visconti

doi:10.1007/978-3-319-63715-0_5

Four-Round Concurrent Non-Malleable Commitments from One-Way Functions

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti

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

Abstract

How many rounds and which assumptions are required for concurrent non-malleable commitments? The above question has puzzled researchers for several years. Pass in [TCC 2013] showed a lower bound of 3 rounds for the case of black-box reductions to falsifiable hardness assumptions with respect to polynomial-time adversaries. On the other side, Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions (OWFs) are sufficient with a constant number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed a 3-round construction based on subexponentially strong one-way permutations.

In this work we show as main result the first 4-round concurrent non-malleable commitment scheme assuming the existence of any one-way function.

Our approach builds on a new security notion for argument systems against man-in-the-middle attacks: Simulation-Witness-Independence. We show how to construct a 4-round one-many simulation-witnesses-independent argument system from one-way functions. We then combine this new tool in parallel with a weak form of non-malleable commitments constructed by Goyal et al. in [FOCS 2014] obtaining the main result of our work.

Original language	English
Title of host publication	Advances in Cryptology -- CRYPTO 2017
Editors	Jonathan Katz, Hovav Shacham
Place of Publication	Cham
Publisher	Springer
Pages	127-157
Number of pages	31
ISBN (Electronic)	978-3-319-63715-0
ISBN (Print)	978-3-319-63714-3
DOIs	https://doi.org/10.1007/978-3-319-63715-0_5
Publication status	Published - 29 Jul 2017
Event	CRYPTO 2017: 37th Annual International Cryptology Conference - University of California, Santa Barbara, Santa Barbara, United States Duration: 20 Aug 2016 → 24 Aug 2017 https://www.iacr.org/conferences/crypto2017/ https://www.iacr.org/conferences/crypto2017/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	10402
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	CRYPTO 2017
Abbreviated title	CRYPTO 2017
Country/Territory	United States
City	Santa Barbara
Period	20/08/16 → 24/08/17
Internet address	https://www.iacr.org/conferences/crypto2017/ https://www.iacr.org/conferences/crypto2017/

Access to Document

10.1007/978-3-319-63715-0_5

Ciampi_4-roundAccepted author manuscript, 654 KB

https://link.springer.com/chapter/10.1007%2F978-3-319-63715-0_5

Cite this

@inproceedings{705a6b5cb97c4122b962b8b503256144,

title = "Four-Round Concurrent Non-Malleable Commitments from One-Way Functions",

abstract = "How many rounds and which assumptions are required for concurrent non-malleable commitments? The above question has puzzled researchers for several years. Pass in [TCC 2013] showed a lower bound of 3 rounds for the case of black-box reductions to falsifiable hardness assumptions with respect to polynomial-time adversaries. On the other side, Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions (OWFs) are sufficient with a constant number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed a 3-round construction based on subexponentially strong one-way permutations. In this work we show as main result the first 4-round concurrent non-malleable commitment scheme assuming the existence of any one-way function. Our approach builds on a new security notion for argument systems against man-in-the-middle attacks: Simulation-Witness-Independence. We show how to construct a 4-round one-many simulation-witnesses-independent argument system from one-way functions. We then combine this new tool in parallel with a weak form of non-malleable commitments constructed by Goyal et al. in [FOCS 2014] obtaining the main result of our work.",

author = "Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Ivan Visconti",

year = "2017",

month = jul,

day = "29",

doi = "10.1007/978-3-319-63715-0\_5",

language = "English",

isbn = "978-3-319-63714-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "127--157",

editor = "Jonathan Katz and Hovav Shacham",

booktitle = "Advances in Cryptology -- CRYPTO 2017",

address = "United Kingdom",

note = "CRYPTO 2017 : 37th Annual International Cryptology Conference, CRYPTO 2017 ; Conference date: 20-08-2016 Through 24-08-2017",

url = "https://www.iacr.org/conferences/crypto2017/, https://www.iacr.org/conferences/crypto2017/",

}

Ciampi, M, Ostrovsky, R, Siniscalchi, L & Visconti, I 2017, Four-Round Concurrent Non-Malleable Commitments from One-Way Functions. in J Katz & H Shacham (eds), Advances in Cryptology -- CRYPTO 2017. Lecture Notes in Computer Science, vol. 10402, Springer, Cham, pp. 127-157, CRYPTO 2017, Santa Barbara, United States, 20/08/16. https://doi.org/10.1007/978-3-319-63715-0_5

Four-Round Concurrent Non-Malleable Commitments from One-Way Functions. / Ciampi, Michele; Ostrovsky, Rafail; Siniscalchi, Luisa et al.
Advances in Cryptology -- CRYPTO 2017. ed. / Jonathan Katz; Hovav Shacham. Cham: Springer, 2017. p. 127-157 (Lecture Notes in Computer Science; Vol. 10402).

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

TY - GEN

T1 - Four-Round Concurrent Non-Malleable Commitments from One-Way Functions

AU - Ciampi, Michele

AU - Ostrovsky, Rafail

AU - Siniscalchi, Luisa

AU - Visconti, Ivan

PY - 2017/7/29

Y1 - 2017/7/29

N2 - How many rounds and which assumptions are required for concurrent non-malleable commitments? The above question has puzzled researchers for several years. Pass in [TCC 2013] showed a lower bound of 3 rounds for the case of black-box reductions to falsifiable hardness assumptions with respect to polynomial-time adversaries. On the other side, Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions (OWFs) are sufficient with a constant number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed a 3-round construction based on subexponentially strong one-way permutations. In this work we show as main result the first 4-round concurrent non-malleable commitment scheme assuming the existence of any one-way function. Our approach builds on a new security notion for argument systems against man-in-the-middle attacks: Simulation-Witness-Independence. We show how to construct a 4-round one-many simulation-witnesses-independent argument system from one-way functions. We then combine this new tool in parallel with a weak form of non-malleable commitments constructed by Goyal et al. in [FOCS 2014] obtaining the main result of our work.

AB - How many rounds and which assumptions are required for concurrent non-malleable commitments? The above question has puzzled researchers for several years. Pass in [TCC 2013] showed a lower bound of 3 rounds for the case of black-box reductions to falsifiable hardness assumptions with respect to polynomial-time adversaries. On the other side, Goyal [STOC 2011], Lin and Pass [STOC 2011] and Goyal et al. [FOCS 2012] showed that one-way functions (OWFs) are sufficient with a constant number of rounds. More recently Ciampi et al. [CRYPTO 2016] showed a 3-round construction based on subexponentially strong one-way permutations. In this work we show as main result the first 4-round concurrent non-malleable commitment scheme assuming the existence of any one-way function. Our approach builds on a new security notion for argument systems against man-in-the-middle attacks: Simulation-Witness-Independence. We show how to construct a 4-round one-many simulation-witnesses-independent argument system from one-way functions. We then combine this new tool in parallel with a weak form of non-malleable commitments constructed by Goyal et al. in [FOCS 2014] obtaining the main result of our work.

U2 - 10.1007/978-3-319-63715-0_5

DO - 10.1007/978-3-319-63715-0_5

M3 - Conference contribution

SN - 978-3-319-63714-3

T3 - Lecture Notes in Computer Science

SP - 127

EP - 157

BT - Advances in Cryptology -- CRYPTO 2017

A2 - Katz, Jonathan

A2 - Shacham, Hovav

PB - Springer

CY - Cham

T2 - CRYPTO 2017

Y2 - 20 August 2016 through 24 August 2017

ER -

Four-Round Concurrent Non-Malleable Commitments from One-Way Functions

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this