Cryptography, One-Way Functions, and Pseudorandom Generators
This project studies one-way functions, pseudorandom generators,
and cryptography.
One focus is seeking the weakest possible sufficient conditions for
making all pseudorandom generators insecure. Another central focus is
seeking characterizations regarding the existance of various types of
one-way functions, such as one-way permutations and polynomial-to-one
one-way functions. Also of interest is the extent to which queries
can be made without leaking information.
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form) papers, from or related to this project, by
University of Rochester authors. Essentially all the papers listed below can
be found, in their full technical report versions, in the
UR-CS Technical Report Archive's theory
section. Lane
Hemaspaandra's complete publication list can always be found at
http://www.cs.rochester.edu/u/lane/publist.pdf.
- 2
-
M. Abadi, E. Allender, A. Broder, J. Feigenbaum, and L. Hemachandra.
On generating solved instances of computational problems.
In Advances in Cryptology--CRYPTO '88, pages 297-310.
Springer-Verlag Lecture Notes in Computer Science #403, 1990.
- 3
-
A. Beygelzimer, L. Hemaspaandra, C. Homan, and J. Rothe.
One-way functions in worst-case cryptography: Algebraic and
security properties are on the house.
SIGACT News, 30(4):25-40, 1999.
- 4
-
J. Cai, R. Lipton, L. Longpré, M. Ogihara, K. Regan, and D. Sivakumar.
Communication complexity of key agreement on limited ranges.
In Proceedings of the 12th Annual Symposium on Theoretical
Aspects of Computer Science, pages 38-49. Springer-Verlag Lecture
Notes in Computer Science #900, March 1995.
- 5
-
J. Goldsmith, L. Hemachandra, and K. Kunen.
Polynomial-time compression.
Computational Complexity, 2(1):18-39, 1992.
- 6
-
Y. Han and L. Hemaspaandra.
Pseudorandom generators and the frequency of simplicity.
Journal of Cryptology, 9(4):251-261, 1996.
- 7
-
Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59-78, 1997.
- 8
-
J. Hartmanis and L. Hemachandra.
One-way functions and the non-isomorphism of NP-complete sets.
Theoretical Computer Science, 81(1):155-163, 1991.
- 9
-
E. Hemaspaandra and L. Hemaspaandra.
Quasi-injective reductions.
Theoretical Computer Science, 123(2):407-413, 1994.
- 10
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science, 345(2-3):345-358, 2005.
- 11
-
L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.
Boolean operations, joins, and the extended low hierarchy.
Theoretical Computer Science, 205(1-2):317-327, 1998.
- 12
-
L. Hemaspaandra, K. Pasanen, and J. Rothe.
If
then some strongly noninvertible functions are
invertible.
In Proceedings of the 13th International Symposium on
Fundamentals of Computation Theory, pages 162-171. Springer-Verlag Lecture Notes in Computer Science #2138, August 2001.
- 13
-
L. Hemaspaandra and J. Rothe.
Creating strong, total, commutative, associative one-way functions
from any one-way function in complexity theory.
Journal of Computer and System Sciences, 58(3):648-659, 1999.
- 14
-
L. Hemaspaandra and J. Rothe.
Characterizing the existence of one-way permutations.
Theoretical Computer Science, 244(1-2):257-261, 2000.
- 15
-
L. Hemaspaandra, J. Rothe, and A. Saxena.
Enforcing and defying associativity, commutativity, totality, and
strong noninvertibility for one-way functions in complexity theory.
In Proceedings of the 9th Italian Conference on Theoretical
Computer Science, pages 265-279. Springer-Verlag Lecture Notes in
Computer Science #3701, October 2005.
- 16
-
L. Hemaspaandra, J. Rothe, and G. Wechsung.
Easy sets and hard certificate schemes.
Acta Informatica, 34(11):859-879, 1997.
- 17
-
L. Hemaspaandra, J. Rothe, and G. Wechsung.
On sets with easy certificates and the existence of one-way
permutations.
In Proceedings of the 3rd Italian Conference on Algorithms and
Complexity, pages 264-275. Springer-Verlag Lecture Notes in Computer
Science #1203, 1997.
- 18
-
M. Ogiwara.
A method for generating cryptographically strong primes.
IEICE Transactions on Communications, Electronics, Information,
and Systems, E73:985-994, 1990.
- 19
-
M. Ogiwara.
On the paddability of the quadratic residuosity problem.
IEICE Transactions on Communications, Electronics, Information,
and Systems, E73:207-211, 1990.
- 20
-
J. Rothe and L. Hemaspaandra.
On characterizing the existence of partial one-way permutations.
Information Processing Letters, 82(3):165-171, 2002.
- 21
-
M. Zimand.
How to privatize random bits.
Technical Report TR-616, Department of Computer Science, University
of Rochester, Rochester, NY, April 1996.
Lane A. Hemaspaandra