One-message zero knowledge and non-malleable commitments

Nir Bitansky, Huijia Lin

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

Abstract

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 16th International Conference, TCC 2018, Proceedings
EditorsAmos Beimel, Stefan Dziembowski
PublisherSpringer Verlag
Pages209-234
Number of pages26
ISBN (Print)9783030038069
DOIs
StatePublished - 2018
Event16th Theory of Cryptography Conference, TCC 2018 - Panaji, India
Duration: Nov 11 2018Nov 14 2018

Publication series

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

Conference

Conference16th Theory of Cryptography Conference, TCC 2018
Country/TerritoryIndia
CityPanaji
Period11/11/1811/14/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'One-message zero knowledge and non-malleable commitments'. Together they form a unique fingerprint.

Cite this