Concise Multi-Challenge CCA-Secure Encryption and Signatures with Almost Tight Security
Benoit Libert, Marc Joye, Moti Yung, and Thomas Peters
Abstract
To gain strong confidence in the security of a public-key scheme, it
is most desirable for the security proof to feature a \emph{tight}
reduction between the adversary and the algorithm solving the
underlying hard problem. Recently, Chen and Wee (Crypto\,'13) described the first Identity-Based Encryption scheme with almost
tight security under a standard assumption. Here, ``almost tight''
means that the security reduction only loses a factor
-- where is the security parameter -- instead of a factor
proportional to the number of adversarial queries. Chen and Wee
also gave the shortest signatures whose security almost tightly
relates to a simple assumption in the standard model. Also recently,
Hofheinz and Jager (Crypto\,'12) constructed the first CCA-secure
public-key encryption scheme in the multi-user setting with tight
security. These constructions give schemes that are significantly
less efficient in length (and thus, processing) when compared with
the earlier schemes with loose reductions in their proof of
security. Hofheinz and Jager's scheme has a ciphertext of a few
hundreds of group elements, and they left open the problem of
finding truly efficient constructions. Likewise, Chen and Wee's
signatures and IBE schemes are somewhat less efficient than previous
constructions with loose reductions from the same assumptions. In
this paper, we consider space-efficient schemes with security almost
tightly related to standard assumptions. As a step in solving the
open question by Hofheinz and Jager, we construct an efficient
CCA-secure public-key encryption scheme whose chosen-ciphertext
security in the multi-challenge, multi-user setting almost tightly
relates to the DLIN assumption (in the standard model). Quite
remarkably, the ciphertext size decreases to group elements
under the DLIN assumption whereas the best previous solution required about group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) we develop here and which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive
non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla
and Roy (Asiacrypt\,'13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by under the Decision Linear assumption, by almost under the -LIN assumption, and it becomes only group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.
@misc{cryptoeprint:2014/743,
author = {Benoit Libert and Marc Joye and Moti Yung and Thomas Peters},
title = {Concise Multi-Challenge {CCA}-Secure Encryption and Signatures with Almost Tight Security},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/743},
year = {2014},
url = {https://eprint.iacr.org/2014/743}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.