Paper 2017/525
Kurosawa-Desmedt Meets Tight Security
Romain Gay, Dennis Hofheinz, and Lisa Kohl
Abstract
At EUROCRYPT 2016, Gay et al. presented the first pairing-free public-key encryption (PKE) scheme with a tight security reduction to a standard assumption. Their scheme is competitive in efficiency with state-of-the art PKE schemes and has very compact ciphertexts (of three group elements), but suffers from a large public key (of about 200 group elements). In this work, we present an improved pairing-free PKE scheme with a tight security reduction to the Decisional Diffie-Hellman assumption, small ciphertexts (of three group elements), and small public keys (of six group elements). Compared to the work of Gay et al., our scheme thus has a considerably smaller public key and comparable other characteristics, although our encryption and decryption algorithms are somewhat less efficient. Technically, our scheme borrows ideas both from the work of Gay et al. and from a recent work of Hofheinz (EUROCRYPT, 2017). The core technical novelty of our work is an efficient and compact designated-verifier proof system for an OR-like language. We show that adding such an OR-proof to the ciphertext of the state-of-the-art PKE scheme from Kurosawa and Desmedt enables a tight security reduction.
Note: Corrected flaw in the three-way OR-proof construction. Corrected flaw in the OR-proof construction for k>1 (resulting in an efficiency decrease for k>1). Fixed typos and inconsistencies. Improved presentation.
Metadata
- Available format(s)
- Publication info
- A major revision of an IACR publication in CRYPTO 2017
- Keywords
- public key encryptiontight security
- Contact author(s)
-
Romain Gay @ ens fr
Dennis Hofheinz @ kit edu
Lisa Kohl @ kit edu - History
- 2017-10-24: last of 2 revisions
- 2017-06-05: received
- See all versions
- Short URL
- https://ia.cr/2017/525
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/525, author = {Romain Gay and Dennis Hofheinz and Lisa Kohl}, title = {Kurosawa-Desmedt Meets Tight Security}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/525}, year = {2017}, url = {https://eprint.iacr.org/2017/525} }