Paper 2017/210

Public Key Cryptosystems with Noisy Secret Keys

Charles Herder, Benjamin Fuller, Marten van Dijk, and Srinivas Devadas

Abstract

Passwords bootstrap symmetric and asymmetric cryptography, tying keys to an individual user. Biometrics are intended to strengthen this tie. Unfortunately, biometrics exhibit noise between repeated readings. Fuzzy extractors (Dodis et al., Eurocrypt 2004) derive stable symmetric keys from noisy sources. We ask if it is also possible for noisy sources to directly replace private keys in asymmetric cryptosystems. We propose a new primitive called public-key cryptosystems with noisy keys. Such a cryptosystem functions when the private key varies according to some metric. An intuitive solution is to combine a fuzzy extractor with a public key cryptosystem. Unfortunately, fuzzy extractors need static helper information to account for noise. This helper information creates fundamental limitations on the resulting cryptosytems. To overcome these limitations, we directly construct public-key encryption and digital signature algorithms with noisy keys. The core of our constructions is a computational version of the fuzzy vault (Juels and Sudan, Designs, Codes, and Cryptography 2006). Security of our schemes is based on graded encoding schemes (Garg et al., Eurocrypt 2013, Garg et al., TCC 2016). Importantly, our public-key encryption algorithm is based on a weaker model of grading encoding. If functional encryption or indistinguishable obfuscation exist in this weaker model, they also exist in the standard model. In addition, we use the computational fuzzy vault to construct the first reusable fuzzy extractor (Boyen, CCS 2004) supporting a linear fraction of errors.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
fuzzy extractorgraded encoding
Contact author(s)
chherder @ gmail com
History
2017-03-01: received
Short URL
https://ia.cr/2017/210
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/210,
      author = {Charles Herder and Benjamin Fuller and Marten van Dijk and Srinivas Devadas},
      title = {Public Key Cryptosystems with Noisy Secret Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2017/210},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/210}},
      url = {https://eprint.iacr.org/2017/210}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.