International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model

Peter Hall , New York University
Feng-Hao Liu , Florida Atlantic University
Chloe Cachet , University of Connecticut
Benjamin Fuller , University of Connecticut
Daniel Apon , MITRE
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). We define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is public but protected from all tampering. We construct a digital locker using a similar paradigm. Our construction achieves nonmalleability over the output point by placing a CRS into the associated data and using an appropriate non-interactive zero-knowledge proof. Tampering is protected against the input point over low-degree polynomials and over any tampering to the output point and associated data. Our constructions achieve virtual black box security. These constructions are then used to create robust fuzzy extractors that can support low-entropy sources in the plain model. By using the geometric structure of a syndrome secure sketch (Dodis et al., SIAM Journal on Computing 2008), the adversary's tampering function can always be expressed as a low-degree polynomial; thus, the protection provided by the constructed nonmalleable objects suffices.
Video from ASIACRYPT 2022
  title={Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model},
  author={Peter Hall and Feng-Hao Liu and Chloe Cachet and Benjamin Fuller and Daniel Apon},