Abstract | ||
---|---|---|
At ICS 2010, Dziembowski, Pietrzak and Wichs introduced the notion of non-malleable codes, a weaker form of error-correcting codes guaranteeing that the decoding of a tampered codeword either corresponds to the original message or to an unrelated value. The last few years established non-malleable codes as one of the recently invented cryptographic primitives with the highest impact and potential, with very challenging open problems and applications. In this work, we focus on so-called continuously non-malleable codes in the split-state model, as proposed by Faust et al. (TCC 2014), where a codeword is made of two shares and an adaptive adversary makes a polynomial number of attempts in order to tamper the target codeword, where each attempt is allowed to modify the two shares independently (yet arbitrarily). Achieving continuous non-malleability in the split-state model has been so far very hard. Indeed, the only known constructions require strong setup assumptions (i.e., the existence of a common reference string) and strong complexity-theoretic assumptions (i.e., the existence of non-interactive zero-knowledge proofs and collision-resistant hash functions). As our main result, we construct a continuously non-malleable code in the split-state model without setup assumptions, requiring only one-toone one-way functions (i.e., essentially optimal computational assumptions). Our result introduces several new ideas that make progress towards understanding continuous non-malleability, and shows interesting connections with protocol-design and proof-approach techniques used in other contexts (e.g., look-ahead simulation in zero-knowledge proofs, non-malleable commitments, and leakage resilience). |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-319-96878-0_21 | ADVANCES IN CRYPTOLOGY - CRYPTO 2018, PT III |
Keywords | DocType | Volume |
Continuously non-malleable codes,Split-state model,Minimal assumptions | Conference | 10993 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.35 |
References | Authors | |
32 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rafail Ostrovsky | 1 | 8743 | 588.15 |
Giuseppe Persiano | 2 | 1773 | 152.14 |
Daniele Venturi | 3 | 210 | 26.43 |
Ivan Visconti | 4 | 612 | 40.30 |