Theory and application of trapdoor functions
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 80-91
- https://doi.org/10.1109/sfcs.1982.45
Abstract
The purpose of this paper is to introduce a new information theory and explore its appplications. Using modern computational complexity, we study the notion of information that can be accessed through a feasible computation. In Part 1 of this paper, we lay the foundation of the theory and set up a framework for cryptography and pseudorandom number generation. In Part 2, we study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory.Keywords
This publication has 19 references indexed in Scilit:
- Probabilistic encryption & how to play mental poker keeping secret all partial informationPublished by Association for Computing Machinery (ACM) ,1982
- 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
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- On simultaneous resource boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS††Portions of this work were carried out at Carngie-Mellon University, while the authors were in the Department of Computer Science. Portions of these results were reported in preliminary form in [1].Published by Elsevier ,1971
- 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