{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T13:13:57Z","timestamp":1775308437838,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,11,30]],"date-time":"2018-11-30T00:00:00Z","timestamp":1543536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2500"],"award-info":[{"award-number":["N00014-17-1-2500"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1059416"],"award-info":[{"award-number":["CNS-1059416"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"crossref","award":["2016-HJ-2690"],"award-info":[{"award-number":["2016-HJ-2690"]}],"id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Multidisciplinary Research Program of the University Research Initiative","award":["FA9550-14-1-0351"],"award-info":[{"award-number":["FA9550-14-1-0351"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>In this article, we present SHAIP, a secure Hamming distance\u2013based mutual authentication protocol. It allows an unlimited number of authentications by employing an intrinsic Physical Unclonable Function (PUF). PUFs are being increasingly employed for remote authentication of devices. Most of these devices have limited resources. Therefore, the intrinsic PUFs are most suitable for this task as they can be built with little or no modification to the underlying hardware platform. One major drawback of the current authentication schemes is that they expose the PUF response. This makes the intrinsic PUFs, which have a limited number of challenge-response pairs, unusable after a certain number of authentication sessions. Moreover, these schemes are one way in the sense that they only allow one party, the prover, to authenticate herself to the verifier. We propose a symmetric mutual authentication scheme based on secure (privacy-preserving) computation of the Hamming distance between the PUF response from the remote device and reference response stored at the verifier end. This allows both parties to authenticate each other without revealing their respective sets of inputs. We show that our scheme is effective with all state-of-the-art intrinsic PUFs. The proposed scheme is lightweight and does not require any modification to the underlying hardware.<\/jats:p>","DOI":"10.1145\/3274669","type":"journal-article","created":{"date-parts":[[2018,12,13]],"date-time":"2018-12-13T10:45:03Z","timestamp":1544697903000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["SHAIP"],"prefix":"10.1145","volume":"23","author":[{"given":"Siam Umar","family":"Hussain","sequence":"first","affiliation":[{"name":"University of California San Diego, Gilman Drive, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Sadegh","family":"Riazi","sequence":"additional","affiliation":[{"name":"University of California San Diego, Gilman Drive, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farinaz","family":"Koushanfar","sequence":"additional","affiliation":[{"name":"University of California San Diego, Gilman Drive, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Towards Hardware-Intrinsic Security","author":"Armknecht Frederik","unstructured":"Frederik Armknecht , Roel Maes , Ahmad-Reza Sadeghi , Berk Sunar , and Pim Tuyls . 2010. Memory leakage-resilient encryption based on physically unclonable functions . In Towards Hardware-Intrinsic Security . Springer , 135--164. Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Berk Sunar, and Pim Tuyls. 2010. Memory leakage-resilient encryption based on physically unclonable functions. In Towards Hardware-Intrinsic Security. Springer, 135--164."},{"key":"e_1_2_1_2_1","volume-title":"Semi-invasive Attacks: A New Approach to Hardware Security Analysis. Technical Report","author":"Skorobogatov Sergei Petrovich","year":"2005","unstructured":"Sergei Petrovich Skorobogatov . 2005 . Semi-invasive Attacks: A New Approach to Hardware Security Analysis. Technical Report . University of Cambridge . Sergei Petrovich Skorobogatov. 2005. Semi-invasive Attacks: A New Approach to Hardware Security Analysis. Technical Report. University of Cambridge."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"M. Rostami F. Koushanfar and R. Karri. 2014. A primer on hardware security: Threat models metrics and remedies (unpublished). M. Rostami F. Koushanfar and R. Karri. 2014. A primer on hardware security: Threat models metrics and remedies (unpublished).","DOI":"10.1109\/ICCAD.2013.6691207"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833566"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-011-0016-9"},{"key":"e_1_2_1_6_1","volume-title":"Towards Hardware-Intrinsic Security","author":"Sadeghi Ahmad-Reza","unstructured":"Ahmad-Reza Sadeghi , Ivan Visconti , and Christian Wachsmann . 2010. Enhancing RFID security and privacy by physically unclonable functions . In Towards Hardware-Intrinsic Security . Springer . Ahmad-Reza Sadeghi, Ivan Visconti, and Christian Wachsmann. 2010. Enhancing RFID security and privacy by physically unclonable functions. In Towards Hardware-Intrinsic Security. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPW.2012.30"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Conference of the International Association for Cryptologic Research (IACR\u201913)","author":"Moriyama Daisuke","year":"2013","unstructured":"Daisuke Moriyama , Shin\u2019ichiro Matsuo , and Moti Yung . 2013 . PUF-based RFID authentication secure and private under complete memory leakage . In Proceedings of the Conference of the International Association for Cryptologic Research (IACR\u201913) . Daisuke Moriyama, Shin\u2019ichiro Matsuo, and Moti Yung. 2013. PUF-based RFID authentication secure and private under complete memory leakage. In Proceedings of the Conference of the International Association for Cryptologic Research (IACR\u201913)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48324-4_28"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74735-2_5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2014.2320516"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53140-2_21"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32946-3_27"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2016.2536609"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41320-9_11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2914422.2914489"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_22"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42045-0_23"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56617-7_14"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134053"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_13"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"e_1_2_1_25_1","volume-title":"Introduction to Hardware Security and Trust","author":"Ruhrmair Ulrich","year":"2011","unstructured":"Ulrich Ruhrmair , Srinivas Devadas , and Farinaz Koushanfar . 2011. Security based on physical unclonability and disorder . In Introduction to Hardware Security and Trust ( 2011 ). Ulrich Ruhrmair, Srinivas Devadas, and Farinaz Koushanfar. 2011. Security based on physical unclonability and disorder. In Introduction to Hardware Security and Trust (2011)."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the European Solid-State Circuits Conference (ESSCIRC\u201912)","author":"Maes Roel","unstructured":"Roel Maes , Vladimir Rozic , Ingrid Verbauwhede , Patrick Koeberl , Erik Van der Sluis , and Vincent van der Leest. 2012. Experimental evaluation of physically unclonable functions in 65 nm CMOS . In Proceedings of the European Solid-State Circuits Conference (ESSCIRC\u201912) . IEEE. Roel Maes, Vladimir Rozic, Ingrid Verbauwhede, Patrick Koeberl, Erik Van der Sluis, and Vincent van der Leest. 2012. Experimental evaluation of physically unclonable functions in 65 nm CMOS. In Proceedings of the European Solid-State Circuits Conference (ESSCIRC\u201912). IEEE."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22846-4_1"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference (DATE\u201912)","author":"Schrijen Geert-Jan","unstructured":"Geert-Jan Schrijen and Vincent van der Leest. 2012. Comparative analysis of SRAM memories used as PUF primitives . In Proceedings of the Design, Automation and Test in Europe Conference (DATE\u201912) . EDA Consortium. Geert-Jan Schrijen and Vincent van der Leest. 2012. Comparative analysis of SRAM memories used as PUF primitives. In Proceedings of the Design, Automation and Test in Europe Conference (DATE\u201912). EDA Consortium."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2014.6865740"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2013.2282114"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0102-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.39"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337028"},{"key":"e_1_2_1_35_1","volume-title":"Whole: Reducing Data Transfer in Garbled Circuits using Half Gates. Cryptology ePrint Archive.","author":"Zahur S.","year":"2014","unstructured":"S. Zahur , M. Rosulek , and D. Evans . 2014 . Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates. Cryptology ePrint Archive. Retrieved from http:\/\/eprint.iacr.org\/2014\/756. S. Zahur, M. Rosulek, and D. Evans. 2014. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates. Cryptology ePrint Archive. Retrieved from http:\/\/eprint.iacr.org\/2014\/756."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the USENIX Security Symposium (USENIX Security\u201913)","author":"Kreuter B.","year":"2013","unstructured":"B. Kreuter , A. Shelat , B. Mood , and K. R. B. Butler . 2013 . PCF: A portable circuit format for scalable two-party secure computation . In Proceedings of the USENIX Security Symposium (USENIX Security\u201913) . B. Kreuter, A. Shelat, B. Mood, and K. R. B. Butler. 2013. PCF: A portable circuit format for scalable two-party secure computation. In Proceedings of the USENIX Security Symposium (USENIX Security\u201913)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Andrei Z. Broder. 1997. On the resemblance and containment of documents. In The Compression and Complexity of Sequences. 21--29. Andrei Z. Broder. 1997. On the resemblance and containment of documents. In The Compression and Complexity of Sequences. 21--29.","DOI":"10.1109\/SEQUEN.1997.666900"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803400"},{"key":"e_1_2_1_41_1","volume-title":"Bryan","author":"Wadsworth George P.","year":"1960","unstructured":"George P. George P. Wadsworth and Joseph G . Bryan . 1960 . Introduction to Probability and Random Variables. McGraw--Hill, New York . George P. George P. Wadsworth and Joseph G. Bryan. 1960. Introduction to Probability and Random Variables. McGraw--Hill, New York."},{"key":"e_1_2_1_42_1","unstructured":"Shelby J. Haberman. 1976. Discrete Multivariate Analysis: Theory and Practice. Shelby J. Haberman. 1976. Discrete Multivariate Analysis: Theory and Practice."},{"key":"e_1_2_1_43_1","volume-title":"Foundations of Cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2009. Foundations of Cryptography : Volume 2 , Basic Applications. Cambridge University Press . Oded Goldreich. 2009. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_45_1","unstructured":"Clifford Wolf. {n.d.}. Yosys Open SYnthesis Suite. Retrieved from http:\/\/www.clifford.at\/yosys\/. Clifford Wolf. {n.d.}. Yosys Open SYnthesis Suite. Retrieved from http:\/\/www.clifford.at\/yosys\/."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.32"},{"key":"e_1_2_1_47_1","unstructured":"Xiao Wang Alex J. Malozemoff and Jonathan Katz. 2016. EMP-toolkit: Efficient MultiParty computation toolkit. Retrieved from https:\/\/github.com\/emp-toolkit. Xiao Wang Alex J. Malozemoff and Jonathan Katz. 2016. EMP-toolkit: Efficient MultiParty computation toolkit. Retrieved from https:\/\/github.com\/emp-toolkit."},{"key":"e_1_2_1_48_1","volume-title":"Optimal densification for fast and accurate minwise hashing. arXiv preprint arXiv:1703.04664","author":"Shrivastava Anshumali","year":"2017","unstructured":"Anshumali Shrivastava . 2017. Optimal densification for fast and accurate minwise hashing. arXiv preprint arXiv:1703.04664 ( 2017 ). Anshumali Shrivastava. 2017. Optimal densification for fast and accurate minwise hashing. arXiv preprint arXiv:1703.04664 (2017)."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201914)","author":"Shrivastava Anshumali","year":"2014","unstructured":"Anshumali Shrivastava and Ping Li . 2014 . Densifying one permutation hashing via rotation for fast near neighbor search . In Proceedings of the International Conference on Machine Learning (ICML\u201914) . 557--565. Anshumali Shrivastava and Ping Li. 2014. Densifying one permutation hashing via rotation for fast near neighbor search. In Proceedings of the International Conference on Machine Learning (ICML\u201914). 557--565."},{"key":"e_1_2_1_50_1","volume-title":"Sub-linear privacy-preserving search with untrusted server and semi-honest parties. arXiv preprint arXiv:1612.01835","author":"Riazi M. Sadegh","year":"2016","unstructured":"M. Sadegh Riazi , Beidi Chen , Anshumali Shrivastava , Dan Wallach , and Farinaz Koushanfar . 2016. Sub-linear privacy-preserving search with untrusted server and semi-honest parties. arXiv preprint arXiv:1612.01835 ( 2016 ). M. Sadegh Riazi, Beidi Chen, Anshumali Shrivastava, Dan Wallach, and Farinaz Koushanfar. 2016. Sub-linear privacy-preserving search with untrusted server and semi-honest parties. arXiv preprint arXiv:1612.01835 (2016)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818186"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2010.39"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1002\/sec.206"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03168-7_14"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/HST.2016.7495590"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01957-9_7"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274669","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274669","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T12:21:34Z","timestamp":1775305294000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274669"}},"subtitle":["Secure Hamming Distance for Authentication of Intrinsic PUFs"],"short-title":[],"issued":{"date-parts":[[2018,11,30]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3274669"],"URL":"https:\/\/doi.org\/10.1145\/3274669","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,30]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}