{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:45:37Z","timestamp":1762875937953,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,12,9]],"date-time":"2017-12-09T00:00:00Z","timestamp":1512777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-14-1-0351"],"award-info":[{"award-number":["FA9550-14-1-0351"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1617774","CNS-1523572"],"award-info":[{"award-number":["CNS-1617774","CNS-1523572"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Herder et al. (IEEE Transactions on Dependable and Secure Computing, 2017) designed a new computational fuzzy extractor and physical unclonable function (PUF) challenge-response protocol based on the Learning Parity with Noise (LPN) problem. The protocol requires no irreversible state updates on the PUFs for security, like burning irreversible fuses, and can correct for significant measurement noise when compared to PUFs using a conventional (information theoretical secure) fuzzy extractor. However, Herder et al. did not implement their protocol. In this paper, we give the first implementation of a challenge response protocol based on computational fuzzy extractors. Our main insight is that \u201cconfidence information\u201d does not need to be kept private, if the noise vector is independent of the confidence information, e.g., the bits generated by ring oscillator pairs which are physically placed close to each other. This leads to a construction which is a simplified version of the design of Herder et al. (also building on a ring oscillator PUF). Our simplifications allow for a dramatic reduction in area by making a mild security assumption on ring oscillator physical obfuscated key output bits.<\/jats:p>","DOI":"10.3390\/cryptography1030023","type":"journal-article","created":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T12:26:37Z","timestamp":1512995197000},"page":"23","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["FPGA Implementation of a Cryptographically-Secure PUF Based on Learning Parity with Noise"],"prefix":"10.3390","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6306-8019","authenticated-orcid":false,"given":"Chenglu","family":"Jin","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Connecticut, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles","family":"Herder","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phuong","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Connecticut, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Fuller","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinivas","family":"Devadas","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marten","family":"Van Dijk","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Connecticut, Storrs, CT 06269, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,12,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2026","DOI":"10.1126\/science.1074376","article-title":"Physical one-way functions","volume":"297","author":"Pappu","year":"2002","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gassend, B., Clarke, D., van Dijk, M., and Devadas, S. (2002, January 18\u201322). Silicon physical random functions. Proceedings of the 9th ACM Conference on Computer and Communications Security, Washington, DC, USA.","DOI":"10.1145\/586110.586132"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Yin, C.E.D., and Qu, G. (2010, January 13\u201314). LISA: Maximizing RO PUF\u2019s secret extraction. Proceedings of the 2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), Anaheim, CA, USA.","DOI":"10.1109\/HST.2010.5513105"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Maiti, A., Casarona, J., McHale, L., and Schaumont, P. (2010, January 13\u201314). A large scale characterization of RO-PUF. Proceedings of the 2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), Anaheim, CA, USA.","DOI":"10.1109\/HST.2010.5513108"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kumar, S., Guajardo, J., Maes, R., Schrijen, G.J., and Tuyls, P. (2008, January 9). The butterfly PUF protecting IP on every FPGA. Proceedings of the IEEE International Workshop on Hardware-Oriented Security and Trust, Anaheim, CA, USA.","DOI":"10.1109\/HST.2008.4559053"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Tuyls, P., Schrijen, G.J., \u0160kori\u0107, B., van Geloven, J., Verhaegh, N., and Wolters, R. (2006, January 10\u201313). Read-proof hardware from protective coatings. Proceedings of the 8th International Conference on Cryptographic Hardware and Embedded Systems, Yokohama, Japan.","DOI":"10.1007\/11894063_29"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"R\u00fchrmair, U., Sehnke, F., S\u00f6lter, J., Dror, G., Devadas, S., and Schmidhuber, J. (2010, January 4\u20138). Modeling attacks on physical unclonable functions. Proceedings of the 17th ACM Conference on Computer and Communications Security, Chicago, IL, USA.","DOI":"10.1145\/1866307.1866335"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1109\/TIFS.2013.2279798","article-title":"PUF modeling attacks on simulated and silicon data","volume":"8","author":"Sehnke","year":"2013","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"R\u00fchrmair, U., Xu, X., S\u00f6lter, J., Mahmoud, A., Majzoobi, M., Koushanfar, F., and Burleson, W.P. (2014, January 23\u201326). Efficient Power and Timing Side Channels for Physical Unclonable Functions. Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded Systems, Busan, South Korea.","DOI":"10.1007\/978-3-662-44709-3_26"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.1109\/TCSI.2013.2290845","article-title":"Fault Injection Modeling Attacks on 65 nm Arbiter and RO Sum PUFs via Environmental Changes","volume":"61-I","author":"Delvaux","year":"2014","journal-title":"IEEE Trans. Circuits Syst."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Nguyen, P.H., Sahoo, D.P., Chakraborty, R.S., and Mukhopadhyay, D. (2015, January 9\u201313). Efficient Attacks on Robust Ring Oscillator PUF with Enhanced Challenge-Response Set. Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France.","DOI":"10.7873\/DATE.2015.0699"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Armknecht, F., Maes, R., Sadeghi, A.R., Standaert, F.X., and Wachsmann, C. (2011, January 22\u201325). A Formal Foundation for the Security Features of Physical Functions. Proceedings of the 2011 IEEE Symposium on Security and Privacy (SP), Berkeley, CA, USA.","DOI":"10.1109\/SP.2011.10"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Reyzin, L., and Smith, A. (2004, January 2\u20136). Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland.","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Simoens, K., Tuyls, P., and Preneel, B. (2009, January 17\u201320). Privacy Weaknesses in Biometric Sketches. Proceedings of the 2009 30th IEEE Symposium on Security and Privacy, Berkeley, CA, USA.","DOI":"10.1109\/SP.2009.24"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Boyen, X. (2004, January 25\u201329). Reusable Cryptographic Fuzzy Extractors. Proceedings of the 11th ACM Conference on Computer and Communications Security, Washington, DC, USA.","DOI":"10.1145\/1030083.1030096"},{"key":"ref_16","unstructured":"Blanton, M., and Aliasgari, M. (2011, January 18\u201321). On the (non-)reusability of fuzzy sketches and extractors and security in the computational setting. Proceedings of the International Conference on Security and Cryptography (SECRYPT), Seville, Spain."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1433","DOI":"10.1109\/TIFS.2013.2272786","article-title":"Analysis of reusability of secure sketches and fuzzy extractors","volume":"8","author":"Blanton","year":"2013","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_18","unstructured":"Fuller, B., Meng, X., and Reyzin, L. (2013, January 1\u20135). Computational Fuzzy Extractors. Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Canetti, R., Fuller, B., Paneth, O., Reyzin, L., and Smith, A. (2016, January 8\u201312). Reusable Fuzzy Extractors for Low-entropy Distributions. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria.","DOI":"10.1007\/978-3-662-49890-3_5"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/TDSC.2016.2536609","article-title":"Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions","volume":"14","author":"Herder","year":"2017","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant learning, the parity problem, and the statistical query model","volume":"50","author":"Blum","year":"2003","journal-title":"J. ACM"},{"key":"ref_22","unstructured":"Xilinx (2017, May 01). Available online: https:\/\/www.xilinx.com\/support\/documentation\/data_sheets\/ds190-Zynq-7000-Overview.pdf."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume":"56","author":"Regev","year":"2009","journal-title":"J. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M.L., Kearns, M.J., and Lipton, R.J. (1993, January 22\u201326). Cryptographic Primitives Based on Hard Learning Problems. Proceedings of the 13th Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-48329-2_24"},{"key":"ref_25","unstructured":"Hopper, N.J., and Blum, M. (2001, January 9\u201313). Secure Human Identification Protocols. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Cash, D., Peikert, C., and Sahai, A. (2009, January 16\u201320). Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. Proceedings of the 29th Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., and Wigderson, A. (2010, January 5\u20138). Public-key cryptography from different assumptions. Proceedings of the Forty-Second ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806715"},{"key":"ref_28","unstructured":"Levieil, \u00c9., and Fouque, P. (2006, January 6\u20138). An Improved LPN Algorithm. Proceedings of the 5th International Conference, Maiori, Italy."},{"key":"ref_29","unstructured":"Arora, S., and Ge, R. (2011, January 4\u20138). New Algorithms for Learning in Presence of Errors. Proceedings of the 38th International Colloquium, Zurich, Switzerland."},{"key":"ref_30","unstructured":"Bernstein, D.J., and Lange, T. (2012, January 2\u20133). Never Trust a Bunny. Proceedings of the 8th International Workshop, RFIDSec 2012, Nijmegen, The Netherlands."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Guo, Q., Johansson, T., and L\u00f6ndahl, C. (2014, January 7\u201311). Solving LPN Using Covering Codes. Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan.","DOI":"10.1007\/978-3-662-45611-8_1"},{"key":"ref_32","unstructured":"Lyubashevsky, V. (2005, January 22\u201324). The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00145-010-9088-4","article-title":"Improved Ring Oscillator PUF: An FPGA-friendly Secure Primitive","volume":"24","author":"Maiti","year":"2011","journal-title":"J. Cryptol."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Sunar, B., Martin, W.J., and Stinson, D.R. (2007). A provably secure true random number generator with built-in tolerance to active attacks. IEEE Trans. Comput., 56.","DOI":"10.1109\/TC.2007.250627"},{"key":"ref_35","unstructured":"Standard, S.H. (2017, May 01). Federal Information Processing Standard Publication 180-2, Available online: https:\/\/csrc.nist.gov\/publications\/fips\/fips180-2\/fips180-2withchangenotice.pdf."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Scholl, S., Stumm, C., and Wehn, N. (2013, January 9\u201312). Hardware implementations of Gaussian elimination over GF (2) for channel decoding algorithms. Proceedings of the Africon 2013, Pointe-Aux-Piments, Mauritius.","DOI":"10.1109\/AFRCON.2013.6757620"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Ganji, F., Tajik, S., F\u00e4\u00dfler, F., and Seifert, J.P. (2016). Strong machine learning attack against PUFs with no mathematical model. Cryptographic Hardware and Embedded Systems\u2014CHES 2016, Proceedings of the 18th International Conference, Santa Barbara, CA, USA, 17\u201319 August 2016, Springer.","DOI":"10.1007\/978-3-662-53140-2_19"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Ganji, F., Tajik, S., and Seifert, J. (2015, January 24\u201326). Why Attackers Win: On the Learnability of XOR Arbiter PUFs. Proceedings of the 8th International Conference, TRUST 2015, Heraklion, Greece.","DOI":"10.1007\/978-3-319-22846-4_2"},{"key":"ref_39","unstructured":"Becker, G.T. (2015, January 24\u201326). The Gap Between Promise and Reality: On the Insecurity of XOR Arbiter PUFs. Proceedings of the 8th International Conference, TRUST 2015, Heraklion, Greece."},{"key":"ref_40","first-page":"1","article-title":"A Combined Optimization-Theoretic and Side-Channel Approach for Attacking Strong Physical Unclonable Functions","volume":"PP","author":"Liu","year":"2017","journal-title":"IEEE Trans. Very Large Scale Integr. Syst."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Tajik, S., Lohrke, H., Ganji, F., Seifert, J.P., and Boit, C. (2015, January 13). Laser Fault Attack on Physically Unclonable Functions. Proceedings of the 12th Workshop on Fault Diagnosis and Tolerance in Cryptography, St. Malo, France.","DOI":"10.1109\/FDTC.2015.19"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Tajik, S., Dietz, E., Frohmann, S., Seifert, J., Nedospasov, D., Helfmeier, C., Boit, C., and Dittrich, H. (2014, January 23\u201326). Physical Characterization of Arbiter PUFs. Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded Systems, Busan, Korea.","DOI":"10.1007\/978-3-662-44709-3_27"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Ganji, F., Kr\u00e4mer, J., Seifert, J., and Tajik, S. (2015, January 12\u201316). Lattice Basis Reduction Attack against Physically Unclonable Functions. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813723"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Gross, H., Mangard, S., and Korak, T. (2017, January 14\u201317). An efficient side-channel protected aes implementation with arbitrary protection order. Proceedings of the Cryptographers\u2019 Track at the RSA Conference 2017, San Francisco, CA, USA.","DOI":"10.1007\/978-3-319-52153-4_6"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Majzoobi, M., Rostami, M., Koushanfar, F., Wallach, D.S., and Devadas, S. (2012, January 24\u201325). Slender PUF Protocol: A Lightweight, Robust, and Secure Authentication by Substring Matching. Proceedings of the 2012 IEEE Symposium on Security and Privacy Workshops (SPW), San Francisco, CA, USA.","DOI":"10.1109\/SPW.2012.30"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1109\/TMSCS.2016.2553027","article-title":"A lockdown technique to prevent machine learning on PUFs for lightweight authentication","volume":"2","author":"Yu","year":"2016","journal-title":"IEEE Trans. Multi-Scale Comput. Syst."},{"key":"ref_47","first-page":"572","article-title":"MXPUF: Secure PUF Design against State-of-the-art Modeling Attacks","volume":"2017","author":"Nguyen","year":"2017","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/1\/3\/23\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:53:21Z","timestamp":1760208801000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/1\/3\/23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,9]]},"references-count":47,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["cryptography1030023"],"URL":"https:\/\/doi.org\/10.3390\/cryptography1030023","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2017,12,9]]}}}