Paper 2018/1118

Non-Interactive Non-Malleability from Quantum Supremacy

Yael Tauman Kalai and Dakshita Khurana

Abstract

We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions. First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon > 0$, under the following assumptions: - Sub-exponential hardness of factoring or discrete log. - Quantum sub-exponential hardness of learning with errors (LWE). Second, as our key technical contribution, we introduce a new tag amplification technique. We show how to convert any non-interactive non-malleable commitment with respect to commitment for $\epsilon\log \log n$ tags (for any constant $\epsilon>0$) into a non-interactive non-malleable commitment with respect to replacement for $2^n$ tags. This part only assumes the existence of sub-exponentially secure non-interactive witness indistinguishable (NIWI) proofs, which can be based on sub-exponential security of the decisional linear assumption. Interestingly, for the tag amplification technique, we crucially rely on the leakage lemma due to Gentry and Wichs (STOC 2011). For the construction of non-malleable commitments for $\epsilon \log \log n$ tags, we rely on quantum supremacy. This use of quantum supremacy in classical cryptography is novel, and we believe it will have future applications. We provide one such application to two-message witness indistinguishable (WI) arguments from (quantum) polynomial hardness assumptions.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
non-malleable commitmentnon-interactivequantum supremacy
Contact author(s)
dakshkhurana @ gmail com
History
2018-11-20: received
Short URL
https://ia.cr/2018/1118
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1118,
      author = {Yael Tauman Kalai and Dakshita Khurana},
      title = {Non-Interactive Non-Malleability from Quantum Supremacy},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1118},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1118}},
      url = {https://eprint.iacr.org/2018/1118}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.