Non-interactive Non-malleability from Quantum Supremacy

Yael Tauman Kalai, Dakshita Khurana

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 w.r.t. commitment for (Formula Presented) tags for a small constant (Formula Presented), under the following assumptions: 1.Sub-exponential hardness of factoring or discrete log.2.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 w.r.t. commitment for (Formula Presented) tags (for any constant (Formula Presented)) into a non-interactive non-malleable commitment w.r.t. replacement for (Formula Presented) 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 (Formula Presented) 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
EditorsDaniele Micciancio, Alexandra Boldyreva
Number of pages31
ISBN (Print)9783030269531
StatePublished - 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: Aug 18 2019Aug 22 2019

Publication series

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


Conference39th Annual International Cryptology Conference, CRYPTO 2019
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-interactive Non-malleability from Quantum Supremacy'. Together they form a unique fingerprint.

Cite this