Paper 2018/1005

Code Offset in the Exponent

Luke Demarest, Benjamin Fuller, and Alexander Russell

Abstract

Fuzzy extractors transform a noisy source e into a stable key which can be reproduced from a nearby value e′. They are a fundamental tool for key derivation from biometric sources. This work introduces code offset in the exponent and uses this construction to build the first reusable fuzzy extractor that simultaneously supports structured, low entropy distributions with correlated symbols and confidence information. These properties are specifically motivated by the most pertinent applications—key derivation from biometrics and physical unclonable functions—which typically demonstrate low entropy with additional statistical correlations and benefit from extractors that can leverage confidence information for efficiency. Code offset in the exponent is a group encoding of the code offset construction (Juels and Wattenberg, CCS 1999) that stores the value e in a one-time pad which is sampled as a codeword, Ax, of a linear error-correcting code: Ax+e. Rather than encoding Ax+e directly, code offset in the exponent calls for encoding by exponentiation of a generator in a cryptographically strong group. We demonstrate security of the construction in the generic group model, establishing security whenever the inner product between the error distribution and all vectors in the null space of the code is unpredictable. We show this condition includes distributions supported by multiple prior fuzzy extractors. Our analysis also shows a prior construction of pattern matching obfuscation (Bishop et al., Crypto 2018) is secure for more distributions than previously known.

Note: Substantial new technical and editorial material. Now shows hardness of general high minentropy distributions. Additionally shows containment of MIPURS in average subset entropy.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
fuzzy extractorscode offsetlearning with errorserror correctiongeneric group modelpattern-matching obfuscation
Contact author(s)
Luke h demarest @ gmail com
benjamin fuller @ uconn edu
acr @ uconn edu
History
2021-02-19: last of 8 revisions
2018-10-22: received
See all versions
Short URL
https://ia.cr/2018/1005
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1005,
      author = {Luke Demarest and Benjamin Fuller and Alexander Russell},
      title = {Code Offset in the Exponent},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1005},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1005}},
      url = {https://eprint.iacr.org/2018/1005}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.