{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T11:51:24Z","timestamp":1785412284720,"version":"3.56.0"},"reference-count":41,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T00:00:00Z","timestamp":1744070400000},"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":[[2025,6,2]]},"abstract":"<jats:p>\n                    The notion of indifferentiability was proposed by Maurer et al. to bound the distinguishing advantage of a construction built on a public primitive, from a public random function.  In Indocrypt'10, Mandal et al. have shown that the sum of two independent permutations is indifferentiable from a public random function up to\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msup>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    queries. Later in ACNS'15, Mennink and Preneel identified an analytical flaw of Mandal et al's result and revised the security bound to\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msup>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    . In Eurocrypt'18, Bhattacharya and Nandi have improved their indifferentiable bound to\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:msup>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msup>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    queries, which was again identified as incorrect in the analysis by Gunsing et al. In this paper, we study the indifferentiability of a few other PRF constructions, namely STH and EDM constructions. We will show that neither STH nor STH2 is indifferentiable, which led us to propose a generalized version called gSTH. We have shown that gSTH achieves a tight\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>l<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    -bit security bound, where\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>l<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    denotes the size of the constants in terms of bits used in the construction. While we show that EDM achieves a tight\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    -bit indifferentiable bound with respect to our proposed simulator, single-keyed EDM is not indifferentiable from a public random function. We would like to mention that all the proofs and the attacks have been done in the sequential indifferentiability model.\n                  <\/jats:p>","DOI":"10.62056\/a3n59qxqi","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T17:09:09Z","timestamp":1751908149000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["Sequential Indifferentiability of STH and EDM"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-9761-1192","authenticated-orcid":false,"given":"Nilanjan","family":"Datta","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence (IAI), TCG CREST","place":["Kolkata, India"]},{"id":[{"id":"https:\/\/ror.org\/053rcsq61","id-type":"ROR","asserted-by":"publisher"}],"name":"Academy of Scientific and Innovative Research (AcSIR)","place":["Ghaziabad, India"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2672-7331","authenticated-orcid":false,"given":"Avijit","family":"Dutta","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence (IAI), TCG CREST","place":["Kolkata, India"]},{"id":[{"id":"https:\/\/ror.org\/053rcsq61","id-type":"ROR","asserted-by":"publisher"}],"name":"Academy of Scientific and Innovative Research (AcSIR)","place":["Ghaziabad, India"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2357-0198","authenticated-orcid":false,"given":"Sougata","family":"Mandal","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence (IAI), TCG CREST","place":["Kolkata, India"]},{"id":[{"id":"https:\/\/ror.org\/03kp2qt98","id-type":"ROR","asserted-by":"publisher"}],"name":"Ramakrishna Mission Vivekananda Educational and Research Institute","place":["Belur, India"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8395-4925","authenticated-orcid":false,"given":"Hrithik","family":"Nandi","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05h2r8y34","id-type":"ROR","asserted-by":"publisher"}],"name":"Institute for Advancing Intelligence (IAI), TCG CREST","place":["Kolkata, India"]},{"id":[{"id":"https:\/\/ror.org\/03kp2qt98","id-type":"ROR","asserted-by":"publisher"}],"name":"Ramakrishna Mission Vivekananda Educational and Research Institute","place":["Belur, India"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:ggm","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1109\/SFCS.1984.715949","article-title":"How to Construct Random Functions (Extended Abstract)","author":"Oded Goldreich","year":"1984"},{"key":"ref2:aes","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/10721064_26","article-title":"The Block Cipher Rijndael","volume":"1820","author":"Joan Daemen","year":"1998"},{"key":"ref3:prince","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-34961-4_14","article-title":"PRINCE - A Low-Latency Block Cipher for Pervasive\n  Computing Applications - Extended Abstract","volume":"7658","author":"Julia Borghoff","year":"2012"},{"key":"ref4:present","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-540-74735-2_31","article-title":"PRESENT: An Ultra-Lightweight Block Cipher","volume":"4727","author":"Andrey Bogdanov","year":"2007"},{"key":"ref5:gift","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-319-66787-4_16","article-title":"GIFT: A Small Present - Towards Reaching the Limit of\n  Lightweight Encryption","volume":"10529","author":"Subhadeep Banik","year":"2017"},{"key":"ref6:bellare","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BFB0054132","article-title":"Luby-Rackoff Backwards: Increasing Security by Making Block\n  Ciphers Non-invertible","volume":"1403","author":"Mihir Bellare","year":"1998"},{"key":"ref7:chm","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/11799313_20","article-title":"New Blockcipher Modes of Operation with Beyond the Birthday\n  Bound Security","volume":"4047","author":"Tetsu Iwata","year":"2006"},{"key":"ref8:WegmanC81","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","article-title":"New Hash Functions and Their Use in Authentication and Set\n  Equality","volume":"22","author":"Mark N. Wegman","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"ref9:bettle","doi-asserted-by":"publisher","first-page":"218","DOI":"10.13154\/TCHES.V2018.I2.218-241","article-title":"Beetle Family of Lightweight and Secure Authenticated\n  Encryption Ciphers","volume":"2018","author":"Avik Chakraborti","year":"2018","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref10:dbhts","doi-asserted-by":"publisher","first-page":"36","DOI":"10.13154\/TOSC.V2018.I3.36-92","article-title":"Double-block Hash-then-Sum: A Paradigm for Constructing\n  BBB Secure PRF","volume":"2018","author":"Nilanjan Datta","year":"2018","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref11:dutta-crypto","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/978-3-319-96884-1_21","article-title":"Encrypt or Decrypt? To Make a Single-Key Beyond Birthday\n  Secure Nonce-Based MAC","volume":"10991","author":"Nilanjan Datta","year":"2018"},{"key":"ref12:nandi-prfprp","first-page":"78","article-title":"A Short Proof of the PRP\/PRF Switching Lemma","author":"Donghoon Chang","year":"2008","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref13:hall","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/BFB0055742","article-title":"Building PRFs from PRPs","volume":"1462","author":"Chris Hall","year":"1998"},{"key":"ref14:bi","first-page":"24","volume-title":"A tool for obtaining tighter security analyses of\n  pseudorandom function based constructions, with applications to PRP to\n  PRF conversion","author":"Mihir Bellare","year":"1999","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref15:gg","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/J.DAM.2021.01.029","article-title":"The advantage of truncated permutations","volume":"294","author":"Shoni Gilboa","year":"2021","journal-title":"Discret. Appl. Math."},{"key":"ref16:dai","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-319-63697-9_17","article-title":"Information-Theoretic Indistinguishability via the\n  Chi-Squared Method","volume":"10403","author":"Wei Dai","year":"2017"},{"key":"ref17:dutta-ieee","doi-asserted-by":"publisher","first-page":"6218","DOI":"10.1109\/TIT.2022.3171178","article-title":"Proof of Mirror Theory for \\(\\xi\\)\\({}_{\\mbox{max}}\\) =\n  2","volume":"68","author":"Avijit Dutta","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref18:edm","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-662-53018-4_5","article-title":"EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse\n  Resistant MAC","volume":"9814","author":"Beno\u00eet Cogliati","year":"2016"},{"key":"ref19:mn17","doi-asserted-by":"publisher","first-page":"228","DOI":"10.13154\/TOSC.V2017.I3.228-252","article-title":"Optimal PRFs from Blockcipher Designs","volume":"2017","author":"Bart Mennink","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref20:guo","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1007\/S10623-018-0528-8","article-title":"Beyond-birthday secure domain-preserving PRFs from a single\n  permutation","volume":"87","author":"Chun Guo","year":"2019","journal-title":"Des. Codes Cryptogr."},{"key":"ref21:gm","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-030-56784-2_7","article-title":"The Summation-Truncation Hybrid: Reusing Discarded Bits for\n  Free","volume":"12170","author":"Aldo Gunsing","year":"2020"},{"key":"ref22:maurer","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24638-1_2","article-title":"Indifferentiability, Impossibility Results on Reductions,\n  and Applications to the Random Oracle Methodology","volume":"2951","author":"Ueli M. Maurer","year":"2004"},{"key":"ref23:coron","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/11535218_26","article-title":"Merkle-Damg\u00e5rd Revisited: How to Construct a Hash\n  Function","volume":"3621","author":"Jean-S\u00e9bastien Coron","year":"2005"},{"key":"ref24:RSS11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-642-20465-4_27","article-title":"Careful with Composition: Limitations of the\n  Indifferentiability Framework","volume":"6632","author":"Thomas Ristenpart","year":"2011"},{"key":"ref25:mandal-seq","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-642-28914-9_16","article-title":"On the Public Indifferentiability and Correlation\n  Intractability of the 6-Round Feistel Construction","volume":"7194","author":"Avradip Mandal","year":"2012"},{"key":"ref26:CEJS23","doi-asserted-by":"publisher","first-page":"330","DOI":"10.46586\/TOSC.V2023.I4.330-364","article-title":"On Large Tweaks in Tweakable Even-Mansour with Linear Tweak\n  and Key Mixing","volume":"2023","author":"Beno\u00eet Cogliati","year":"2023","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref27:mandal","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-642-17401-8_6","article-title":"Indifferentiability beyond the Birthday Bound for the Xor of\n  Two Public Random Permutations","volume":"6498","author":"Avradip Mandal","year":"2010"},{"key":"ref28:mp","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/978-3-319-28166-7_30","article-title":"On the XOR of Multiple Random Permutations","volume":"9092","author":"Bart Mennink","year":"2015"},{"key":"ref29:bn","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-319-78381-9_15","article-title":"Full Indifferentiable Security of the Xor of Two or More\n  Random Permutations Using the \\chi 2 Method","volume":"10820","author":"Srimanta Bhattacharya","year":"2018"},{"key":"ref30:lee","doi-asserted-by":"publisher","first-page":"4050","DOI":"10.1109\/TIT.2017.2679757","article-title":"Indifferentiability of the Sum of Random Permutations Toward\n  Optimal Security","volume":"63","author":"Jooyoung Lee","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref31:dodis","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-03317-9_7","article-title":"Indifferentiability of Permutation-Based Compression\n  Functions and Tree-Based Modes of Operation, with Applications to MD6","volume":"5665","author":"Yevgeniy Dodis","year":"2009"},{"key":"ref32:choi","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-030-34578-5_7","article-title":"Indifferentiability of Truncated Random Permutations","volume":"11921","author":"Wonseok Choi","year":"2019"},{"key":"ref33:dodis-sumpip","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-540-78967-3_12","article-title":"A New Mode of Operation for Block Ciphers and\n  Length-Preserving MACs","volume":"4965","author":"Yevgeniy Dodis","year":"2008"},{"key":"ref34:gunsing","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-031-15985-5_8","article-title":"Block-Cipher-Based Tree Hashing","volume":"13510","author":"Aldo Gunsing","year":"2022"},{"key":"ref35:bhaumik","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/978-3-031-38548-3_21","article-title":"Revisiting the Indifferentiability of the Sum of\n  Permutations","volume":"14083","author":"Aldo Gunsing","year":"2023"},{"key":"ref36:CGH98","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/276698.276741","article-title":"The Random Oracle Methodology, Revisited (Preliminary\n  Version)","author":"Ran Canetti","year":"1998"},{"key":"ref37:KR07","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-76900-2_19","article-title":"Known-Key Distinguishers for Some Block Ciphers","volume":"4833","author":"Lars R. Knudsen","year":"2007"},{"key":"ref38:CogliatiS15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/978-3-662-46800-5_23","article-title":"On the Provable Security of the Iterated Even-Mansour Cipher\n  Against Related-Key and Chosen-Key Attacks","volume":"9056","author":"Benoit Cogliati","year":"2015"},{"key":"ref39:CogliatiS16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/978-3-662-52993-5_25","article-title":"Strengthening the Known-Key Security Notion for Block\n  Ciphers","volume":"9783","author":"Beno\u00eet Cogliati","year":"2016"},{"key":"ref40:CPS08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-85174-5_1","article-title":"The Random Oracle Model and the Ideal Cipher Model Are\n  Equivalent","volume":"5157","author":"Jean-S\u00e9bastien Coron","year":"2008"},{"key":"ref41:LS13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/978-3-642-42033-7_23","article-title":"How to Construct an Ideal Cipher from a Small Set of Public\n  Permutations","volume":"8269","author":"Rodolphe Lampe","year":"2013"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T17:10:10Z","timestamp":1751908210000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":41,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/a3n59qxqi","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-04-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-2-72"}}