Paper 2022/1108

Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model

Daniel Apon, MITRE
Chloe Cachet, University of Connecticut
Benjamin Fuller, University of Connecticut
Peter Hall, New York University
Feng-Hao Liu, Florida Atlantic University

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). Along the way, 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 use the same paradigm to then extend this to digital lockers. Our constructions achieve 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.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Point obfuscation digital lockers nonmalleability virtual black box obfuscation fuzzy extractors.
Contact author(s)
dapon crypto @ gmail com
chloe cachet @ uconn edu
benjamin fuller @ uconn edu
pf2184 @ nyu edu
liuf @ fau edu
2022-09-19: revised
2022-08-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Apon and Chloe Cachet and Benjamin Fuller and Peter Hall and Feng-Hao Liu},
      title = {Nonmalleable Digital Lockers and Robust Fuzzy Extractors in the Plain Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1108},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.