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.
- One-way permutations from a worst-case lattice assumption ($100 from Vinod Vaikuntanathan).
- Non-interactive zero-knowledge (NIZK) proofs (or even arguments) for NP from LWE ($100 from Vinod Vaikuntanathan).
- 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.
- 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).
- $20 per broken password challenge (from Jeremiah Blocki).
- (Dis)prove that scrypt requires amortized (space × time) = Ω(n2/polylog(n)) per evaluation on a parallel machine ($100 from Joël).
- A 3-linear map with unique encoding (i.e., without noise) for which “discrete log” is “plausibly hard” ($1000 from Dan Boneh).
- SZK = PZK, or in other words, transform any statistical zero-knowledge proof (SZK) into a perfect zero-knowledge proof (PZK) ($100 from Shafi Goldwasser).