{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:20:45Z","timestamp":1775794845285,"version":"3.50.1"},"reference-count":26,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T00:00:00Z","timestamp":1703808000000},"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,3,5]]},"abstract":"<jats:p>  We revisit the question of what the definition of bit security should be, previously answered by Micciancio-Walter (Eurocrypt 2018) and Watanabe-Yasunaga (Asiacrypt 2021). Our new definition is simple, but (i) captures both search and decision primitives in a single framework like Micciancio-Walter, and (ii) has a firm operational meaning like Watanabe-Yasunaga. It also matches intuitive expectations and can be well-formulated regarding Hellinger distance. To support and justify the new definition, we prove several classic security reductions with respect to our bit security. We also provide pathological examples that indicate the ill-definedness of bit security defined in Micciancio-Walter and Watanabe-Yasunaga. <\/jats:p>","DOI":"10.62056\/an5txol7","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":4,"title":["Bit Security as Cost to Demonstrate Advantage"],"prefix":"10.62056","author":[{"given":"Keewoo","family":"Lee","sequence":"first","affiliation":[{"name":"UC Berkeley","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:FOCS:AGHP90","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1109\/FSCS.1990.89575","article-title":"Simple Constructions of Almost k-Wise Independent Random\n  Variables","volume-title":"31st FOCS","author":"Noga Alon","year":"1990"},{"key":"ref2:KM13","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1515\/GCC-2013-0008","article-title":"Another look at non-uniformity","volume":"5","author":"Neal Koblitz","year":"2013","journal-title":"Groups Complex. Cryptol."},{"key":"ref3:AC:BerLan13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-42045-0_17","article-title":"Non-uniform Cracks in the Concrete: The Power of Free\n  Precomputation","volume-title":"ASIACRYPT\u00a02013, Part\u00a0II","volume":"8270","author":"Daniel J. Bernstein","year":"2013"},{"key":"ref4:STOC:Regev05","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/1060590.1060603","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","volume-title":"37th ACM STOC","author":"Oded Regev","year":"2005"},{"key":"ref5:Pei16","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A Decade of Lattice Cryptography","volume":"10","author":"Chris Peikert","year":"2016","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref6:CHES:PopDucGun14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-662-44709-3_20","article-title":"Enhanced Lattice-Based Signatures on Reconfigurable\n  Hardware","volume-title":"CHES\u00a02014","volume":"8731","author":"Thomas P\u00f6ppelmann","year":"2014"},{"key":"ref7:AC:BLLSS15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-48797-6_1","article-title":"Improved Security Proofs in Lattice-Based Cryptography:\n  Using the R\u00e9nyi Divergence Rather Than the Statistical Distance","volume-title":"ASIACRYPT\u00a02015, Part\u00a0I","volume":"9452","author":"Shi Bai","year":"2015"},{"key":"ref8:C:MicWal17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-319-63715-0_16","article-title":"Gaussian Sampling over the Integers: Efficient, Generic,\n  Constant-Time","volume-title":"CRYPTO\u00a02017, Part\u00a0II","volume":"10402","author":"Daniele Micciancio","year":"2017"},{"key":"ref9:USENIX:ADPS16","first-page":"327","article-title":"Post-quantum Key Exchange - A New Hope","volume-title":"USENIX Security 2016","author":"Erdem Alkim","year":"2016"},{"key":"ref10:STOC:GolLev89","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/73007.73010","article-title":"A Hard-Core Predicate for all One-Way Functions","volume-title":"21st ACM STOC","author":"Oded Goldreich","year":"1989"},{"key":"ref11:HILL99","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","article-title":"A Pseudorandom Generator from any One-way Function","volume":"28","author":"Johan H\u00e5stad","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"ref12:EC:MicWal18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-78381-9_1","article-title":"On the Bit Security of Cryptographic Primitives","volume-title":"EUROCRYPT\u00a02018, Part\u00a0I","volume":"10820","author":"Daniele Micciancio","year":"2018"},{"key":"ref13:AC:WatYas21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-030-92078-4_6","article-title":"Bit Security as Computational Cost for Winning Games with\n  High Probability","volume-title":"ASIACRYPT\u00a02021, Part\u00a0III","volume":"13092","author":"Shun Watanabe","year":"2021"},{"key":"ref14:STOC:GenWic11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1993636.1993651","article-title":"Separating succinct non-interactive arguments from all\n  falsifiable assumptions","volume-title":"43rd ACM STOC","author":"Craig Gentry","year":"2011"},{"key":"ref15:PW","article-title":"Information Theory","author":"Yury Polyanskiy"},{"key":"ref16:C:Naor03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","article-title":"On Cryptographic Assumptions and Challenges (Invited Talk)","volume-title":"CRYPTO\u00a02003","volume":"2729","author":"Moni Naor","year":"2003"},{"key":"ref17:TCC:GolKal16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-662-49096-9_21","article-title":"Cryptographic Assumptions: A Position Paper","volume-title":"TCC\u00a02016-A, Part\u00a0I","volume":"9562","author":"Shafi Goldwasser","year":"2016"},{"key":"ref18:BelRog","article-title":"Introduction to Modern Cryptography","author":"Mihir Bellare","year":"2005"},{"key":"ref19:Rosulek","article-title":"The Joy of Cryptography","author":"Mike Rosulek","year":"2021"},{"key":"ref20:KatLin","isbn-type":"print","article-title":"Introduction to Modern Cryptography, Second Edition","author":"Jonathan Katz","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781466570269"},{"key":"ref21:Goldreich2","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","article-title":"The Foundations of Cryptography - Volume 2: Basic\n  Applications","author":"Oded Goldreich","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0521830842"},{"key":"ref22:FOCS:BDJR97","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1109\/SFCS.1997.646128","article-title":"A Concrete Security Treatment of Symmetric Encryption","volume-title":"38th FOCS","author":"Mihir Bellare","year":"1997"},{"key":"ref23:AC:BerHul19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-030-34618-8_2","article-title":"Decisional Second-Preimage Resistance: When Does SPR Imply\n  PRE?","volume-title":"ASIACRYPT\u00a02019, Part\u00a0III","volume":"11923","author":"Daniel J. Bernstein","year":"2019"},{"key":"ref24:BY02","article-title":"The complexity of massive data set computations","author":"Ziv Bar-Yossef","year":"2002"},{"key":"ref25:Can17","article-title":"A short note on distinguishing discrete distributions","author":"Cl\u00e9ment Canonne","year":"2017"},{"key":"ref26:AC:WatYas23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-981-99-8736-8_12","article-title":"Unified View for Notions of Bit Security","volume-title":"ASIACRYPT\u00a02023, Part\u00a0VI","volume":"14443","author":"Shun Watanabe","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:26Z","timestamp":1733865926000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":26,"URL":"https:\/\/doi.org\/10.62056\/an5txol7","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2023-12-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-1"}}