{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T09:28:02Z","timestamp":1674898082565},"reference-count":35,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T00:00:00Z","timestamp":1605571200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,11,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky <jats:italic>et al<\/jats:italic>. (Eurocrypt \u201913) proved a \u201cregularity lemma,\u201d which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the \u201cregularity lemma\u201d of Lyubashevsky <jats:italic>et al<\/jats:italic>. to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions.<\/jats:p>","DOI":"10.1515\/jmc-2020-0076","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T20:54:49Z","timestamp":1606769689000},"page":"87-110","source":"Crossref","is-referenced-by-count":1,"title":["Towards a Ring Analogue of the Leftover Hash Lemma"],"prefix":"10.1515","volume":"15","author":[{"given":"Dana","family":"Dachman-Soled","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America"}]},{"given":"Huijing","family":"Gong","sequence":"additional","affiliation":[{"name":"Department of Computer Science and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America"}]},{"given":"Mukul","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America"}]},{"given":"Aria","family":"Shahverdi","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America"}]}],"member":"374","published-online":{"date-parts":[[2020,11,17]]},"reference":[{"key":"2021081821075206375_j_jmc-2020-0076_ref_001","doi-asserted-by":"crossref","unstructured":"Adi Akavia, Shafi Goldwasser and Vinod Vaikuntanathan, Simultaneous Hardcore Bits and Cryptography against Memory Attacks, in: TCC 2009 (Omer Reingold, ed.), LNCS 5444, pp. 474\u2013495, Springer, Heidelberg, March 2009.","DOI":"10.1007\/978-3-642-00457-5_28"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_002","doi-asserted-by":"crossref","unstructured":"Martin R. Albrecht, Amit Deo and Kenneth G. Paterson, Cold Boot Attacks on Ring and Module LWE Keys Under the NTT, IACR TCHES 2018 (2018), 173\u2013213, https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/7273","DOI":"10.46586\/tches.v2018.i3.173-213"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_003","doi-asserted-by":"crossref","unstructured":"Pauline Bert, Pierre-Alain Fouque, Adeline Roux-Langlois and Mohamed Sabt, Practical Implementation of Ring-SIS\/LWE Based Signature and IBE, in: Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018 (Tanja Lange and Rainer Steinwandt, eds.), pp. 271\u2013291, Springer, Heidelberg, 2018.","DOI":"10.1007\/978-3-319-79063-3_13"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_004","unstructured":"Madalina Bolboceanu, Zvika Brakerski, Renen Perlman and Devika Sharma, Order-LWE and the Hardness of Ring-LWE with Entropic Secrets Cryptology ePrint Archive, Report 2018\/494, 2018, https:\/\/eprint.iacr.org\/2018\/494"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_005","doi-asserted-by":"crossref","unstructured":"Elette Boyle, Gil Segev and Daniel Wichs, Fully Leakage-Resilient Signatures, Journal of Cryptology 26 (2013), 513\u2013558.","DOI":"10.1007\/s00145-012-9136-3"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_006","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz and Vinod Vaikuntanathan, Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage, in: 51st FOCS pp. 501\u2013510, IEEE Computer Society Press, October 2010.","DOI":"10.1109\/FOCS.2010.55"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_007","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev and Damien Stehl\u00e9, Classical hardness of learning with errors, in: 45th ACM STOC (Dan Boneh, Tim Roughgarden and Joan Feigenbaum, eds.), pp. 575\u2013584, ACM Press, June 2013.","DOI":"10.1145\/2488608.2488680"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_008","unstructured":"Dong Pyo Chi, Jeong Woon Choi, Jeong San Kim and Taewan Kim, Lattice Based Cryptography for Beginners Cryptology ePrint Archive, Report 2015\/938, 2015, https:\/\/eprint.iacr.org\/2015\/938"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_009","doi-asserted-by":"crossref","unstructured":"Kai-Min Chung, Daniel Dadush, Feng-Hao Liu and Chris Peikert, On the lattice smoothing parameter problem, in: Computational Complexity (CCC), 2013 IEEE Conference on IEEE, pp. 230\u2013241, 2013.","DOI":"10.1109\/CCC.2013.31"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_010","unstructured":"Dana Dachman-Soled, Huijing Gong, Mukul Kulkarni and Aria Shahverdi, On the Leakage Resilience of Ideal-Lattice Based Public Key Encryption Cryptology ePrint Archive, Report 2017\/1127, 2017, https:\/\/eprint.iacr.org\/2017\/1127"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_011","unstructured":"Dana Dachman-Soled, Huijing Gong, Mukul Kulkarni and Aria Shahverdi, Partial Key Exposure in Ring-LWE-Based Cryptosys-tems: Attacks and Resilience Cryptology ePrint Archive, Report 2018\/1068, 2018, https:\/\/eprint.iacr.org\/2018\/1068"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_012","doi-asserted-by":"crossref","unstructured":"Luc Devroye, Sample-based non-uniform random variate generation, in: Proceedings of the 18th conference on Winter simulation ACM, pp. 260\u2013265, 1986.","DOI":"10.1145\/318242.318443"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_013","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan, Public-Key Encryption Schemes with Auxiliary Inputs, in: TCC 2010 (Daniele Micciancio, ed.), LNCS 5978, pp. 361\u2013381, Springer, Heidelberg, February 2010.","DOI":"10.1007\/978-3-642-11799-2_22"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_014","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Kristiyan Haralambiev, Adriana L\u00f3pez-Alt and Daniel Wichs, Cryptography against Continuous Memory Attacks, in: 51st FOCS pp. 511\u2013520, IEEE Computer Society Press, October 2010.","DOI":"10.1109\/FOCS.2010.56"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_015","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Yael Tauman Kalai and Shachar Lovett, On cryptography with auxiliary input, in: 41st ACM STOC (Michael Mitzenmacher, ed.), pp. 621\u2013630, ACM Press, May\/June 2009.","DOI":"10.1145\/1536414.1536498"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_016","doi-asserted-by":"crossref","unstructured":"Stefan Dziembowski and Krzysztof Pietrzak, Leakage-Resilient Cryptography, in: 49th FOCS pp. 293\u2013302, IEEE Computer Society Press, October 2008.","DOI":"10.1109\/FOCS.2008.56"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_017","doi-asserted-by":"crossref","unstructured":"Wolfgang Ebeling, Lattices and codes Lattices and Codes, Springer, 2013, pp. 1\u201332.","DOI":"10.1007\/978-3-658-00360-9_1"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_018","doi-asserted-by":"crossref","unstructured":"Thomas Espitau, Pierre-Alain Fouque, Benoit Gerard and Mehdi Tibouchi, Side-Channel Attacks on BLISS Lattice-Based Signatures \u2013 Exploiting Branch Tracing Against strongSwan and Electromagnetic Emanations in Microcontrollers Cryptology ePrint Archive, Report 2017\/505, 2017, http:\/\/eprint.iacr.org\/2017\/505","DOI":"10.1145\/3133956.3134028"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_019","doi-asserted-by":"crossref","unstructured":"Craig Gentry, Chris Peikert and Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in: 40th ACM STOC (Richard E. Ladner and Cynthia Dwork, eds.), pp. 197\u2013206, ACM Press, May 2008.","DOI":"10.1145\/1374376.1374407"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_020","unstructured":"Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan, Robustness of the Learning with Errors Assumption, in: ICS 2010 (Andrew Chi-Chih Yao, ed.), pp. 230\u2013240, Tsinghua University Press, January 2010."},{"key":"2021081821075206375_j_jmc-2020-0076_ref_021","doi-asserted-by":"crossref","unstructured":"Loukas Grafakos and Gerald Teschl, On Fourier Transforms of Radial Functions and Distributions, Journal of Fourier Analysis and Applications 19 (2013), 167\u2013179.","DOI":"10.1007\/s00041-012-9242-5"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_022","doi-asserted-by":"crossref","unstructured":"Jonathan Katz and Vinod Vaikuntanathan, Signature Schemes with Bounded Leakage Resilience, in: ASIACRYPT 2009 (Mitsuru Matsui, ed.), LNCS 5912, pp. 703\u2013720, Springer, Heidelberg, December 2009.","DOI":"10.1007\/978-3-642-10366-7_41"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_023","doi-asserted-by":"crossref","unstructured":"Allison B. Lewko, Mark Lewko and Brent Waters, How to leak on key updates, in: 43rd ACM STOC (Lance Fortnow and Salil P. Vadhan, eds.), pp. 725\u2013734, ACM Press, June 2011.","DOI":"10.1145\/1993636.1993732"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_024","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky, Chris Peikert and Oded Regev, On Ideal Lattices and Learning with Errors over Rings, J. ACM 60 (2013), 43:1\u201343:35.","DOI":"10.1145\/2535925"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_025","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky, Chris Peikert and Oded Regev, A Toolkit for Ring-LWE Cryptography, in: EUROCRYPT 2013 (Thomas Johansson and Phong Q. Nguyen, eds.), LNCS 7881, pp. 35\u201354, Springer, Heidelberg, May 2013.","DOI":"10.1007\/978-3-642-38348-9_3"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_026","doi-asserted-by":"crossref","unstructured":"Vadim Lyubashevsky, Chris Peikert and Oded Regev, A Toolkit for Ring-LWE Cryptography Cryptology ePrint Archive, Report 2013\/293, 2013, http:\/\/eprint.iacr.org\/2013\/293","DOI":"10.1007\/978-3-642-38348-9_3"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_027","doi-asserted-by":"crossref","unstructured":"Tal Malkin, Isamu Teranishi, Yevgeniy Vahlis and Moti Yung, Signatures Resilient to Continual Leakage on Memory and Computation, in: TCC 2011 (Yuval Ishai, ed.), LNCS 6597, pp. 89\u2013106, Springer, Heidelberg, March 2011.","DOI":"10.1007\/978-3-642-19571-6_7"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_028","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Eflcient One-Way Functions, Computational Complexity 16 (2007), 365\u2013411.","DOI":"10.1007\/s00037-007-0234-9"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_029","doi-asserted-by":"crossref","unstructured":"Daniele Micciancio and Oded Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM Journal on Computing 37 (2007), 267\u2013302.","DOI":"10.1137\/S0097539705447360"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_030","doi-asserted-by":"crossref","unstructured":"Moni Naor and Gil Segev, Public-Key Cryptosystems Resilient to Key Leakage, SIAM J. Comput. 41 (2012), 772\u2013814.","DOI":"10.1137\/100813464"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_031","doi-asserted-by":"crossref","unstructured":"Krzysztof Pietrzak, A Leakage-Resilient Mode of Operation, in: EUROCRYPT 2009 (Antoine Joux, ed.), LNCS 5479, pp. 462\u2013482, Springer, Heidelberg, April 2009.","DOI":"10.1007\/978-3-642-01001-9_27"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_032","doi-asserted-by":"crossref","unstructured":"Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM) 56 (2009), 34.","DOI":"10.1145\/1568318.1568324"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_033","doi-asserted-by":"crossref","unstructured":"Miruna Rosca, Damien Stehl\u00e9 and Alexandre Wallet, On the Ring-LWE and Polynomial-LWE Problems, in: EUROCRYPT 2018, Part I (Jesper Buus Nielsen and Vincent Rijmen, eds.), LNCS 10820, pp. 146\u2013173, Springer, Heidelberg, April\/May 2018.","DOI":"10.1007\/978-3-319-78381-9_6"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_034","doi-asserted-by":"crossref","unstructured":"Damien Stehl\u00e9 and Ron Steinfeld, Making NTRU as Secure as Worst-Case Problems over Ideal Lattices, in: EUROCRYPT 2011 (Kenneth G. Paterson, ed.), LNCS 6632, pp. 27\u201347, Springer, Heidelberg, May 2011.","DOI":"10.1007\/978-3-642-20465-4_4"},{"key":"2021081821075206375_j_jmc-2020-0076_ref_035","unstructured":"G.N. Watson, A Treatise on the Theory of Bessel Functions Cambridge Mathematical Library, Cambridge University Press, 1995."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p87.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0076\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0076\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T21:20:36Z","timestamp":1629321636000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0076\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,17]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,11,17]]},"published-print":{"date-parts":[[2020,11,17]]}},"alternative-id":["10.1515\/jmc-2020-0076"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0076","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,17]]}}}  <script>parent.window.postMessage('ixistenz.url:https://api.crossref.org/works/10.1515%2FJMC-2020-0076', '*'); </script> <div id='browserdiffcontainer' style='position: fixed; right: 10px; top: 10vh; min-width: 60px;  border: 1px solid white; background: rgb(251, 189, 0);; opacity: 0.9; font-family: helvetica, arial, sans serif;  font-size: 12px; z-index: 20001; padding-bottom: 20px;'><div onclick="toggle('browserdiffcontainerlist'); return false;" style='background: rgb(151, 89, 0);; color: white; '><strong>&nbsp; <span class='glyphicon glyphicon-minus'></span> NODES</strong></div><div id='browserdiffcontainerlist' style='padding-left: 10px; padding-right: 5px; max-height: 50vh; overflow: auto; '><div><a href='#diffid884' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:884', '*');; return false;" style='text-decoration: none; '>Idea </a> <a style='color: white;' href='#diffid884'><sup>3</sup></a></div><div><a href='#diffid119' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:119', '*');; return false;" style='text-decoration: none; '>idea </a> <a style='color: white;' href='#diffid119'><sup>3</sup></a></div><div><a href='#diffid123' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:123', '*');; return false;" style='text-decoration: none; '>INTERN </a> <a style='color: white;' href='#diffid123'><sup>1</sup></a></div></div></div>
<script>
function toggle( divname ) {
  var x = document.getElementById( divname );
  if (x.style.display === 'none') {
    x.style.display = 'block';
  } else {
    x.style.display = 'none';
  }
} </script>