How To Construct Randolli Functions
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 464-479
- https://doi.org/10.1109/sfcs.1984.715949
Abstract
This paper develops a constructive theory of randomness for functions based on computational complexity. We present a deterministic polynomial-time algorithm that transforms pairs (g,r), where g is any one-way (in a very weak sense) function and r is a random k-bit string, to polynomial-time computable functions f/sub r/:{1,..., 2/sup k} /spl I.oarr/ {1, ..., 2/sup k/}. These f/sub r/'s cannot be distinguished from random functions by any probabilistic polynomial time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions and complexity theory.Keywords
This publication has 21 references indexed in Scilit:
- Randomness conservation inequalities; information and independence in mathematical theoriesInformation and Control, 1984
- On Computationally Secure Authentication Tags Requiring Short Secret Shared KeysPublished by Springer Nature ,1983
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMSRussian Mathematical Surveys, 1970
- The definition of random sequencesInformation and Control, 1966
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- A formal theory of inductive inference. Part IInformation and Control, 1964