Omer
Reingold - Online Publications
Note: Experience shows that the versions given here are not
necessarily the fullest and most updated (though this is certainly my
intention). They are also not meant to be the same as any published version. An
email to me (or better yet, to my coauthors ;-) may result in a better version.
In reversed chronological order:
- R. Gradwohl and O. Reingold, Partial Exposure and
Correlated Types in Large Games, manuscript, 2007.
- I. Haitner, J. J. Hoch, O. Reingold and G. Segev,
Finding Collisions in Interactive Protocols --
A Tight Lower Bound on the Round Complexity of Statistically-Hiding
Commitments, To appear in: FOCS 2007.
- I. Haitner and O. Reingold,
A New Interactive Hashing Theorem, CCC 2007.
- K.-M. Chung, O. Reingold and S. Vadhan,
S-T Connectivity on Digraphs with Known Stationary Distribution, CCC 2007.
- I. Haitner and O. Reingold,
Statistically-Hiding Commitment from Any One-Way Function, STOC 2007.
- I. Haitner, D. Harnik, O. Reingold,
On the Power of the Randomized Iterate,
CRYPTO 2006.
- I. Haitner, D. Harnik, O. Reingold,
Efficient Pseudorandom Generators from Exponentially
Hard One-Way Functions, ICALP 2006.
- O. Reingold, L. Trevisan and S. Vadhan,
Pseudorandom walks on regular digraphs and the RL vs. L
problem. STOC 2006.
- R. Gradwohl, G. Kindler, O. Reingold and A. Ta-Shma,
On the Error Parameter of Dispersers, RANDOM
2005.
- E. Kaplan, M. Naor and O. Reingold,
Derandomized Constructions of k-Wise (Almost) Independent Permutations,
RANDOM 2005.
- O. Reingold, Undirected ST-Connectivity in
Log-Space, STOC 2005.
- D. Harnik, J. Kilian, M. Naor, O. Reingold, and Alon Rosen,
On robust combiners for oblivious transfer and other
primitives, EUROCRYPT 2005.
- M. J. Freedman, Y. Ishai, B. Pinkas and O. Reingold,
Keyword search and oblivious pseudorandom functions, TCC 2005.
- I. Dinur and O. Reingold,
Assignment-Testers: towards a combinatorial proof of the PCP-Theorem, SIAM
J. Comput. - special issue on "Randomness and Computation", 2006. Preliminary
Version: FOCS
2004.
- C. Dwork, M. Naor and O. Reingold, Immunizing encryption
schemes from decryption errors, EUROCRYPT 2004.
- O. Reingold, L. Trevisan and S. P. Vadhan,
Notions of
reducibility between cryptographic primitives, TCC 2004.
- D. Harnik, M. Naor, O. Reingold and A. Rosen,
Completeness
in two-party secure computation: a computational view, J. Cryptology,
2006, Preliminary Version: STOC 2004.
- C.-J. Lu, O. Reingold, S. P. Vadhan, and Avi Wigderson:
Extractors: optimal up to constant factors, STOC 2003.
- N. Alon, M. Merritt, O. Reingold, G. Taubenfeld, R. N.
Wright, Tight bounds for shared memory systems accessed by Byzantine
processes, Distributed Computing, Preliminary version in DISC
2002.
- Bar-Yossef, O. Reingold and R. Shaltiel and L. Trevisan,
Streaming computation of combinatorial objects, IEEE Conference on
Computational Complexity 2002.
- M. R. Capalbo, O. Reingold, S. P. Vadhan and A. Wigderson,
Randomness conductors and constant-degree lossless expanders, Joint session: STOC 2002, and IEEE Conference on Computational Complexity 2002.
- Y. Gertner, T. Malkin and O. Reingold, On the impossibility
of basing trapdoor functions on trapdoor predicates, FOCS 2001.
- W. Aiello, S. M. Bellovin, M. Blaze, R. Canetti, J.
Ioannidis, A. D. Keromytis, and O. Reingold: Just fast keying: Key agreement
in a hostile internet. ACM Trans. Inf. Syst. Secur., 2004.
Preliminary Version: Efficient, DoS-Resistant, Secure Key Exchange for
Internet Protocols. Security Protocols Workshop 2001.
- M. Naor and O. Reingold: Constructing pseudorandom
permutations with a prescribed structure, J. Cryptology, 2002, Preliminary
Version: SODA 2001.
- W. Aiello, Y. Ishai and O. Reingold, Priced oblivious
transfer: how to sell digital goods, EUROCRYPT 2001.
- O. Reingold, S. P. Vadhan and A. Wigderson,
Entropy waves,
the Zig-Zag graph product, and new constant-degree expanders and extractors, FOCS 2000.
Full Version of part of this work: Annals of Mathematics, 2001.
- O. Reingold, R. Shaltiel and A. Wigderson,
Extracting
randomness via repeated condensing, SIAM J. Comput., 2006. Preliminary
Version: FOCS 2000.
- Y. Gertner, S. Kannan, T. Malkin, O. Reingold and M.
Viswanathan, The relationship between public key encryption and oblivious
transfer, FOCS 2000.
- M. Naor, O. Reingold and A. Rosen, Pseudorandom functions
and factoring, SIAM J. Comput., 2002. Preliminary Version: STOC 2000.
- R. Raz, O. Reingold and S. P. Vadhan, Error reduction for
extractors, FOCS 1999, pp. 191-201, 1999.
- C. Dwork, M. Naor, O. Reingold and L. J. Stockmeyer,
Magic
functions, J. ACM, 2003. Preliminary Version: FOCS 1999.
- M. Naor, B. Pinkas and O. Reingold, Distributed
pseudorandom functions and KDCs, EUROCRYPT 1999.
- R. Raz, O. Reingold and S. P. Vadhan, Extracting all the
randomness and reducing the error in Trevisan's extractors, J. Comput. Syst.
Sci. (JCSS), 2002. Preliminary Version: STOC 1999.
- R. Raz and O. Reingold, On recycling the randomness of
states in space bounded computation, STOC 1999.
- E. Biham, D. Boneh and O. Reingold, Breaking generalized Diffie-Hellmann modulo a composite is no easier than factoring, Information
Processing Letters, 1999.
- M. Naor and O. Reingold, From unpredictability to indistinguishability: A simple construction of pseudorandom functions from
MACs, CRYPTO 1998.
- R. Canetti, D. Micciancio and O. Reingold, Perfectly
one-way probabilistic hash functions, STOC 1998.
- M. Naor and O. Reingold, Number-Theoretic constructions of
efficient pseudorandom functions, J. ACM 2004. Preliminary Version: FOCS 1997.
An
implementation.
- M. Naor and O. Reingold, On the construction of
pseudorandom permutations: Luby-Rackoff revisited, J. of Cryptology, 1999.
Preliminary Version: STOC 1997.
- M. Naor and O. Reingold, Synthesizers and their application
to the parallel construction of pseudorandom functions, Journal of Computer
and System Sciences (JCSS), 1999. Preliminary Version: FOCS 1995.
For something a little bit different:
