### Tightly Secure Signatures and Public-Key Encryption

Dennis Hofheinz and Tibor Jager

##### Abstract

We construct the first public-key encryption scheme whose chosen-ciphertext (i.e., IND-CCA) 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, our 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, 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.

Note: Remark added to Lemma 4.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2012
DOI
10.1007/978-3-642-32009-5_35
Keywords
Tight security proofsstructure-preserving signaturespublic-key encryptionGroth-Sahai proofs
Contact author(s)
tibor jager @ rub de
History
2013-10-29: last of 5 revisions
See all versions
Short URL
https://ia.cr/2012/311

CC BY

BibTeX

@misc{cryptoeprint:2012/311,
author = {Dennis Hofheinz and Tibor Jager},
title = {Tightly Secure Signatures and Public-Key Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2012/311},
year = {2012},
doi = {10.1007/978-3-642-32009-5_35},
note = {\url{https://eprint.iacr.org/2012/311}},
url = {https://eprint.iacr.org/2012/311}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.