Browsing Faculty of Arts and Sciences by Keyword "cryptography"

Now showing items 1-6 of 6

    • Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions 

      Vadhan, Salil P.; Zheng, Colin Jia (ACM Press, 2012)
      We provide a characterization of pseudoentropy in terms of hardness of sampling: Let (X,B) be jointly distributed random variables such that B takes values in a polynomial-sized set. We show that B is computationally ...

    • On Approximating the Entropy of Polynomial Mappings 

      Dvir, Zeev; Gutfreund, Dan; Rothblum, Guy N.; Vadhan, Salil P. (2017-09-14)
      We investigate the complexity of Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping p : F^n-> F^m, where F is a finite field, approximate the output entropy H(p(U_n)), where U_n is the uniform ...

    • On the (Im)possibility of Obfuscating Programs 

      Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil P.; Yang, Ke (Association for Computing Machinery (ACM), 2012)
      Informally, an obfuscator O is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is “unintelligible” in some ...

    • Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function 

      Haitner, Iftach; Nguyen, Minh-Huyen; Ong, Shien Jin; Reingold, Omer; Vadhan, Salil P. (Society for Industrial & Applied Mathematics (SIAM), 2009)
      We give a construction of statistically hiding commitment schemes (those in which the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions ...

    • Unconditional Relationships within Zero Knowledge 

      Ong, Shien Jin (2011-09-09)
      Zero-knowledge protocols enable one party, called a prover, to "convince" another party, called a verifier, the validity of a mathematical statement such that the verifier "learns nothing" other than the fact that the ...

    • Universal One-Way Hash Functions via Inaccessible Entropy 

      Haitner, Iftach; Holenstein, Thomas; Reingold, Omer; Vadhan, Salil P.; Wee, Hoeteck (Springer Verlag, 2010)
      This paper revisits the construction of Universal One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs, which also obtains better efficiency and ...