Open Problems, Cryptography, Summer 2015

Below is a list of open problems proposed during the Cryptography program at the Simons Institute for the Theory of Computing, compiled by Ron Rothblum and Alessandra Scafuro.  Each problem comes with a symbolic cash prize.

  1. One-way permutations from a worst-case lattice assumption ($100 from Vinod Vaikuntanathan).
  2. Non-interactive zero-knowledge (NIZK) proofs (or even arguments) for NP from LWE ($100 from Vinod Vaikuntanathan).
  3. iO from LWE ($100 from Amit Sahai). This result would also solve problems (1) and (2). For (1) see construction and limitations and for (2) see argument system and proof system.
  4. Interactive proofs for languages computable in DTISP(t,s) (time t and space s), where the prover runs in time poly(t) and the verifier runs in time poly(s). The provers in known proofs of IP = PSPACE run in time exponential in 2poly(s) or 2O(s) ($100 from Yael Kalai).
  5. $20 per broken password challenge (from Jeremiah Blocki).
  6. (Dis)prove that scrypt requires amortized (space × time) = Ω(n2/polylog(n)) per evaluation on a parallel machine ($100 from Joël).
  7. A 3-linear map with unique encoding (i.e., without noise) for which “discrete log” is “plausibly hard” ($1000 from Dan Boneh).
  8. SZK = PZK, or in other words, transform any statistical zero-knowledge proof (SZK) into a perfect zero-knowledge proof (PZK) ($100 from Shafi Goldwasser).