A new probabilistic public key algorithm based on elliptic logarithms

• Afonso Comba de Araujo Neto UFRGS
• Raul Fernando Weber UFRGS

DOI: https://doi.org/10.5753/sbseg.2006.20947

Resumo

This paper introduces a new probabilistic public key algorithm based on elliptic curves and show that it is secure. The security of the scheme is solely based on the difficulty of the elliptic curve discrete logarithm problem while at the same time it has a constant message expansion for one encryption of a plaintext of any practical size. In the alternative algorithms, like Cramer-Shoup and PSEC, for a large plaintext, either the message expansion is proportional to its size or an additional security assumption is needed. Although some restrictions are posed on the public part of the key, we show how to easily find the needed parameters, and also suggest ways to make the public key as small as possible.

Referências

I. F. Blake, G. Seroussi and N. P. Smart, “Elliptic Curves in Cryptography,” London Mathematical Society. Lecture Notes Series 265. Cambridge University Press., 1999;

M. Blum and S. Goldwasser, “An Efficient Probabilistic Public-key Encryption Scheme Which Hides All Partial Information,” Advances in Cryptology - CRYPTO’84, vol. 196, Springer Verlag, pp. 289–302, 1985;

H. Cohen, “A course in computational algebraic number theory,” Graduate Texts in Mathematics 138. Springer-Verlag., 1993;

R. Cramer and V. Shoup, “A practical public key crypto system provably secure against adaptive chosen ciphertext attack,” proceedings of Crypto 1998, LNCS 1462, p.13ff, 1998;

S. Goldwasser and S. Micali, “Probabilistic encryption,” JCSS, vol. 28, pp. 270–299, April 1948;

B. S. Kaliski, Jr. “Elliptic Curves and Cryptography: A Pseudorandom Bit Generator and Other Tools,” PhD Thesis, MIT EECS Dept., January 1988;

A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, 1996;

T. Okamoto, E. Fujisaki and H. Morita, “PSEC: Provably Secure Elliptic Curve Encryption Scheme,” Submission to IEEE P1363a., March 1999;

R. Peralta , “On the distribution of quadratic residues and non-residues modulo a prime number”, Mathematics of Computation, Vol. 58, pp. 433 – 440, 1992.