{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:21:42Z","timestamp":1764980502322,"version":"3.46.0"},"reference-count":25,"publisher":"Walter de Gruyter GmbH","issue":"3","license":[{"start":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T00:00:00Z","timestamp":1504224000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Cryptographic identification protocols enable a prover to prove its identity to a verifier. A subclass of such protocols are shared-secret challenge-response identification protocols in which the prover and the verifier share the same secret and the prover has to respond to a series of challenges from the verifier. When the prover is a human, as opposed to a machine, such protocols are called human identification protocols. To make human identification protocols usable, protocol designers have proposed different techniques in the literature. One such technique is to make the challenges\n                    <jats:italic>sparse<\/jats:italic>\n                    , in the sense that only a subset of the shared secret is used to compute the response to each challenge. Coskun and Herley demonstrated a generic attack on shared-secret challenge-response type identification protocols which use sparse challenges. They showed that if the subset of the secret used is too small, an eavesdropper can learn the secret after observing a small number of challenge-response pairs. Unfortunately, from their results, it is not possible to find the safe number of challenge-response pairs a sparse-challenge protocol can be used for, without actually implementing the attack on the protocol and weeding out unsafe parameter sizes. Such a task can be time-consuming and computationally infeasible if the subset of the secret used is not small enough. In this work, we show an analytical estimate of the number of challenge-response pairs required by an eavesdropper to find the secret through the Coskun and Herley attack. Against this number, we also give an analytical estimate of the time complexity of the attack. Our results will help protocol designers to choose safe parameter sizes for identification protocols that employ sparse challenges.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2015-0059","type":"journal-article","created":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T06:01:01Z","timestamp":1505973661000},"page":"177-194","source":"Crossref","is-referenced-by-count":0,"title":["When are identification protocols with sparse challenges safe? The case of the Coskun and Herley attack"],"prefix":"10.1515","volume":"11","author":[{"given":"Hassan Jameel","family":"Asghar","sequence":"first","affiliation":[{"name":"Data Privacy Team , Data61, CSIRO , 13 Garden Street, Eveleigh, NSW 2015 , Sydney , Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed Ali","family":"Kaafar","sequence":"additional","affiliation":[{"name":"Data Privacy Team , Data61, CSIRO , 13 Garden Street, Eveleigh, NSW 2015 , Sydney , Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"2025120600191288639_j_jmc-2015-0059_ref_001_w2aab3b7b1b1b6b1ab1b7b1Aa","unstructured":"H. J.  Asghar, S.  Li, R.  Steinfeld and J.  Pieprzyk,\nDoes counting still count? Revisiting the security of counting based user authentication protocols against statistical attacks,\n20th Annual Network and Distributed System Security Symposium,\nInternet Society, Geneva (2013), 1\u201318."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_002_w2aab3b7b1b1b6b1ab1b7b2Aa","doi-asserted-by":"crossref","unstructured":"H. J.  Asghar, J.  Pieprzyk and H.  Wang,\nA new human identification protocol and Coppersmith\u2019s baby-step giant-step algorithm,\nProceedings of the 8th International Conference on Applied Cryptography and Network Security,\nSpringer, Berlin (2010), 349\u2013366.","DOI":"10.1007\/978-3-642-13708-2_21"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_003_w2aab3b7b1b1b6b1ab1b7b3Aa","doi-asserted-by":"crossref","unstructured":"H. J.  Asghar, R.  Steinfeld, S.  Li, M. A.  K\u00e2afar and J.  Pieprzyk,\nOn the linearization of human identification protocols: Attacks based on linear algebra, coding theory, and lattices,\nIEEE Trans. Inform. Forensics Secur. 10 (2015), 1643\u20131655.\n10.1109\/TIFS.2015.2421875","DOI":"10.1109\/TIFS.2015.2421875"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_004_w2aab3b7b1b1b6b1ab1b7b4Aa","doi-asserted-by":"crossref","unstructured":"T.  Baign\u00e8res, P.  Junod and S.  Vaudenay,\nHow far can we go beyond linear cryptanalysis?,\nAdvances in Cryptology \u2013 ASIACRYPT 2004,\nLecture Notes in Comput. Sci. 3329,\nSpringer, Berlin (2004), 432\u2013450.","DOI":"10.1007\/978-3-540-30539-2_31"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_005_w2aab3b7b1b1b6b1ab1b7b5Aa","unstructured":"J.  Blocki, M.  Blum, A.  Datta and S.  Vempala,\nHuman computable passwords,\npreprint (2014), http:\/\/arxiv.org\/pdf\/1404.0024.pdf."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_006_w2aab3b7b1b1b6b1ab1b7b6Aa","doi-asserted-by":"crossref","unstructured":"S.  Boucheron, G.  Lugosi and O.  Bousquet,\nConcentration inequalities,\nAdvanced Lectures in Machine Learning,\nLecture Notes in Comput. Sci. 3176,\nSpringer, Berlin (2004), 208\u2013240.","DOI":"10.1007\/978-3-540-28650-9_9"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_007_w2aab3b7b1b1b6b1ab1b7b7Aa","unstructured":"J.  Chauhan, B. Z. H.  Zhao, H. J.  Asghar, J.  Chan and M. A.  Kaafar,\nBehavioCog: An observation resistant authentication scheme,\npreprint (2016), https:\/\/arxiv.org\/abs\/1610.09044."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_008_w2aab3b7b1b1b6b1ab1b7b8Aa","doi-asserted-by":"crossref","unstructured":"B.  Coskun and C.  Herley,\nCan \u201csomething you know\u201d be saved?,\nInternational Conference on Information Security,\nLecture Notes in Comput. Sci. 5222,\nSpringer, Berlin (2008), 421\u2013440.","DOI":"10.1007\/978-3-540-85886-7_29"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_009_w2aab3b7b1b1b6b1ab1b7b9Aa","unstructured":"T. M.  Cover and J. A.  Thomas,\nElements of Information Theory, 2nd ed.,\nWiley-Interscience, Hoboken, 2006."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_010_w2aab3b7b1b1b6b1ab1b7c10Aa","doi-asserted-by":"crossref","unstructured":"G.  de Meulenaer, F.  Gosset, F. X.  Standaert and O.  Pereira,\nOn the energy cost of communication and cryptography in wireless sensor networks,\n2008 IEEE International Conference on Wireless and Mobile Computing, Networking and Communications,\nIEEE Press, Piscataway (2008), 580\u2013585.","DOI":"10.1109\/WiMob.2008.16"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_011_w2aab3b7b1b1b6b1ab1b7c11Aa","doi-asserted-by":"crossref","unstructured":"N. J.  Hopper and M.  Blum,\nSecure human identification protocols,\nAdvances in Cryptology \u2013 ASIACRYPT 2001,\nLecture Notes in Comput. Sci. 2248,\nSpringer, Berlin (2001), 52\u201366.","DOI":"10.1007\/3-540-45682-1_4"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_012_w2aab3b7b1b1b6b1ab1b7c12Aa","unstructured":"F.  Johansson,\nMpmath: A Python library for arbitrary-precision floating-point arithmetic (Version 0.18),\npreprint (2013), http:\/\/mpmath.org\/."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_013_w2aab3b7b1b1b6b1ab1b7c13Aa","doi-asserted-by":"crossref","unstructured":"A.  Juels and S. A.  Weis,\nAuthenticating pervasive devices with human protocols,\nAdvances in Cryptology \u2013 CRYPTO 2005,\nLecture Notes in Comput. Sci. 3621,\nSpringer, Berlin (2005), 293\u2013308.","DOI":"10.1007\/11535218_18"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_014_w2aab3b7b1b1b6b1ab1b7c14Aa","doi-asserted-by":"crossref","unstructured":"M.  Lei, Y.  Xiao, S. V.  Vrbsky and C.-C.  Li,\nVirtual password using random linear functions for on-line services, ATM machines, and pervasive computing,\nComput. Commun. 31 (2008), 4367\u20134375.\n10.1016\/j.comcom.2008.05.005","DOI":"10.1016\/j.comcom.2008.05.005"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_015_w2aab3b7b1b1b6b1ab1b7c15Aa","unstructured":"S.  Li and H.-Y.  Shum,\nSecure human-computer identification (Interface) systems against peeping attacks: SecHCI,\npreprint (2005), http:\/\/eprint.iacr.org\/2005\/268."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_016_w2aab3b7b1b1b6b1ab1b7c16Aa","unstructured":"N.  Linial and D.  Weitz,\nRandom vectors of bounded weight and their linear dependencies,\npreprint (2000), http:\/\/dimacs.rutgers.edu\/~dror\/pubs\/rand_mat.pdf."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_017_w2aab3b7b1b1b6b1ab1b7c17Aa","doi-asserted-by":"crossref","unstructured":"T.  Matsumoto and H.  Imai,\nHuman identification through insecure channel,\nAdvances in Cryptology,\nLecture Notes in Comput. Sci. 547,\nSpringer, Berlin (1991), 409\u2013421.","DOI":"10.1007\/3-540-46416-6_35"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_018_w2aab3b7b1b1b6b1ab1b7c18Aa","unstructured":"S.  Ross,\nA First Course in Probability,\nMacmillan Publishing, New York, 1976."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_019_w2aab3b7b1b1b6b1ab1b7c19Aa","unstructured":"B.  Schoenmakers,\nLecture notes cryptographic protocols. Version 1.1,\npreprint (2015), http:\/\/www.win.tue.nl\/~berry\/2WC13\/LectureNotes.pdf,"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_020_w2aab3b7b1b1b6b1ab1b7c20Aa","unstructured":"L.  Sobrado and J.-C.  Birget,\nGraphical Passwords,\nRutgers Scholar 4 (2002)."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_021_w2aab3b7b1b1b6b1ab1b7c21Aa","doi-asserted-by":"crossref","unstructured":"D.  Weinshall,\nCognitive authentication schemes safe against spyware (short paper),\nIEEE Symposium on Security and Privacy,\nIEEE Computer Society, Piscataway (2006), 295\u2013300.","DOI":"10.1109\/SP.2006.10"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_022_w2aab3b7b1b1b6b1ab1b7c22Aa","doi-asserted-by":"crossref","unstructured":"S.  Wiedenbeck, J.  Waters, L.  Sobrado and J.-C.  Birget,\nDesign and evaluation of a shoulder-surfing resistant graphical password scheme,\nProceedings of the Working Conference on Advanced Visual Interfaces,\nACM, New York (2006), 177\u2013184.","DOI":"10.1145\/1133265.1133303"},{"key":"2025120600191288639_j_jmc-2015-0059_ref_023_w2aab3b7b1b1b6b1ab1b7c23Aa","unstructured":"R. L.  Wolpert,\nMarkov, Chebychev and Hoeffding Inequalities,\nlecture notes (2009), https:\/\/stat.duke.edu\/courses\/Spring09\/sta205\/lec\/hoef.pdf."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_024_w2aab3b7b1b1b6b1ab1b7c24Aa","unstructured":"Q.  Yan, J.  Han, Y.  Li and R. H.  Deng,\nOn limitations of designing leakage-resilient password systems: Attacks, principals and usability,\n19th Annual Network and Distributed System Security Symposium,\nInternet Society, Geneva (2012), 1\u201316."},{"key":"2025120600191288639_j_jmc-2015-0059_ref_025_w2aab3b7b1b1b6b1ab1b7c25Aa","unstructured":"Semtech Corporation,\nLoRa FAQs,\npreprint 2016, http:\/\/www.semtech.com\/wireless-rf\/lora\/LoRa-FAQs.pdf."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2017.11.issue-3\/jmc-2015-0059\/jmc-2015-0059.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0059\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0059\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:19:22Z","timestamp":1764980362000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0059\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,1]]},"references-count":25,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9,21]]},"published-print":{"date-parts":[[2017,9,1]]}},"alternative-id":["10.1515\/jmc-2015-0059"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2015-0059","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2017,9,1]]}}}