Paper 2016/829

Efficient KDM-CCA Secure Public-Key Encryption for Polynomial Functions

Shuai Han, Shengli Liu, and Lin Lyu

Abstract

KDM$[\mathcal{F}]$-CCA secure public-key encryption (PKE) protects the security of message $f(sk)$, with $f \in \mathcal{F}$, that is computed directly from the secret key, even if the adversary has access to a decryption oracle. An efficient KDM$[\mathcal{F}_{\text{aff}}]$-CCA secure PKE scheme for affine functions was proposed by Lu, Li and Jia (LLJ, EuroCrypt2015). We point out that their security proof cannot go through based on the DDH assumption. In this paper, we introduce a new concept _Authenticated Encryption with Auxiliary-Input_ $\mathsf{AIAE}$ and define for it new security notions dealing with related-key attacks, namely _IND-RKA security_ and _weak INT-RKA security_. We also construct such an $\mathsf{AIAE}$ w.r.t. a set of restricted affine functions from the DDH assumption. With our $\mathsf{AIAE}$, -- we construct the first efficient KDM$[\mathcal{F}_{\text{aff}}]$-CCA secure PKE w.r.t. affine functions with compact ciphertexts, which consist only of a constant number of group elements; -- we construct the first efficient KDM$[\mathcal{F}_{\text{poly}}^d]$-CCA secure PKE w.r.t. polynomial functions of bounded degree $d$ with almost compact ciphertexts, and the number of group elements in a ciphertext is polynomial in $d$, independent of the security parameter. Our PKEs are both based on the DDH & DCR assumptions, free of NIZK and free of pairing.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2016
Keywords
public-key encryptionkey-dependent messageschosen-ciphertext securityauthenticated encryptionrelated-key attack
Contact author(s)
dalen17 @ sjtu edu cn
History
2016-09-09: last of 2 revisions
2016-08-30: received
See all versions
Short URL
https://ia.cr/2016/829
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/829,
      author = {Shuai Han and Shengli Liu and Lin Lyu},
      title = {Efficient KDM-CCA Secure Public-Key Encryption for Polynomial Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/829},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/829}},
      url = {https://eprint.iacr.org/2016/829}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.