×
Brier, Éric; Ferradi, Houda; Joye, Marc; Naccache, David

New number-theoretic cryptographic primitives. (English) Zbl 1465.94059

J. Math. Cryptol. 14, 224-235 (2020).
It is known that factoring unbalanced integers, e.g. integers of the form \(n = {p^r}q\), \(p\), \(q\)-primes is easy if \(r\) is large, but for small values of \(r\) the task seems to be as hard as in the general case. Thus, a new family of one-way functions and signature schemes based on this fact is introduced, e.g. for signing a document signer generates multiple moduli \({n_i} = p_i^2{q_i}\) using secret primes \({p_i}\), \({q_i}\). The signature is a bounded-size prime whose Jacobi symbols with respect to the \({n_i}\)s match the message digest.
Reviewer: Jaak Henno (Tallinn)

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11A15 Power residues, reciprocity
11R18 Cyclotomic extensions

Keywords:

\(r\)-th power residue symbol; \(r\)-th order imprint; \(p^rq\) moduli; number theory; one-way functions; digital signatures; cryptographic primitives

Software:

ESIGN
PDF BibTeX XML Cite
\textit{É. Brier} et al., J. Math. Cryptol. 14, 224--235 (2020; Zbl 1465.94059)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] E. Bach and J. Shallit, Algorithmic Number Theory. Vol. 1: Efficient Algorithms, MIT Press, Cambridge, 1996.
[2] 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-73.
[3] D. Boneh, G. Durfee and N. Howgrave-Graham, Factoring N = p^rq for large r, Advances in Cryptology—CRYPTO ’99, Lecture Notes in Comput. Sci. 1666, Springer, Berlin (1999), 326-337. · Zbl 1007.11077
[4] P. C. Caranay and R. Scheidler, An efficient seventh power residue symbol algorithm, Int. J. Number Theory 6 (2010), no. 8, 1831-1853. · Zbl 1242.11079
[5] H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts in Math. 138, Springer, Berlin, 1993.
[6] I. B. Damgård, On the randomness of Legendre and Jacobi sequences, Advances in Cryptology—CRYPTO’88, Lecture Notes in Comput. Sci. 403, Springer, Berlin (1990), 163-172.
[7] I. B. Damgård 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-652. · Zbl 1156.11346
[8] H. Davenport, On the distribution of quadratic residues (mod p), J. Lond. Math. Soc. 6 (1931), no. 1, 49-54. · JFM 57.0213.03
[9] H. Davenport, On the distribution of quadratic residues (mod p). II, J. Lond. Math. Soc. 8 (1933), no. 1, 46-52. · JFM 59.0211.01
[10] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644-654. · Zbl 0435.94018
[11] C. Ding, D. Pei and A. Salomaa, Chinese Remainder Theorem. Applications in Computing, Coding, Cryptography, World Scientific, River Edge, 1996. · Zbl 0907.11002
[12] A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO’86, Lecture Notes in Comput. Sci. 263, Springer, Berlin (1987), 186-194. · Zbl 0636.94012
[13] A. Fujioka, T. Okamoto and S. Miyaguchi, ESIGN: An efficient digital signature implementation for smart cards, Advances in Cryptology—EUROCRYPT’91, Lecture Notes in Comput. Sci. 547, Springer, Berlin (1991), 446-457. · Zbl 0825.94184
[14] O. Goldreich, Foundations of Cryptography. Basic Tools, Cambridge University, Cambridge, 2001. · Zbl 1007.94016
[15] 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-308. · Zbl 0644.94012
[16] L. Goubin, C. Mauduit and A. Sárközy, Construction of large families of pseudorandom binary sequences, J. Number Theory 106 (2004), no. 1, 56-69. · Zbl 1049.11089
[17] L. Granboulan, How to repair ESIGN, Security in Communication Networks—SCN 2002, Lecture Notes in Comput. Sci. 2576, Springer, Berlin (2003), 234-240. · Zbl 1022.68537
[18] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Grad. Texts in Math. 84, Springer, New York, 1990. · Zbl 0712.11001
[19] J. Katz, Digital Signatures, Springer, New York, 2010. · Zbl 1202.94002
[20] F. Lemmermeyer, The Euclidean algorithm in algebraic number fields, Exp. Math. 13 (1995), no. 5, 385-416. · Zbl 0843.11046
[21] A. K. Lenstra, Unbelievable security (Matching AES security using public key systems), Advances in Cryptology—ASIACRYPT 2001, Lecture Notes in Comput. Sci. 2248, Springer, Berlin (2001), 67-86. · Zbl 1062.94550
[22] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. · Zbl 0488.12001
[23] A. K. Lenstra and E. Verheul, Selecting cryptographic key sizes, J. Cryptology 14 (2001), no. 4, 255-293. · Zbl 1006.94020
[24] H. W. Lenstra, Jr., Euclid’s algorithm in cyclotomic fields, J. Lond. Math. Soc. (2) 10 (1975), no. 4, 457-465. · Zbl 0313.12001
[25] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649-673. · Zbl 0629.10006
[26] 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-3. · Zbl 0806.11063
[27] N. Manohar and B. Fisch, Factoring n = p^2q, Final project report CS359C, Stanford University, 2017.
[28] A. May, Secret exponent attacks on RSA-type schemes with moduli N = p^rq, Public Key Cryptography—PKC 2004, Lecture Notes in Comput. Sci. 2947, Springer, Berlin (2004), 218-230. · Zbl 1198.94113
[29] 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.
[30] 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].
[31] 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-133.
[32] T. Okamoto and S. Uchiyama, A new public-key cryptosystem as secure as factoring, Advances in Cryptology—EUROCRYPT’98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin (1998), 308-318. · Zbl 0919.94028
[33] R. Peralta, On the distribution of quadratic residues and nonresidues modulo a prime number, Math. Comp. 58 (1992), no. 197, 433-440. · Zbl 0745.11057
[34] 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-493.
[35] 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-126. · Zbl 0368.94005
[36] A. Sárközy and C. L. Stewart, On pseudorandomness in families of sequences derived from the Legendre symbol, Period. Math. Hungar. 54 (2007), no. 2, 163-173. · Zbl 1136.11049
[37] H. Sato, T. Takagi, S. Tezuka and K. Takaragi, Generalized powering functions and their application to digital signatures, Advances in Cryptology—ASIACRYPT 2003, Lecture Notes in Comput. Sci. 2894, Springer, Berlin (2003), 434-451. · Zbl 1205.11130
[38] R. Scheidler and H. C. Williams, A public-key cryptosystem utilizing cyclotomic fields, Des. Codes Cryptogr. 6 (1995), no. 2, 117-131. · Zbl 0829.94005
[39] K. Schmidt-Samoa, A new Rabin-type trapdoor permutation equivalent to factoring, Electron. Notes Theor. Comput. Sci. 157 (2006), no. 3, 79-94. · Zbl 1294.94076
[40] K. Schmidt-Samoa and T. Takagi, Paillier’s cryptosystem modulo p^2q and its applications to trapdoor commitment schemes, Progress in Cryptology—Mycrypt 2005, Lecture Notes in Comput. Sci. 3715, Springer, Berlin (2005), 296-313. · Zbl 1126.94340
[41] C. P. Schnorr, Efficient signature generation by smart cards, J. Cryptology 4 (1991), no. 3, 161-174. · Zbl 0743.68058
[42] J. Stern, D. Pointcheval, J. Malone-Lee and N. P. Smart, Flaws in applying proof methodologies to signature schemes, Advances in cryptology—CRYPTO 2002, Lecture Notes in Comput. Sci. 2442, Springer, Berlin (2002), 93-110. · Zbl 1026.94550
[43] T. Takagi, Fast RSA-type cryptosystem modulo p^kq., Advances in Cryptology—CRYPTO’98, Lecture Notes in Comput. Sci. 1462, Springer, Berlin (1998), 318-326. · Zbl 0931.94041
[44] L. C. Washington, Introduction to Cyclotomic Fields, 2nd ed., Grad. Texts Math. 83, Springer, New York, 1997. · Zbl 0966.11047
[45] A. Weilert, Fast computation of the biquadratic residue symbol, J. Number Theory 96 (2002), no. 1, 133-151. · Zbl 1043.11003
[46] H. C. Williams, An M^3 public-key encryption scheme, Advances in Cryptology—CRYPTO’85, Lecture Notes in Comput. Sci. 218, Springer, Berlin (1986), 358-368. · Zbl 0612.94010
[47] BlueKrypt, Cryptographic key length recommendations, 2018.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.