IEICE TRANSACTIONS on Fundamentals
A Theory of Randomness for Public Key Cryptosystems: The ElGamal Cryptosystem Case
Summary :
There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the ElGamal cryptosystem with some well-known generators (e. g. , the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.614-619
- Publication Date
- 2000/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeshi KOSHIBA, "A Theory of Randomness for Public Key Cryptosystems: The ElGamal Cryptosystem Case" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 614-619, April 2000, doi: .
Abstract: There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the ElGamal cryptosystem with some well-known generators (e. g. , the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_614/_p
Copy
@ARTICLE{e83-a_4_614,
author={Takeshi KOSHIBA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Theory of Randomness for Public Key Cryptosystems: The ElGamal Cryptosystem Case},
year={2000},
volume={E83-A},
number={4},
pages={614-619},
abstract={There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the ElGamal cryptosystem with some well-known generators (e. g. , the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - A Theory of Randomness for Public Key Cryptosystems: The ElGamal Cryptosystem Case
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 614
EP - 619
AU - Takeshi KOSHIBA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - There are many public key cryptosystems that require random inputs to encrypt messages and their security is always discussed assuming that random objects are ideally generated. Since cryptosystems run on computers, it is quite natural that these random objects are computationally generated. One theoretical solution is the use of pseudorandom generators in the Yao's sense. Informally saying, the pseudorandom generators are polynomial-time algorithms whose outputs are computationally indistinguishable from the uniform distribution. Since if we use the Yao's generators then it takes much more time to generate pseudorandom objects than to encrypt messages in public key cryptosystems, we relax the conditions of pseudorandom generators to fit public key cryptosystems and give a minimal requirement for pseudorandom generators within public key cryptosystems. As an example, we discuss the security of the ElGamal cryptosystem with some well-known generators (e. g. , the linear congruential generator). We also propose a new pseudorandom number generator, for random inputs to the ElGamal cryptosystem, that satisfies the minimal requirement. The newly proposed generator is based on the linear congruential generator. We show some evidence that the ElGamal cryptosystem with the proposed generator is secure.
ER -
English
