Safer parameters for the Chor-Rivest cryptosystem. (English) Zbl 1165.94320
Summary: Vaudenay’s cryptanalysis against Chor-Rivest cryptosystem is applicable when the parameters, \(p\) and \(h\), originally proposed by the authors are used. Nevertheless, if \(p\) and \(h\) are both prime integers, then Vaudenay’s attack is not applicable. In this work, a choice of these parameters resistant to the existing cryptanalytic attacks, is presented. The parameters are determined in a suitable range guaranteeing its security and the computational feasibility of implementation. Regrettably, the obtained parameters are scarce in practice.
MSC:
| 94A60 | Cryptography |
Keywords:
Chor-Rivest cryptosystem; cryptanalysis; finite fields; prime parameters; public key cryptographyReferences:
| [1] | Chor, B., Two Issues in Public Key Cryptography. RSA Bit Security and a New Knapsack Type System (1985), The MIT Press: The MIT Press Cambridge, MS |
| [2] | Chor, B.; Rivest, R. L., A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Trans. Inform. Theory, 34, 5, 901-909 (1988) · Zbl 0664.94011 |
| [3] | Brickell, E., Solving low density knapsacks, (Chaum, D., Proc. of Crypto’83 (1984), Plenum Press), 25-37 · Zbl 1486.94082 |
| [4] | Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C. P.; Stern, J., Improved low-density subset sum algorithms, Comput. Complexity, 2, 111-128 (1992) · Zbl 0768.11049 |
| [5] | Frieze, A. M., On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM J. Comput., 15, 2, 536-539 (1986) · Zbl 0592.94010 |
| [6] | Jorissen, F.; Vandewalle, J.; Govaerts, R., Extension of Brickell’s algorithm for breaking high density knapsacks, Lect. Notes Comput. Sci., 304, 109-115 (1988) · Zbl 1464.94036 |
| [7] | Joux, A.; Stern, J., Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems, Lect. Notes Comput. Sci., 529, 258-264 (1991) · Zbl 0925.90301 |
| [8] | Lagarias, J. C.; Odlyzko, A. M., Solving low-density subset sum problems, J. ACM, 32, 1, 229-246 (1985) · Zbl 0632.94007 |
| [9] | H.H. Hörner, Verbesserte Gitterbasenreduktion; getestet am Chor-Rivest Kryptosystem und an allgemeinen Rucksack-Problemen, Diplomarbeit, Universität Frankfurt, August, 1994; H.H. Hörner, Verbesserte Gitterbasenreduktion; getestet am Chor-Rivest Kryptosystem und an allgemeinen Rucksack-Problemen, Diplomarbeit, Universität Frankfurt, August, 1994 |
| [10] | Schnorr, C. P.; Hörner, H. H., Attacking the Chor-Rivest cryptosystem by improved lattice reduction, Lect. Notes Comput. Sci., 921, 1-12 (1995) · Zbl 0973.94514 |
| [11] | Vaudenay, S., Cryptanalysis of the Chor-Rivest cryptosystem, J. Cryptology, 14, 87-100 (2001) · Zbl 0979.94037 |
| [12] | Menezes, A. J.; van Oorschot, P. C.; Vanstone, S., Handbook of Applied Cryptography (1997), CRC Press: CRC Press Boca Raton, FL · Zbl 0868.94001 |
| [13] | Bach, E.; Shallit, J., Algorithmic number theory, (Vol 1: Efficient Algorithms (1996), The MIT Press: The MIT Press Cambridge, MS) · Zbl 0873.11070 |
| [14] | Koblitz, N., A Course in Number Theory and Cryptography (1994), Springer-Verlag: Springer-Verlag Berlin · Zbl 0819.11001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
