Cryptography, One-Way Functions, and Pseudorandom Generators

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

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.

Bibliography

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. Here is Lane's complete publication list and links to essentially all his conference and journal papers (and also his arxiv.org technical reports) can be found via the ``EE'' (electronic edition) links at Lane's entry at the DBLP project.

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. Goldsmith, L. Hemachandra, and K. Kunen.
Polynomial-time compression.
Computational Complexity, 2(1):18-39, 1992.

5
Y. Han and L. Hemaspaandra.
Pseudorandom generators and the frequency of simplicity.
Journal of Cryptology, 9(4):251-261, 1996.

6
Y. Han, L. Hemaspaandra, and T. Thierauf.
Threshold computation and cryptographic security.
SIAM Journal on Computing, 26(1):59-78, 1997.

7
J. Hartmanis and L. Hemachandra.
One-way functions and the non-isomorphism of NP-complete sets.
Theoretical Computer Science, 81(1):155-163, 1991.

8
E. Hemaspaandra and L. Hemaspaandra.
Quasi-injective reductions.
Theoretical Computer Science, 123(2):407-413, 1994.

9
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNP-hard.
Theoretical Computer Science, 345(2-3):345-358, 2005.

10
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.

11
L. Hemaspaandra, K. Pasanen, and J. Rothe.
If P $\neq$ NP then some strongly noninvertible functions are invertible.
Theoretical Computer Science, 362(1-3):54-62, 2006.

12
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.

13
L. Hemaspaandra and J. Rothe.
Characterizing the existence of one-way permutations.
Theoretical Computer Science, 244(1-2):257-261, 2000.

14
L. Hemaspaandra, J. Rothe, and A. Saxena.
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for one-way functions in complexity theory.
Theoretical Computer Science.
To appear.

15
L. Hemaspaandra, J. Rothe, and G. Wechsung.
Easy sets and hard certificate schemes.
Acta Informatica, 34(11):859-879, 1997.

16
J. Rothe and L. Hemaspaandra.
On characterizing the existence of partial one-way permutations.
Information Processing Letters, 82(3):165-171, 2002.

17
M. Zimand.
How to privatize random bits.
Technical Report TR-616, Department of Computer Science, University of Rochester, Rochester, NY, April 1996.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: June 5, 2008.)


Lane A. Hemaspaandra