Abstract
Now that “random functions” can be efficiently constructed([GGM]), we discuss some of their possible applications to cryptography:
-
1)
Distributing unforgable ID numbers which can be locally verified by stations which contain only a small amount of storage.
-
2)
Dynamic Hashing: even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, still he can not force collisions.
-
3)
Constructing deterministic, memoryless authentication schemes which are provably secure against chosen message attack.
-
4)
Construction Identity Friend or Foe systems.
The first author was supported in part by a Weizmann Postdoctoral fellowship. The second author was supported in part by the International Business Machines Corporation under the IBM/MIT Joint Research Program, Faculty Development Award agreement dated August 9, 1983.
Chapter PDF
Similar content being viewed by others
References
D. Angluin and D. Lichtenstein, Provable Security of Cryptosystems: a Survey, YaleU/DCS/TR-288, 1983
L. Blum, M. Blum and M. Shub, A simple secure pseudo random number generator, Advances in Cryptology: Proc. of CRYPTO-82, ed. D. Shaum, R. L. Rivest and A.T. Sherman. Plenum press 1983, pp 61–78.
M. Blum and S. Goldwasser, An Efficient Probabilistic Public-Key Encryption Scheme Which Hides all Partial Information, preprint May 1984.
M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. COMPUT., Vol 13, No. 4, Nov. 1984.
G. Brassard, On computationally secure authentication tags requiring short secret shared keys, Advances in Cryptology: Proc. of CRYPTO-82, ed. D. Sham, R.L. Rivest and A.T. Sherman. Plenum press 1983, pp 79–86.
B. Chor and O. Goldreich, RSA Rabin least significant bits are \( \frac{1} {2} + \frac{1} {{poly (\log N)}} \) secure, MIT/LCS/TM-260, May 1984.
J.L. Carter and M.N. Wegman, Universal classes of hash functions, Proc. 9th ACE Symp. on Theory of Computing, 1977, pp 106–112.
O. Goldreich, S. Coldwasser and S. Micali, How to construc random functions, MIT/LCS/TM-244, November 1983.
O. Goldreich and S. Micali, The weakest CSPRB generator implies the strongest one, in preparation.
S. Goldwasser, S. Micali and P. Tong. Why and how to establish a private code on a public network, Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982, pp 134–144.
R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Commun. ACM vol. 21, Feb. 1978, pp 120–126.
A. Shamir, On the Generation of Cryptographically Strong Pseudorandom Sequences, 8th International Colloquiun on Automata, Languages, and Programming, Lect. Notes in Comp. Sci. 62, Springer Verlag, 1981.
A.C. Yao, Theory and applications of trapdoor functions, Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982, pp 80–91
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldreich, O., Goldwasser, S., Micali, S. (1985). On the Cryptographic Applications of Random Functions (Extended Abstract). In: Blakley, G.R., Chaum, D. (eds) Advances in Cryptology. CRYPTO 1984. Lecture Notes in Computer Science, vol 196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39568-7_22
Download citation
DOI: https://doi.org/10.1007/3-540-39568-7_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15658-1
Online ISBN: 978-3-540-39568-3
eBook Packages: Springer Book Archive