ComplexityTheoretic OneWay Functions, Cryptography, and Pseudorandom Generators
This project studies complexitytheoretic oneway functions,
cryptography, and pseudorandom generators.
One central focus is
seeking characterizations regarding the existance of various types of
oneway functions, such as oneway permutations and polynomialtoone
oneway 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 oneway functions with those properties exist. We
have, relatedly, shown that oneway functions exist if and only if
strong, total, commutative, associative oneway 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
complexitytheoretic notions
and whether all pseudorandom generators are insecure.
 1

This is a list of selected journal (except when the work has not yet
appeared in journal/book form, plus in some cases some conference articles)
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 URCS 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.
SpringerVerlag Lecture Notes in Computer Science #403, 1990.
 3

A. Beygelzimer, L. Hemaspaandra, C. Homan, and J. Rothe.
Oneway functions in worstcase cryptography: Algebraic and
security properties are on the house.
SIGACT News, 30(4):25–40, 1999.
 4

J. Goldsmith, L. Hemachandra, and K. Kunen.
Polynomialtime 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.
Oneway functions and the nonisomorphism of NPcomplete sets.
Theoretical Computer Science, 81(1):155–163, 1991.
 8

E. Hemaspaandra and L. Hemaspaandra.
Quasiinjective reductions.
Theoretical Computer Science, 123(2):407–413, 1994.
 9

E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
All superlinear inverse schemes are coNPhard.
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(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, Z. Jiang, J. Rothe, and O. Watanabe.
Boolean operations, joins, and the extended low hierarchy.
Theoretical Computer Science, 205(1–2):317–327, 1998.
 14

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

L. Hemaspaandra and J. Rothe.
Creating strong, total, commutative, associative oneway functions
from any oneway function in complexity theory.
Journal of Computer and System Sciences, 58(3):648–659, 1999.
 16

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

L. Hemaspaandra, J. Rothe, and A. Saxena.
Enforcing and defying associativity, commutativity, totality, and
strong noninvertibility for oneway functions in complexity theory.
Theoretical Computer Science, 401(1–3):27–35, 2008.
 18

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

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

C. Homan.
Exploring and eliminating redundancy in computation.
Technical Report TR921, 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/theorytrs.html, of Christopher Homan's Ph.D.
dissertation.
 21

C. Homan and M. Thakur.
Oneway permutations and selfwitnessing languages.
Journal of Computer and System Sciences, 67(3):608–622,
November 2003.
 22

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

M. Zimand.
How to privatize random bits.
Technical Report TR616, Department of Computer Science, University
of Rochester, Rochester, NY, April 1996.
(Last modified: July 9, 2021.)
Lane A. Hemaspaandra
