| CIDEC ÜIK |
Estonian Winter Schools in Computer Science Eesti arvutiteaduse talvekoolid |
EWSCS 2000 EATTK 2000 |
University Frankfurt
Department of Mathematics
PSF 111932
60054 Frankfurt am Main
Germany
We introduce novel security proofs that use combinatorial counting arguments rather than reductions to the discrete logarithm or to the Diffie-Hellman problem. Our security results are sharp with no polynomial reduction times involved. Our approach separates in a better way cryptographic weaknesses of the hash function, the group and the cryptographic protocol. This separation is crucial. If an attack is possible for a specific hash function or group we replace the latter while keeping the cryptographic protocol. As strong hash functions and strong groups have been proposed, it makes sense to analyze cryptographic protocols assuming that the hash function and the group have no cryptographic weaknesses. So we merely consider attacks that work for all hash functions and for all groups. Formally, we consider a combination of the random oracle model and the generic model. This corresponds to assuming an ideal hash function given by an oracle and an ideal group of prime order q, where the binary encoding of the group elements is useless for cryptographic attacks.
In this model, we first show that Schnorr signatures are secure against the one-more signature forgery: A generic adversary performing t generic steps including l sequential interactions with the signer cannot produce l+1 signatures with a better probability than t^2/q. We also characterize the different power of sequential and of parallel attacks.
Secondly, we show that signed ElGamal encryption is secure against the adaptive chosen ciphertext attack, in which an attacker can arbitrarily use a decryption oracle except for the challenge ciphertext. Moreover, signed ElGamal encryption is secure against the one-more decryption attack: A generic adversary performing t generic steps including l interactions with the decryption oracle cannot distinguish the plaintexts of l+1 ciphertexts from random strings with a probability exceeding t^2/q.
Claus Peter Schnorr, born in 1943, studied mathematics and physics at the university Saarbruecken, where he obtained a Diplom in mathematics (1966) and a promotion as Dr. rer. nat. (1967), supervised by Prof. Dr. Hotz. In 1970 he got a Habilitation for extending the theory of Kolmogorov random sequences. C.P. Schnorr became professor at the University Saarbruecken (1970), at the University Erlangen-Nuernberg (1971). Since August 1971 he is full professor in the Mathematics Department (http://www.mi.informatik.uni-frankfurt.de/) and also in the Computer Science Department (since its foundation) of the University Frankfurt am Main. He initiated and continues to chair a series of workshops on Complexity Theory and Cryptography at the Mathematical Forschungsinstitut Oberwolfach, the IBFI Dagstuhl and the CIRM Luminy. He was visiting professor at Stanford, Berkeley, U. Chicago, SMU Dallas, ENS Paris, U. Marseille Luminy and at Bell Laboratories. He is author of about 60 research papers and two books on various subjects in applied mathematics, number theory, computer science and cryptography. He holds basic patents in public key cryptography.
This abstract and information about the speaker is taken from the website of PKC 2000 - International Workshop on Practice and Theory of Public Key Cryptography, Melbourne, Jan 18-20, 2000, where C.P. Schnorr presented an Invited Talk on the same subject.
02/02/2000 monika@cs.ioc.ee