{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T04:41:27Z","timestamp":1720500087196},"reference-count":28,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T00:00:00Z","timestamp":1606262400000},"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,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Let <jats:italic>\u03a9<\/jats:italic> be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational <jats:italic>\u03a9<\/jats:italic>-algebras in arbitrary varieties of <jats:italic>\u03a9<\/jats:italic>-algebras. A family (<jats:italic>H<jats:sub>d<\/jats:sub>\n                  <\/jats:italic> | <jats:italic>d<\/jats:italic> \u2208 <jats:italic>D<\/jats:italic>) of computational <jats:italic>\u03a9<\/jats:italic>-algebras (where <jats:italic>D<\/jats:italic> \u2286 {0, 1}<jats:sup>*<\/jats:sup>) is called polynomially bounded (resp., having exponential size) if there exists a polynomial <jats:italic>\u03b7<\/jats:italic> such that for all <jats:italic>d<\/jats:italic> \u2208 <jats:italic>D<\/jats:italic>, the length of any representation of every <jats:italic>h<\/jats:italic> \u2208 <jats:italic>H<jats:sub>d<\/jats:sub>\n                  <\/jats:italic> is at most <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2020-0014_eq_001.png\" \/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mrow>\n                              <m:mi>\u03b7<\/m:mi>\n                              <m:mo stretchy=\"false\">(<\/m:mo>\n                              <m:mo>|<\/m:mo>\n                              <m:mi>d<\/m:mi>\n                              <m:mo>|<\/m:mo>\n                              <m:mo stretchy=\"false\">)<\/m:mo>\n                              <m:mrow>\n                                 <m:mo>(<\/m:mo>\n                                 <m:mrow>\n                                    <m:mtext>\u2009resp<\/m:mtext>\n                                    <m:mtext>.,\u2009<\/m:mtext>\n                                    <m:mrow>\n                                       <m:mo>|<\/m:mo>\n                                       <m:mrow>\n                                          <m:msub>\n                                             <m:mi>H<\/m:mi>\n                                             <m:mi>d<\/m:mi>\n                                          <\/m:msub>\n                                       <\/m:mrow>\n                                       <m:mo>|<\/m:mo>\n                                    <\/m:mrow>\n                                    <m:mo>\u2264<\/m:mo>\n                                    <m:msup>\n                                       <m:mn>2<\/m:mn>\n                                       <m:mrow>\n                                          <m:mi>\u03b7<\/m:mi>\n                                          <m:mo stretchy=\"false\">(<\/m:mo>\n                                          <m:mo>|<\/m:mo>\n                                          <m:mi>d<\/m:mi>\n                                          <m:mo>|<\/m:mo>\n                                          <m:mo stretchy=\"false\">)<\/m:mo>\n                                       <\/m:mrow>\n                                    <\/m:msup>\n                                 <\/m:mrow>\n                                 <m:mo>)<\/m:mo>\n                              <\/m:mrow>\n                              <m:mo>.<\/m:mo>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>$\\eta (|d|)\\left( \\text{ resp}\\text{., }\\left| {{H}_{d}} \\right|\\le {{2}^{\\eta (|d|)}} \\right).$<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> First, we prove the following trichotomy: (i) if <jats:italic>\u03a9<\/jats:italic> consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family; (ii) if <jats:italic>\u03a9<\/jats:italic> = <jats:italic>\u03a9<\/jats:italic>\n                  <jats:sub>0<\/jats:sub> \u222a {<jats:italic>\u03c9<\/jats:italic>}, where <jats:italic>\u03a9<\/jats:italic>\n                  <jats:sub>0<\/jats:sub> consists of nullary operation symbols and the arity of <jats:italic>\u03c9<\/jats:italic> is 1, then there exist an exponential-size pseudo-free family and a polynomially bounded weakly pseudo-free family; (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families implies the existence of collision-resistant families of hash functions. In this trichotomy, (weak) pseudo-freeness is meant in the variety of all <jats:italic>\u03a9<\/jats:italic>-algebras. Second, assuming the existence of collision-resistant families of hash functions, we construct a polynomially bounded weakly pseudo-free family and an exponential-size pseudo-free family in the variety of all <jats:italic>m<\/jats:italic>-ary groupoids, where <jats:italic>m<\/jats:italic> is an arbitrary positive integer.<\/jats:p>","DOI":"10.1515\/jmc-2020-0014","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T20:54:46Z","timestamp":1606769686000},"page":"197-222","source":"Crossref","is-referenced-by-count":2,"title":["Pseudo-free families of computational universal algebras"],"prefix":"10.1515","volume":"15","author":[{"given":"Mikhail","family":"Anokhin","sequence":"first","affiliation":[{"name":"Information Security Institute, Lomonosov University , Michurinsky prosp. 1 , Moscow , Russia"}]}],"member":"374","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"key":"2021081821075354548_j_jmc-2020-0014_ref_001","doi-asserted-by":"crossref","unstructured":"M. Anokhin, Constructing a pseudo-free family of finite computational groups under the general integer factoring intractability assumption, Groups Complex. Cryptol. 5 (2013), 53\u201374, erratum: Groups Complex. Cryptol. 11 (2019), 133\u2013134.","DOI":"10.1515\/gcc-2019-2009"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_002","doi-asserted-by":"crossref","unstructured":"M. Anokhin, Pseudo-free families of finite computational elementary abelian p-groups, Groups Complex. Cryptol. 9 (2017), 1\u201318.","DOI":"10.1515\/gcc-2017-0001"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_003","doi-asserted-by":"crossref","unstructured":"M. Anokhin, A certain family of subgroups of \n\u2124n\u22c6\n$\\mathbb{Z}_{n}^{\\star }$ is weakly pseudo-free under the general integer factoring intractability assumption, Groups Complex. Cryptol. 10 (2018), 99\u2013110.","DOI":"10.1515\/gcc-2018-0007"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_004","doi-asserted-by":"crossref","unstructured":"V. A. Artamonov, A. A. Klyachko, V. M. Sidelnikov and V. V. Yashchenko, Algebraic aspects of key generation systems, in: Error Control, Cryptology, and Speech Compression (ECCSP 1993), Lecture Notes in Comput. Sci. 829, pp. 1\u20135, Springer, 1994.","DOI":"10.1007\/3-540-58265-7_1"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_005","doi-asserted-by":"crossref","unstructured":"V. A. Artamonov and V. V. Yashchenko, Multibasic algebras in public key distribution systems (Russian), Uspekhi Mat. Nauk 49 (1994), 149\u2013150, English translation: Russian Math. Surveys, 49 (1994), 145\u2013146.","DOI":"10.1070\/RM1994v049n04ABEH002392"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_006","doi-asserted-by":"crossref","unstructured":"D. Boneh and R. J. Lipton, Algorithms for black-box fields and their application to cryptography, in: Advances in Cryptology\u2014CRYPTO\u201996, Lecture Notes in Comput. Sci. 1109, pp. 283\u2013297, Springer, 1996.","DOI":"10.1007\/3-540-68697-5_22"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_007","unstructured":"S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, the Millennium ed, available at http:\/\/www.math.uwaterloo.ca\/~snburris\/htdocs\/ualg.html 2012."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_008","unstructured":"R. Canetti and V. Vaikuntanathan, Obfuscating branching programs using black-box pseudo-free groups, Cryptology ePrint Archive http:\/\/eprint.iacr.org\/ Report 2013\/500, 2013."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_009","doi-asserted-by":"crossref","unstructured":"D. Catalano, D. Fiore and B. Warinschi, Adaptive pseudo-free groups and applications, in: Advances in Cryptology\u2014EUROCRYPT 2011, Lecture Notes in Comput. Sci. 6632, pp. 207\u2013223, Springer, 2011.","DOI":"10.1007\/978-3-642-20465-4_13"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_010","unstructured":"P. M. Cohn, Universal Algebra,Mathematics and Its Applications 6, D. Reidel Publishing Company, Dordrecht\u2013Boston\u2013London, 1981."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_011","unstructured":"M. Fukumitsu, Pseudo-free groups and cryptographic assumptions, Ph.D. thesis, Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University, January 2014."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_012","doi-asserted-by":"crossref","unstructured":"M. Fukumitsu, S. Hasegawa, S. Isobe, E. Koizumi and H. Shizuya, Toward separating the strong adaptive pseudo-freeness from the strong RSA assumption, in: Information Security and Privacy (ACISP 2013), Lecture Notes in Comput. Sci. 7959, pp. 72\u201387, Springer, 2013.","DOI":"10.1007\/978-3-642-39059-3_6"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_013","doi-asserted-by":"crossref","unstructured":"M. Fukumitsu, S. Hasegawa, S. Isobe and H. Shizuya, On the impossibility of proving security of strong-RSA signatures via the RSA assumption, in: Information Security and Privacy (ACISP 2014), Lecture Notes in Comput. Sci. 8544, pp. 290\u2013305, Springer, 2014.","DOI":"10.1007\/978-3-319-08344-5_19"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_014","doi-asserted-by":"crossref","unstructured":"M. Fukumitsu, S. Hasegawa, S. Isobe and H. Shizuya, The RSA group is adaptive pseudo-free under the RSA assumption, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Cryptography and Information Security E97.A (2014), 200\u2013214.","DOI":"10.1587\/transfun.E97.A.200"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_015","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Foundations of Cryptography. Volume 1: Basic Tools, Cambridge University Press, 2001.","DOI":"10.1017\/CBO9780511546891"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_016","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Foundations of Cryptography. Volume 2: Basic Applications, Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511721656"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_017","doi-asserted-by":"crossref","unstructured":"S. Hasegawa, S. Isobe, H. Shizuya and K. Tashiro, On the pseudo-freeness and the CDH assumption, Int. J. Inf. Secur. 8 (2009), 347\u2013355.","DOI":"10.1007\/s10207-009-0087-0"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_018","unstructured":"T. Hirano and K. Tanaka, Variations on pseudo-free groups, Tokyo Institute of Technology, Department of Mathematical and Computing Sciences, Research Reports on Mathematical and Computing Sciences, Series C: Computer Science, no. C-239, January 2007."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_019","unstructured":"S. R. Hohenberger, The cryptographic impact of groups with infeasible inversion, Master\u2019s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 2003."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_020","doi-asserted-by":"crossref","unstructured":"M. P. Jhanwar and R. Barua, Sampling from signed quadratic residues: RSA group is pseudofree, in: Progress in Cryptology\u2014 INDOCRYPT 2009, Lecture Notes in Comput. Sci. 5922, pp. 233\u2013247, Springer, 2009.","DOI":"10.1007\/978-3-642-10628-6_16"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_021","doi-asserted-by":"crossref","unstructured":"M. Luby, Pseudorandomness and Cryptographic Applications, Princeton Computer Science Notes, Princeton University Press, Princeton, 1996.","DOI":"10.1515\/9780691206844"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_022","doi-asserted-by":"crossref","unstructured":"D. Micciancio, The RSA group is pseudo-free, J. Cryptology 23 (2010), 169\u2013186.","DOI":"10.1007\/s00145-009-9042-5"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_023","unstructured":"J. Partala, Key agreement based on homomorphisms of algebraic structures, Cryptology ePrint Archive (http:\/\/eprint.iacr.org\/), Report 2011\/203, 2011."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_024","unstructured":"J. Partala, Algebraic methods for cryptographic key exchange, Ph.D. thesis, Department of Computer Science and Engineering, Faculty of Information Technology and Electrical Engineering, University of Oulu, March 2015."},{"key":"2021081821075354548_j_jmc-2020-0014_ref_025","doi-asserted-by":"crossref","unstructured":"J. Partala, Algebraic generalization of Diffi;e\u2013Hellman key exchange, J. Math. Cryptol. 12 (2018), 1\u201321.","DOI":"10.1515\/jmc-2017-0015"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_026","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, On the notion of pseudo-free groups, in: Theory of Cryptography (TCC 2004), Lecture Notes in Comput. Sci. 2951, pp. 505\u2013521, Springer, 2004.","DOI":"10.1007\/978-3-540-24638-1_28"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_027","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, On the notion of pseudo-free groups, available at https:\/\/people.csail.mit.edu\/rivest\/pubs\/Riv04e.slides.pdf https:\/\/people.csail.mit.edu\/rivest\/pubs\/Riv04e.slides.ppt and http:\/\/people.csail.mit.edu\/rivest\/Rivest-TCC04-PseudoFreeGroups.ppt February 2004, Presentation of [26].","DOI":"10.1007\/978-3-540-24638-1_28"},{"key":"2021081821075354548_j_jmc-2020-0014_ref_028","doi-asserted-by":"crossref","unstructured":"W. Wechler, Universal Algebra for Computer Scientists, EATCS Monographs on Theoretical Computer Science 25, Springer, Berlin et al., 1992.","DOI":"10.1007\/978-3-642-76771-5"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p197.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0014\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0014\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,18]],"date-time":"2021-08-18T21:26:42Z","timestamp":1629322002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2020-0014\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,25]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,11,17]]},"published-print":{"date-parts":[[2020,11,17]]}},"alternative-id":["10.1515\/jmc-2020-0014"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0014","relation":{},"ISSN":["1862-2984"],"issn-type":[{"value":"1862-2984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,25]]}}}  <script>parent.window.postMessage('ixistenz.url:https://api.crossref.org/works/10.1515%2FJMC-2020-0014', '*'); </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='#diffid878' style='color: white;' onClick="parent.window.postMessage('ixistenz.opendiff:878', '*');; return false;" style='text-decoration: none; '>Note </a> <a style='color: white;' href='#diffid878'><sup>8</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>