Document Open Access Logo

Code Offset in the Exponent

Authors Luke Demarest , Benjamin Fuller , Alexander Russell

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.15.pdf
  • Filesize: 1.17 MB
  • 23 pages

Document Identifiers

Author Details

Luke Demarest
  • University of Connecticut, Storrs, CT, USA
Benjamin Fuller
  • University of Connecticut, Storrs, CT, USA
Alexander Russell
  • University of Connecticut, Storrs, CT, USA

Funding

  • Demarest, Luke: Funded in part by NSF Grants No. 1849904 and 1547399.
  • Fuller, Benjamin: Funded in part by NSF Grants No. 1849904 and 1547399. This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via Contract No. 2019-19020700008. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
  • Russell, Alexander: This material is based upon work supported by the National Science Foundation under Grant No. 1801487.

Acknowledgements

The authors give special thanks to reviewer comments and feedback. The authors thank James Bartusek, Ryann Cartor, Fermi Ma, and Mark Zhandry and their helpful discussions of their work.

Cite AsGet BibTex

Luke Demarest, Benjamin Fuller, and Alexander Russell. Code Offset in the Exponent. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.15

Abstract

Fuzzy extractors derive stable keys from noisy sources. They are a fundamental tool for key derivation from biometric sources. This work introduces a new construction, code offset in the exponent. This construction is 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). A random codeword of a linear error-correcting code is used as a one-time pad for a sampled value from the noisy source. Rather than encoding this directly, code offset in the exponent encodes by exponentiation of a generator in a cryptographically strong group. We introduce and characterize a condition on noisy sources that directly translates to security of our construction in the generic group model. Our condition requires the inner product between the source distribution and all vectors in the null space of the code to be unpredictable.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Biometrics
Keywords
  • fuzzy extractors
  • code offset
  • learning with errors
  • error-correction
  • generic group model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In Theory of cryptography conference, pages 474-495. Springer, 2009. Google Scholar
  2. Daniel Apon, Chongwon Cho, Karim Eldefrawy, and Jonathan Katz. Efficient, reusable fuzzy extractors from LWE. In International Conference on Cyber Security Cryptography and Machine Learning, pages 1-18. Springer, 2017. Google Scholar
  3. Ward Beullens and Hoeteck Wee. Obfuscating simple functionalities from knowledge assumptions. In IACR International Workshop on Public Key Cryptography, pages 254-283. Springer, 2019. Google Scholar
  4. Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, and Kevin Shi. A simple obfuscation scheme for pattern-matching with wildcards. In Annual International Cryptology Conference, pages 731-752. Springer, 2018. Google Scholar
  5. Nir Bitansky, Ran Canetti, Yael Tauman Kalai, and Omer Paneth. On virtual grey box obfuscation for general circuits. Algorithmica, 79(4):1014-1051, 2017. Google Scholar
  6. Xavier Boyen. Reusable cryptographic fuzzy extractors. In Proceedings of the 11th ACM conference on Computer and Communications Security, pages 82-91, 2004. Google Scholar
  7. Ran Canetti and Ronny Ramzi Dakdouk. Obfuscating point functions with multibit output. In Advances in Cryptology-EUROCRYPT 2008, pages 489-508. Springer, 2008. Google Scholar
  8. Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith. Reusable fuzzy extractors for low-entropy distributions. In Advances in Cryptology - EUROCRYPT, pages 117-146. Springer, 2016. Google Scholar
  9. Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith. Reusable fuzzy extractors for low-entropy distributions. Journal of Cryptology, 34(1):1-33, 2021. Google Scholar
  10. Ran Canetti, Yael Tauman Kalai, Mayank Varia, and Daniel Wichs. On symmetric encryption and point obfuscation. In Theory of Cryptography Conference, pages 52-71. Springer, 2010. Google Scholar
  11. Ran Canetti, Guy N Rothblum, and Mayank Varia. Obfuscation of hyperplane membership. In Theory of Cryptography Conference, pages 72-89. Springer, 2010. Google Scholar
  12. Luke Demarest, Benjamin Fuller, and Alexander Russell. Code offset in the exponent. Cryptology ePrint archive, 2018. URL: https://eprint.iacr.org/2018/1005.
  13. Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM journal on computing, 38(1):97-139, 2008. Google Scholar
  14. Nico Döttling and Jörn Müller-Quade. Lossy codes and a new variant of the learning-with-errors problem. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 18-34. Springer, 2013. Google Scholar
  15. Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. Computational fuzzy extractors. In Advances in Cryptology-ASIACRYPT 2013, pages 174-193. Springer, 2013. Google Scholar
  16. Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. Computational fuzzy extractors. Information and Computation, page 104602, 2020. Google Scholar
  17. Benjamin Fuller and Lowen Peng. Continuous-source fuzzy extractors: source uncertainty and insecurity. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2952-2956. IEEE, 2019. Google Scholar
  18. Benjamin Fuller, Leonid Reyzin, and Adam Smith. When are fuzzy extractors possible? In International Conference on the Theory and Application of Cryptology and Information Security, pages 277-306. Springer, 2016. Google Scholar
  19. Benjamin Fuller, Leonid Reyzin, and Adam Smith. When are fuzzy extractors possible? IEEE Transactions on Information Theory, 2020. Google Scholar
  20. Steven D Galbraith and Lukas Zobernig. Obfuscated fuzzy hamming distance and conjunctions from subset product problems. In Theory of Cryptography Conference, pages 81-110. Springer, 2019. Google Scholar
  21. Jing Hao, Han Huang, Galyna Livshyts, and Konstantin Tikhomirov. Distribution of the minimum distance of random linear codes. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 114-119. IEEE, 2020. Google Scholar
  22. Charles Herder, Ling Ren, Marten van Dijk, Meng-Day Yu, and Srinivas Devadas. Trapdoor computational fuzzy extractors and stateless cryptographically-secure physical unclonable functions. IEEE Transactions on Dependable and Secure Computing, 2016. Google Scholar
  23. Chenglu Jin, Charles Herder, Ling Ren, Phuong Ha Nguyen, Benjamin Fuller, Srinivas Devadas, and Marten Van Dijk. Fpga implementation of a cryptographically-secure puf based on learning parity with noise. Cryptography, 1(3):23, 2017. Google Scholar
  24. Ari Juels and Martin Wattenberg. A fuzzy commitment scheme. In Proceedings of the 6th ACM conference on Computer and communications security, pages 28-36, 1999. Google Scholar
  25. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. Google Scholar
  26. Eugene Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5-9, 1962. Google Scholar
  27. Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304, 1960. Google Scholar
  28. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1-40, 2009. Google Scholar
  29. Oded Regev. The learning with errors problem. Invited survey in CCC, 7(30):11, 2010. Google Scholar
  30. Victor Shoup. Lower bounds for discrete logarithms and related problems. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 256-266. Springer, 1997. Google Scholar
  31. Sailesh Simhadri, James Steel, and Benjamin Fuller. Cryptographic authentication from the iris. In International Conference on Information Security, pages 465-485. Springer, 2019. Google Scholar
  32. Yunhua Wen and Shengli Liu. Robustly reusable fuzzy extractor from standard assumptions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 459-489. Springer, 2018. Google Scholar
  33. Yunhua Wen, Shengli Liu, and Dawu Gu. Generic constructions of robustly reusable fuzzy extractor. In IACR International Workshop on Public Key Cryptography, pages 349-378. Springer, 2019. Google Scholar
  34. Joanne Woodage, Rahul Chatterjee, Yevgeniy Dodis, Ari Juels, and Thomas Ristenpart. A new distribution-sensitive secure sketch and popularity-proportional hashing. In Annual International Cryptology Conference, pages 682-710. Springer, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact