Round optimal concurrent non-malleability from polynomial hardness

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

Abstract

Non-malleable commitments are a central cryptographic primitive that guarantee security against man-in-the-middle adversaries, and their exact round complexity has been a subject of great interest. Pass (TCC 2013, CC 2016) proved that non-malleable commitments with respect to commitment are impossible to construct in less than three rounds, via black-box reductions to polynomial hardness assumptions. Obtaining a matching positive result has remained an open problem so far. While three-round constructions of non-malleable commitments have been achieved, beginning with the work of Goyal, Pandey and Richelson (STOC 2016), current constructions require super-polynomial assumptions. In this work, we settle the question of whether three-round non-malleable commitments can be based on polynomial hardness assumptions. We give constructions based on polynomial hardness of ZAPs, as well as one out of DDH/QR/ Nt h residuosity. Our protocols also satisfy concurrent non-malleability.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 15th International Conference, TCC 2017, Proceedings
EditorsYael Kalai, Leonid Reyzin
PublisherSpringer
Pages139-171
Number of pages33
ISBN (Print)9783319705026
DOIs
StatePublished - 2017
Externally publishedYes
Event15th International Conference on Theory of Cryptography, TCC 2017 - Baltimore, United States
Duration: Nov 12 2017Nov 15 2017

Publication series

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

Other

Other15th International Conference on Theory of Cryptography, TCC 2017
Country/TerritoryUnited States
CityBaltimore
Period11/12/1711/15/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Round optimal concurrent non-malleability from polynomial hardness'. Together they form a unique fingerprint.

Cite this