Complexity-Theoretic One-Way Functions, Cryptography, and Pseudorandom Generators

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

Project Description

This project studies complexity-theoretic one-way functions, cryptography, and pseudorandom generators.

One 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. For example, for each of the 81 ways one can require, forbid, or be oblivious to the four attributes “strong,” “total,” “commutative,” and “associative,” we have completely characterized in terms of the separation of complexity classes the issue of whether one-way functions with those properties exist. We have, relatedly, shown that one-way functions exist if and only if strong, total, commutative, associative one-way functions exist.

Also of interest in this project is the extent to which queries can be made without leaking information, and learning more about the connection between foundational complexity-theoretic notions and whether all pseudorandom generators are insecure.

References

1

This is a list of selected papers, from or related to this project, by University of Rochester authors. Links to essentially all Lane's conference and journal papers (and also his arXiv.org technical reports) can be found via the pointers from the related entries within Lane's entry at the DBLP project. Additionally, here is a link to Lane's complete publication list (note: that list does not itself have links to papers).

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

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
In Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, pages 377–388. Leibniz International Proceedings in Informatics (LIPIcs) #20, February/March 2013.

11

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
ACM Transactions on Computation Theory, 12(#1, Article 3):1–42, 2020.

12

L. Hemaspaandra.
Beautiful structures: An appreciation of the contributions of Alan Selman.
SIGACT News, 45(3):54–70, 2014.

13

L. Hemaspaandra.
Juris Hartmanis and two golden rules.
SIGACT News, 53(4):35–40, 2022.

14

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.

15

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.

16

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.

17

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

18

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, 401(1–3):27–35, 2008.

19

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

20

C. Homan.
Tight lower bounds on the ambiguity in strong, total, associative, one-way functions.
Journal of Computer and System Sciences, 68(3):657–674, 2004.

21

C. Homan.
Exploring and eliminating redundancy in computation.
Technical Report TR-921, Department of Computer Science, University of Rochester, Rochester, NY, August 2007.
This is the technical report version, available on the web at cs.rochester.edu/trs/theory-trs.html, of Christopher Homan's Ph.D. dissertation.

22

C. Homan and M. Thakur.
One-way permutations and self-witnessing languages.
Journal of Computer and System Sciences, 67(3):608–622, November 2003.

23

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

24

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: February 16, 2023.)