Version History:
ArXiv v1, 24 April 2017 https://arxiv.org/abs/1704.07309v1 ArXiv v2, 25 April 2017 https://arxiv.org/abs/1704.07309v2 ArXiv v3, 9 September 2017 https://arxiv.org/abs/1704.07309v3 ArXiv v4, 5 October 2017 https://arxiv.org/abs/1704...Version History. Preliminary versions of this work appeared in the first author's undergraduate thesis and in the conference paper (STOC '05).
We study the round complexity of two-party protocols for generating a random \(n\)-bit string such that the...
Version History: Merged with STOC '07 paper of Haitner and Reingold. Also available as a journal version. Full version invited to SIAM J. Computing Special Issue on FOCS ‘06
We show that every language in NP has a statistical zero-knowledge argument...
Version History: Preliminary version posted as Cryptology ePrint Archive Report 2011/553, under title “Non-Interactive Time-Stamping and Proofs of Work in the Random Oracle Model”.
We construct a publicly verifiable protocol for proving computational...
Version History: Preliminary versions of this article appeared as Technical Report TR06-134 in Electronic Colloquium on Computational Complexity, 2006, and in Proceedings of the 22nd Annual IEEE Conference on Computional Complexity (CCC '07), pp. 96–108...
Version History: Preliminary version posted as ECCC TR08-103.
We show that every bounded function \({g} \) : \(\{0,1\}^n \to [0,1]\) admits an efficiently computable "simulator" function \({h} \) : \(\{0,1\}^n \to [0,1]\) such that every fixed polynomial...
Version History: Recipient of Best Paper Award. Preliminary version posted on ECCC as TR06-139, November 2006.
We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems. This characterization is...
Version History: earlier version published in ECCC in November 2024: https://eccc.weizmann.ac.il/report/2024/169/
We initiate the study of the randomness complexity of differential privacy, i.e., how many random bits an algorithm needs in order to...
