Karlsruhe Institute of Technology
The authors construct the first public-key encryption scheme whose chosen-ciphertext (i.e., INDCCA) security can be proved under a standard assumption and does not degrade in either the number of users or the number of ciphertexts. In particular, their scheme can be safely deployed in unknown settings in which no a-priori bound on the number of encryptions and/or users is known. As a central technical building block, they devise the first structure-preserving signature scheme with a tight security reduction. (This signature scheme may be of independent interest.) Combining this scheme with Groth-Sahai proofs yields a tightly simulation-sound non-interactive zero-knowledge proof system for group equations.