As a central technical building block, we 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. If we use this proof system in the Naor-Yung double encryption scheme, we obtain a tightly IND-CCA secure public-key encryption scheme from the Decision Linear assumption.
We point out that our techniques are not specific to public-key encryption security. Rather, we view our signature scheme and proof system as general building blocks that can help to achieve a tight security reduction.Category / Keywords: public-key cryptography / Tight security proofs, structure-preserving signatures, public-key encryption, Groth-Sahai proofs Publication Info: Crypto 2012 Date: received 1 Jun 2012, last revised 15 Apr 2013 Contact author: tibor jager at rub de Available format(s): PDF | BibTeX Citation Note: Remark added to Lemma 4. Version: 20130415:150417 (All versions of this report) Discussion forum: Show discussion | Start new discussion