{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T09:14:58Z","timestamp":1770542098006,"version":"3.49.0"},"reference-count":29,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>New proposals for scalable key rank estimation methods have appeared recently, in particular the sampling based approach MCRank. The idea is that one can consistently estimate the key rank by sampling only a small portion of the key space as a \u201cproxy\u201d, leading to both an accurate and scalable approach, at least in comparison with another approach based on histograms. We show that the (earlier) GEEA algorithm is in fact a sampling based algorithm, and provide an in-depth comparison between GEEA (when adapted to produce rank estimates rather than guessing entropy estimates), GM bounds, MCRank and the currently most performant counting based rank estimation as implemented in the Labynkyr library. We find that although MCRank does live up to the promised accuracy and scalability for probability-based distinguishers, it fails to handle cases with unusual distinguisher distributions.<\/jats:p>\n          <jats:p>Furthermore, we put forward a novel proposal for a highly scalable key rank estimation method by introducing the notion of an \u201cattacker budget\u201d. Our proposal is based on the idea that, in particular for very long keys, the exact key rank is less important than the knowledge whether a key is within a certain bound. Thus our \u201cbudget approach\u201d is based on efficiently checking if the result of an attack is such that the attacker's budget suffices for successful enumeration. Our budget approach scales linearly with the key size and thus enables security estimations even for post-quantum key lengths. <\/jats:p>","DOI":"10.62056\/aytxl86bm","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["Key Rank Estimation Methods: Comparisons and Practical Considerations"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9659-8139","authenticated-orcid":false,"given":"Rebecca","family":"Hay","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0524sp257","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Bristol","place":["Bristol, United Kingdom"],"department":["Computer Science"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7502-3184","authenticated-orcid":false,"given":"Elisabeth","family":"Oswald","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05q9m0937","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Klagenfurt","place":["Klagenfurt, Austria"],"department":["Digital Age Research Centre"]},{"id":[{"id":"https:\/\/ror.org\/03angcq70","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Birmingham","place":["Birmingham, United Kingdom"],"department":["Computer Science"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:polanco2019cold","volume-title":"Cold boot attacks on post-quantum schemes","author":"Ricardo Villanueva Polanco","year":"2019"},{"key":"ref2:VeyratCharvillon2012","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-642-35999-6_25","article-title":"An Optimal Key Enumeration Algorithm and Its Application to\n  Side-Channel Attacks","volume":"7707","author":"Nicolas Veyrat-Charvillon","year":"2012"},{"key":"ref3:VeyratCharvillon2013","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-642-38348-9_8","article-title":"Security Evaluations beyond Computing Power","volume":"7881","author":"Nicolas Veyrat-Charvillon","year":"2013"},{"key":"ref4:glowacz2015simpler","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-662-48116-5_6","article-title":"Simpler and More Efficient Rank Estimation for Side-Channel\n  Security Assessment","volume":"9054","author":"Cezary Glowacz","year":"2015"},{"key":"ref5:martin2015counting","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-662-48800-3_13","article-title":"Counting Keys in Parallel After a Side Channel Attack","volume":"9453","author":"Daniel P. Martin","year":"2015"},{"key":"ref6:BernsteinLV15","first-page":"221","article-title":"Tighter, faster, simpler side-channel security evaluations\n  beyond computing power","volume":"2015","author":"Daniel J. Bernstein","year":"2015","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref7:DBLP:journals\/iacr\/Longo0MOSS16","first-page":"609","article-title":"How low can you go? Using side-channel data to enhance\n  brute-force key recovery","author":"Jake Longo","year":"2016","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref8:grosso2018scalable","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-030-15462-2_6","article-title":"Scalable Key Rank Estimation (and Key Enumeration) Algorithm\n  for Large Keys","volume":"11389","author":"Vincent Grosso","year":"2018"},{"key":"ref9:Martin2018TwoSides","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-319-76953-0_21","article-title":"Two Sides of the Same Coin: Counting and Enumerating Keys\n  Post Side-Channel Attacks Revisited","volume":"10808","author":"Daniel P. Martin","year":"2018"},{"key":"ref10:martin2016characterisation","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/978-3-662-53887-6_20","article-title":"Characterisation and Estimation of the Key Rank Distribution\n  in the Context of Side Channel Evaluations","volume":"10031","author":"Daniel P. Martin","year":"2016"},{"key":"ref11:Poussier2016Simple","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-662-53140-2_4","article-title":"Simple Key Enumeration (and Rank Estimation) Using\n  Histograms: An Integrated Approach","volume":"9813","author":"Romain Poussier","year":"2016"},{"key":"ref12:David2019Poly-logarithmic","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/978-3-030-12612-4_17","article-title":"Poly-Logarithmic Side Channel Rank Estimation via\n  Exponential Sampling","volume":"11405","author":"Liron David","year":"2019"},{"key":"ref13:DavidW19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-030-16350-1_10","article-title":"Fast Analytical Rank Estimation","volume":"11421","author":"Liron David","year":"2019"},{"key":"ref14:DavidW22","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s13389-021-00269-4","article-title":"Rank estimation with bounded error via exponential\n  sampling","volume":"12","author":"Liron David","year":"2022","journal-title":"J. Cryptogr. Eng."},{"key":"ref15:zhang2020fast","doi-asserted-by":"publisher","first-page":"26","DOI":"10.13154\/TCHES.V2020.I2.26-48","article-title":"A Fast and Accurate Guessing Entropy Estimation Algorithm\n  for Full-key Recovery","volume":"2020","author":"Ziyue Zhang","year":"2020","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref16:young2023comparing","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-031-25319-5_10","article-title":"Comparing Key Rank Estimation Methods","volume":"13820","author":"Rebecca Young","year":"2022"},{"key":"ref17:camurati2022mcrank","doi-asserted-by":"publisher","first-page":"277","DOI":"10.46586\/TCHES.V2023.I1.277-300","article-title":"MCRank: Monte Carlo Key Rank Estimation for Side-Channel\n  Security Evaluations","volume":"2023","author":"Giovanni Camurati","year":"2023","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref18:labynkyr","volume-title":"Labynkyr","author":"Daniel P. Martin","year":"2016"},{"key":"ref19:choudary2017back","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-319-66787-4_18","article-title":"Back to Massey: Impressively Fast, Scalable and Tight\n  Security Evaluation Tools","volume":"10529","author":"Marios O. Choudary","year":"2017"},{"key":"ref20:massey1994guessing","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1109\/ISIT.1994.394764","article-title":"Guessing and entropy","author":"James L Massey","year":"1994"},{"key":"ref21:cryptoeprint:2018\/614","volume-title":"A Note on Key Rank","author":"Daniel P. Martin","year":"2018"},{"key":"ref22:burkardt2014truncated","volume-title":"The truncated normal distribution","author":"John Burkardt","year":"2014","journal-title":"Department of Scientific Computing Website, Florida State\n  University"},{"key":"ref23:mpmath","volume-title":"mpmath: a Python library for arbitrary-precision\n  floating-point arithmetic (version 1.3.0)","author":"The mpmath development team","year":"2023"},{"key":"ref24:Ye2014BoundedYetSufficient","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-319-16763-3_13","article-title":"Bounded, yet Sufficient? How to Determine Whether Limited\n  Side Channel Information Enables Key Recovery","volume":"8968","author":"Xin Ye","year":"2014"},{"key":"ref25:tukey1977exploratory","article-title":"Exploratory data analysis","author":"John Wilder Tukey","year":"1977","journal-title":"Reading\/Addison-Wesley"},{"key":"ref26:heumann2016introduction","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-11833-3","volume-title":"Introduction to statistics and data analysis","author":"Christian Heumann","year":"2016"},{"key":"ref27:choudary2016score","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-319-49890-4_8","article-title":"Score-Based vs. Probability-Based Enumeration - A\n  Cautionary Note","volume":"10095","author":"Marios O. Choudary","year":"2016"},{"key":"ref28:hogg2005introduction","series-title":"Pearson education international","isbn-type":"print","volume-title":"Introduction to Mathematical Statistics","author":"R.V. Hogg","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780130085078"},{"key":"ref29:kenney1951mathematics","volume-title":"Mathematics of Statistics: Part two","author":"J.F. Kenney","year":"1951"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:35Z","timestamp":1733866115000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":29,"URL":"https:\/\/doi.org\/10.62056\/aytxl86bm","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-96"}}