{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:23:04Z","timestamp":1766269384425,"version":"3.46.0"},"reference-count":47,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This paper introduces new\n                    <jats:italic>\n                      p\n                      <jats:sup>r<\/jats:sup>\n                      q\n                    <\/jats:italic>\n                    -based one-way functions and companion signature schemes. The new signature schemes are interesting because they\n                    <jats:italic>do not<\/jats:italic>\n                    belong to the two common design blueprints, which are the inversion of a trapdoor permutation and the Fiat\u2013Shamir transform. In the basic signature scheme, the signer generates multiple RSA-like moduli\n                    <jats:italic>\n                      n\n                      <jats:sub>i<\/jats:sub>\n                    <\/jats:italic>\n                    =\n                    <jats:italic>\n                      p\n                      <jats:sub>i<\/jats:sub>\n                    <\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    <jats:italic>\n                      q\n                      <jats:sub>i<\/jats:sub>\n                    <\/jats:italic>\n                    and keeps their factors secret. The signature is a bounded-size prime whose Jacobi symbols with respect to the\n                    <jats:italic>\n                      n\n                      <jats:sub>i<\/jats:sub>\n                    <\/jats:italic>\n                    \u2019s match the message digest. The generalized signature schemes replace the Jacobi symbol with higher-power residue symbols. Given of their very unique design, the proposed signature schemes seem to be overlooked \u201cmissing species\u201d in the corpus of known signature algorithms.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2019-0035","type":"journal-article","created":{"date-parts":[[2019,11,9]],"date-time":"2019-11-09T04:04:16Z","timestamp":1573272256000},"page":"224-235","source":"Crossref","is-referenced-by-count":3,"title":["New number-theoretic cryptographic primitives"],"prefix":"10.1515","volume":"14","author":[{"given":"\u00c9ric","family":"Brier","sequence":"first","affiliation":[{"name":"Ingenico , Valence , France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Houda","family":"Ferradi","sequence":"additional","affiliation":[{"name":"NTT Secure Platform Laboratories , Tokyo , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Joye","sequence":"additional","affiliation":[{"name":"OneSpan , Brussels , Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Naccache","sequence":"additional","affiliation":[{"name":"\u00c9cole normale sup\u00e9rieure , Paris , France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,8,1]]},"reference":[{"key":"2025120600172419910_j_jmc-2019-0035_ref_001_w2aab3b7d195b1b6b1ab2b1b1Aa","unstructured":"E. Bach and J. Shallit, Algorithmic Number Theory. Vol. 1: Efficient Algorithms, MIT Press, Cambridge, 1996."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_002_w2aab3b7d195b1b6b1ab2b1b2Aa","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, ACM Conference on Computer and Communications Security, ACM Press, New York (1993), 62\u201373.","DOI":"10.1145\/168588.168596"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_003_w2aab3b7d195b1b6b1ab2b1b3Aa","doi-asserted-by":"crossref","unstructured":"D. Boneh, G. Durfee and N. Howgrave-Graham, Factoring N = prq for large r, Advances in Cryptology\u2014CRYPTO \u201999, Lecture Notes in Comput. Sci. 1666, Springer, Berlin (1999), 326\u2013337.","DOI":"10.1007\/3-540-48405-1_21"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_004_w2aab3b7d195b1b6b1ab2b1b4Aa","doi-asserted-by":"crossref","unstructured":"P. C. Caranay and R. Scheidler, An efficient seventh power residue symbol algorithm, Int. J. Number Theory 6 (2010), no. 8, 1831\u20131853.","DOI":"10.1142\/S1793042110003770"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_005_w2aab3b7d195b1b6b1ab2b1b5Aa","doi-asserted-by":"crossref","unstructured":"H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts in Math. 138, Springer, Berlin, 1993.","DOI":"10.1007\/978-3-662-02945-9"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_006_w2aab3b7d195b1b6b1ab2b1b6Aa","doi-asserted-by":"crossref","unstructured":"I. B. Damg\u00e5rd, On the randomness of Legendre and Jacobi sequences, Advances in Cryptology\u2014CRYPTO\u201988, Lecture Notes in Comput. Sci. 403, Springer, Berlin (1990), 163\u2013172.","DOI":"10.1007\/0-387-34799-2_13"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_007_w2aab3b7d195b1b6b1ab2b1b7Aa","doi-asserted-by":"crossref","unstructured":"I. B. Damg\u00e5rd and G. S. Frandsen, Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers, J. Symbolic Comput. 39 (2005), no. 6, 643\u2013652.","DOI":"10.1016\/j.jsc.2004.02.006"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_008_w2aab3b7d195b1b6b1ab2b1b8Aa","doi-asserted-by":"crossref","unstructured":"H. Davenport, On the distribution of quadratic residues (mod p), J. Lond. Math. Soc. 6 (1931), no. 1, 49\u201354.","DOI":"10.1112\/jlms\/s1-6.1.49"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_009_w2aab3b7d195b1b6b1ab2b1b9Aa","doi-asserted-by":"crossref","unstructured":"H. Davenport, On the distribution of quadratic residues (mod p). II, J. Lond. Math. Soc. 8 (1933), no. 1, 46\u201352.","DOI":"10.1112\/jlms\/s1-8.1.46"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_010_w2aab3b7d195b1b6b1ab2b1c10Aa","doi-asserted-by":"crossref","unstructured":"W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644\u2013654.","DOI":"10.1109\/TIT.1976.1055638"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_011_w2aab3b7d195b1b6b1ab2b1c11Aa","doi-asserted-by":"crossref","unstructured":"C. Ding, D. Pei and A. Salomaa, Chinese Remainder Theorem. Applications in Computing, Coding, Cryptography, World Scientific, River Edge, 1996.","DOI":"10.1142\/9789812779380"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_012_w2aab3b7d195b1b6b1ab2b1c12Aa","doi-asserted-by":"crossref","unstructured":"A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology\u2014CRYPTO\u201986, Lecture Notes in Comput. Sci. 263, Springer, Berlin (1987), 186\u2013194.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_013_w2aab3b7d195b1b6b1ab2b1c13Aa","doi-asserted-by":"crossref","unstructured":"A. Fujioka, T. Okamoto and S. Miyaguchi, ESIGN: An efficient digital signature implementation for smart cards, Advances in Cryptology\u2014EUROCRYPT\u201991, Lecture Notes in Comput. Sci. 547, Springer, Berlin (1991), 446\u2013457.","DOI":"10.1007\/3-540-46416-6_38"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_014_w2aab3b7d195b1b6b1ab2b1c14Aa","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Foundations of Cryptography. Basic Tools, Cambridge University, Cambridge, 2001.","DOI":"10.1017\/CBO9780511546891"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_015_w2aab3b7d195b1b6b1ab2b1c15Aa","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali and R. L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. Special issue on cryptography, SIAM J. Comput. 17 1988, no. 2, 281\u2013308.","DOI":"10.1137\/0217017"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_016_w2aab3b7d195b1b6b1ab2b1c16Aa","doi-asserted-by":"crossref","unstructured":"L. Goubin, C. Mauduit and A. S\u00e1rk\u00f6zy, Construction of large families of pseudorandom binary sequences, J. Number Theory 106 (2004), no. 1, 56\u201369.","DOI":"10.1016\/j.jnt.2003.12.002"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_017_w2aab3b7d195b1b6b1ab2b1c17Aa","doi-asserted-by":"crossref","unstructured":"L. Granboulan, How to repair ESIGN, Security in Communication Networks\u2014SCN 2002, Lecture Notes in Comput. Sci. 2576, Springer, Berlin (2003), 234\u2013240.","DOI":"10.1007\/3-540-36413-7_17"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_018_w2aab3b7d195b1b6b1ab2b1c18Aa","doi-asserted-by":"crossref","unstructured":"K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Grad. Texts in Math. 84, Springer, New York, 1990.","DOI":"10.1007\/978-1-4757-2103-4"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_019_w2aab3b7d195b1b6b1ab2b1c19Aa","doi-asserted-by":"crossref","unstructured":"J. Katz, Digital Signatures, Springer, New York, 2010.","DOI":"10.1007\/978-0-387-27712-7"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_020_w2aab3b7d195b1b6b1ab2b1c20Aa","unstructured":"F. Lemmermeyer, The Euclidean algorithm in algebraic number fields, Exp. Math. 13 (1995), no. 5, 385\u2013416."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_021_w2aab3b7d195b1b6b1ab2b1c21Aa","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, Unbelievable security (Matching AES security using public key systems), Advances in Cryptology\u2014ASIACRYPT 2001, Lecture Notes in Comput. Sci. 2248, Springer, Berlin (2001), 67\u201386.","DOI":"10.1007\/3-540-45682-1_5"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_022_w2aab3b7d195b1b6b1ab2b1c22Aa","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra, H. W. Lenstra, Jr. and L. Lov\u00e1sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515\u2013534.","DOI":"10.1007\/BF01457454"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_023_w2aab3b7d195b1b6b1ab2b1c23Aa","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra and E. Verheul, Selecting cryptographic key sizes, J. Cryptology 14 (2001), no. 4, 255\u2013293.","DOI":"10.1007\/s00145-001-0009-4"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_024_w2aab3b7d195b1b6b1ab2b1c24Aa","doi-asserted-by":"crossref","unstructured":"H. W. Lenstra, Jr., Euclid\u2019s algorithm in cyclotomic fields, J. Lond. Math. Soc. (2) 10 (1975), no. 4, 457\u2013465.","DOI":"10.1112\/jlms\/s2-10.4.457"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_025_w2aab3b7d195b1b6b1ab2b1c25Aa","doi-asserted-by":"crossref","unstructured":"H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649\u2013673.","DOI":"10.2307\/1971363"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_026_w2aab3b7d195b1b6b1ab2b1c26Aa","doi-asserted-by":"crossref","unstructured":"H. W. Lenstra, Jr., The number field sieve: An annotated bibliography, The Development of the Number Field Sieve, Lecture Notes in Math. 1554, Springer, Berlin (1993), 1\u20133.","DOI":"10.1007\/BFb0091535"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_027_w2aab3b7d195b1b6b1ab2b1c27Aa","unstructured":"N. Manohar and B. Fisch, Factoring n = p2q, Final project report CS359C, Stanford University, 2017."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_028_w2aab3b7d195b1b6b1ab2b1c28Aa","doi-asserted-by":"crossref","unstructured":"A. May, Secret exponent attacks on RSA-type schemes with moduli N = prq, Public Key Cryptography\u2014PKC 2004, Lecture Notes in Comput. Sci. 2947, Springer, Berlin (2004), 218\u2013230.","DOI":"10.1007\/978-3-540-24632-9_16"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_029_w2aab3b7d195b1b6b1ab2b1c29Aa","unstructured":"A. Menezes, M. Qu, D. Stinson and Y. Wang, Evaluation of security level of cryptography: ESIGN signature scheme, External Evaluation Report ex-1053-2000, CRYPTREC, 2001."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_030_w2aab3b7d195b1b6b1ab2b1c30Aa","unstructured":"T. Okamoto, E. Fujisaki and H. Morita, TSH-ESIGN: Efficient digital signature scheme using trisection size hash, Submission to IEEE P1363a, November 1998. [Online; accessed 7-February-2019]."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_031_w2aab3b7d195b1b6b1ab2b1c31Aa","doi-asserted-by":"crossref","unstructured":"T. Okamoto and A. Shibaishi, A fast signature scheme based on quadratic inequalities, 1985 IEEE Symposium on Security and Privacy, IEEE Press, Piscataway (1985), 123\u2013133.","DOI":"10.1109\/SP.1985.10026"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_032_w2aab3b7d195b1b6b1ab2b1c32Aa","doi-asserted-by":"crossref","unstructured":"T. Okamoto and S. Uchiyama, A new public-key cryptosystem as secure as factoring, Advances in Cryptology\u2014EUROCRYPT\u201998, Lecture Notes in Comput. Sci. 1403, Springer, Berlin (1998), 308\u2013318.","DOI":"10.1007\/BFb0054135"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_033_w2aab3b7d195b1b6b1ab2b1c33Aa","doi-asserted-by":"crossref","unstructured":"R. Peralta, On the distribution of quadratic residues and nonresidues modulo a prime number, Math. Comp. 58 (1992), no. 197, 433\u2013440.","DOI":"10.1090\/S0025-5718-1992-1106978-9"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_034_w2aab3b7d195b1b6b1ab2b1c34Aa","unstructured":"R. Peralta and E. Okamoto, Faster factoring of integers of a special form, IEICE Trans. Fundam. Electron. Comm. Comp. Sci. E79 (1996), no. A4, 489\u2013493."},{"key":"2025120600172419910_j_jmc-2019-0035_ref_035_w2aab3b7d195b1b6b1ab2b1c35Aa","doi-asserted-by":"crossref","unstructured":"R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120\u2013126.","DOI":"10.1145\/359340.359342"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_036_w2aab3b7d195b1b6b1ab2b1c36Aa","doi-asserted-by":"crossref","unstructured":"A. S\u00e1rk\u00f6zy and C. L. Stewart, On pseudorandomness in families of sequences derived from the Legendre symbol, Period. Math. Hungar. 54 (2007), no. 2, 163\u2013173.","DOI":"10.1007\/s-10998-007-2163-9"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_037_w2aab3b7d195b1b6b1ab2b1c37Aa","doi-asserted-by":"crossref","unstructured":"H. Sato, T. Takagi, S. Tezuka and K. Takaragi, Generalized powering functions and their application to digital signatures, Advances in Cryptology\u2014ASIACRYPT 2003, Lecture Notes in Comput. Sci. 2894, Springer, Berlin (2003), 434\u2013451.","DOI":"10.1007\/978-3-540-40061-5_28"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_038_w2aab3b7d195b1b6b1ab2b1c38Aa","doi-asserted-by":"crossref","unstructured":"R. Scheidler and H. C. Williams, A public-key cryptosystem utilizing cyclotomic fields, Des. Codes Cryptogr. 6 (1995), no. 2, 117\u2013131.","DOI":"10.1007\/BF01398010"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_039_w2aab3b7d195b1b6b1ab2b1c39Aa","doi-asserted-by":"crossref","unstructured":"K. Schmidt-Samoa, A new Rabin-type trapdoor permutation equivalent to factoring, Electron. Notes Theor. Comput. Sci. 157 (2006), no. 3, 79\u201394.","DOI":"10.1016\/j.entcs.2005.09.039"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_040_w2aab3b7d195b1b6b1ab2b1c40Aa","doi-asserted-by":"crossref","unstructured":"K. Schmidt-Samoa and T. Takagi, Paillier\u2019s cryptosystem modulo p2q and its applications to trapdoor commitment schemes, Progress in Cryptology\u2014Mycrypt 2005, Lecture Notes in Comput. Sci. 3715, Springer, Berlin (2005), 296\u2013313.","DOI":"10.1007\/11554868_21"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_041_w2aab3b7d195b1b6b1ab2b1c41Aa","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr, Efficient signature generation by smart cards, J. Cryptology 4 (1991), no. 3, 161\u2013174.","DOI":"10.1007\/BF00196725"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_042_w2aab3b7d195b1b6b1ab2b1c42Aa","doi-asserted-by":"crossref","unstructured":"J. Stern, D. Pointcheval, J. Malone-Lee and N. P. Smart, Flaws in applying proof methodologies to signature schemes, Advances in cryptology\u2014CRYPTO 2002, Lecture Notes in Comput. Sci. 2442, Springer, Berlin (2002), 93\u2013110.","DOI":"10.1007\/3-540-45708-9_7"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_043_w2aab3b7d195b1b6b1ab2b1c43Aa","doi-asserted-by":"crossref","unstructured":"T. Takagi, Fast RSA-type cryptosystem modulo pkq., Advances in Cryptology\u2014CRYPTO\u201998, Lecture Notes in Comput. Sci. 1462, Springer, Berlin (1998), 318\u2013326.","DOI":"10.1007\/BFb0055738"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_044_w2aab3b7d195b1b6b1ab2b1c44Aa","doi-asserted-by":"crossref","unstructured":"L. C. Washington, Introduction to Cyclotomic Fields, 2nd ed., Grad. Texts Math. 83, Springer, New York, 1997.","DOI":"10.1007\/978-1-4612-1934-7"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_045_w2aab3b7d195b1b6b1ab2b1c45Aa","doi-asserted-by":"crossref","unstructured":"A. Weilert, Fast computation of the biquadratic residue symbol, J. Number Theory 96 (2002), no. 1, 133\u2013151.","DOI":"10.1016\/S0022-314X(02)92783-6"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_046_w2aab3b7d195b1b6b1ab2b1c46Aa","doi-asserted-by":"crossref","unstructured":"H. C. Williams, An M3 public-key encryption scheme, Advances in Cryptology\u2014CRYPTO\u201985, Lecture Notes in Comput. Sci. 218, Springer, Berlin (1986), 358\u2013368.","DOI":"10.1007\/3-540-39799-X_26"},{"key":"2025120600172419910_j_jmc-2019-0035_ref_047_w2aab3b7d195b1b6b1ab2b1c47Aa","unstructured":"BlueKrypt, Cryptographic key length recommendations, 2018."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p224.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0035\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0035\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:18:06Z","timestamp":1764980286000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0035\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":47,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,8,7]]},"published-print":{"date-parts":[[2020,8,7]]}},"alternative-id":["10.1515\/jmc-2019-0035"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2019-0035","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}