Download (free)

Abstract

We provide reductionist security arguments for a key agreement
protocol KA, which is the Die-Hellman key agreement protocol
generalized to the context of a group action on a set, and for a public-
key encryption scheme PE, which is the \\hashed\" ElGamal scheme
generalized for a group action on a set. For the KA protocol we use the
notion of session key security in the authenticated links model, proposed
by Canetti and Krawczyk. For the PE scheme we use a version of the
semantic security notion proposed by Goldwasser and Micali. We prove
that the security of the KA protocol and the PE scheme is based on
the decisional Die-Hellman group action problem, dened later in this
paper. The PE scheme security also depends on the entropy smoothing
property of the hash function family used in the scheme.

References

[1] Ko, Lee, Cheon, Han, Kang, and Park. New public-key cryptosystem using
braid groups. In CRYPTO: Proceedings of Crypto, 2000.
[2] Christopher J. Monico. Semirings and Semigroup Actions in Public-Key
Cryptography. PhD thesis, The Graduate School of the University of Notre
Dame, Indiana, 2002.
[3] Alexander Rostovtsev and Anton Stolbunov. Public-key cryptosystem based
on isogenies. Report 2006/145, Cryptology ePrint Archive, April 2006.
[4] Gerard Maze, Chris Monico, and Joachim Rosenthal. Public key cryptography
based on semigroup actions. Advances in Math. of Communications, 1(4):489{
507, 2007.
[5] Neal Koblitz and Alfred Menezes. Another look at \"provable security\".
J. Cryptology, 20(1):3{37, 2007.
[6] Neal Koblitz and Alfred Menezes. Another look at \"provable security\". II. In
Rana Barua and Tanja Lange, editors, INDOCRYPT, volume 4329 of Lecture
Notes in Computer Science, pages 148{175. Springer, 2006.
[7] Mihir Bellare and Phillip Rogaway. Entity authentication and key distribution.
In Douglas R. Stinson, editor, Advances in Cryptology { CRYPTO\' 93, volume
773 of Lecture Notes in Computer Science, pages 232{249. Springer-Verlag,
Berlin Germany, 1994.
[8] Ran Canetti and Hugo Krawczyk. Analysis of key-exchange protocols and
their use for building secure channels. In Birgit Ptzmann, editor, Advances in
Cryptology { EUROCRYPT\' 2001, volume 2045 of Lecture Notes in Computer
Science, pages 451{472, Innsbruck, Austria, 2001. Springer-Verlag, Berlin
Germany.
[9] Ran Canetti and Hugo Krawczyk. Analysis of key-exchange protocols and their
use for building secure channels. Report 2001/040, Cryptology ePrint Archive,
May 2001.
108 The Norwegian Information Security Conference (NISK) 2009
[10] Danny Dolev and Andrew C. Yao. On the security of public key protocols.
IEEE Transactions on Information Theory, 29(2):198{208, 1983.
[11] Kudla and Paterson. Modular security proofs for key agreement protocols.
In ASIACRYPT: Advances in Cryptology { ASIACRYPT: International
Conference on the Theory and Application of Cryptology. LNCS, Springer-
Verlag, 2005.
[12] Sha Goldwasser and Silvio Micali. Probabilistic encryption. Journal of
Computer and System Sciences, 28(2):270{299, 1984.
[13] Oded Goldreich. The Foundations of Cryptography. Cambridge University
Press, 2001.
[14] David S. Dummit and Richard M. Foote. Abstract Algebra. Wiley, third edition,
2004.
[15] Whiteld Die and Martin E. Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, IT-22(6):644{654, 1976.
[16] Mihir Bellare, Anand Desai, David Pointcheval, and Phil Rogaway. Relations
among notions of security for public-key encryption schemes. In Hugo
Krawczyk, editor, Advances in Cryptology { CRYPTO\' 98, volume 1462 of
Lecture Notes in Computer Science, pages 26{45. Springer-Verlag, Berlin
Germany, 1998.
[17] Christian Cachin and Ueli Maurer. Smoothing probability distributions
and smooth entropy (extended abstract). In Proceedings of International
Symposium on Information Theory, ISIT 97, 1996.
[18] V. Shoup. Sequences of games: a tool for taming complexity in security proofs.
Report 2004/332, Cryptology ePrint Archive, November 2004.
[19] Cas J. F. Cremers. Feasibility of multi-protocol attacks. In ARES, pages 287{
294. IEEE Computer Society, 2006.



Previous article      Next article