TY - GEN
T1 - One-message zero knowledge and non-malleable commitments
AU - Bitansky, Nir
AU - Lin, Huijia
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2018.
PY - 2018
Y1 - 2018
N2 - We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee—the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.
AB - We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee—the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.
UR - http://www.scopus.com/inward/record.url?scp=85057089522&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057089522&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-03807-6_8
DO - 10.1007/978-3-030-03807-6_8
M3 - Conference contribution
AN - SCOPUS:85057089522
SN - 9783030038069
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 209
EP - 234
BT - Theory of Cryptography - 16th International Conference, TCC 2018, Proceedings
A2 - Beimel, Amos
A2 - Dziembowski, Stefan
PB - Springer Verlag
T2 - 16th Theory of Cryptography Conference, TCC 2018
Y2 - 11 November 2018 through 14 November 2018
ER -