Paper 2018/974
Adaptively Secure and Succinct Functional Encryption: Improving Security and Efficiency, Simultaneously
Fuyuki Kitagawa and Ryo Nishimaki and Keisuke Tanaka and Takashi Yamakawa
Abstract
Functional encryption (FE) is advanced encryption that enables us to issue functional decryption keys where functions are hardwired. When we decrypt a ciphertext of a message $m$ by a functional decryption key where a function $f$ is hardwired, we can obtain $f(m)$ and nothing else. We say FE is selectively or adaptively secure when target messages are chosen at the beginning or after function queries are sent, respectively. In the setting of weakly-selective setting, function queries are also chosen at the beginning. We say FE is single-key/collusion-resistant when it is secure against adversaries that are given only-one/polynomially-many functional decryption keys, respectively. We say FE is sublinearly-succinct/succinct when the running time of an encryption algorithm is sublinear/poly-logarithmic in the function description size, respectively. In this study, we propose adaptively secure, collusion-resistant, and succinct (we call ``fully-equipped'') PKFE schemes for circuits. More specifically, we propose a generic transformation from weakly-selectively secure, single-key, and sublinearly-succinct PKFE for circuits into fully-equipped PKFE for circuits. We assume only the existence of weakly-selectively secure, single-key, and sublinearly-succinct PKFE for circuits. That is, our transformation relies on \emph{neither} concrete assumptions such as learning with errors \emph{nor} indistinguishability obfuscation. This is the first generic construction of fully-equipped PKFE that does not rely on indistinguishability obfuscation. As side-benefits of our results, we obtain the following primitives from weakly-selectively, single-key, and sublinearly-succinct PKFE for circuits: (1) laconic oblivious transfer (2) succinct garbling scheme for Turing machines (3) selectively secure, collusion-resistant, and succinct PKFE for Turing machines (4) low-overhead adaptively secure traitor tracing (5) key-dependent-message secure and leakage-resilient public-key encryption. We also obtain a semi-generic transformation from simulation-based adaptively secure garbling schemes into adaptively indistinguishable garbling schemes whose online complexity does not depend on the output length.
Note: Add an explanation about transforming laconic OT into updatable laconic OT.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Functional encryptionAdaptive securitySuccinctnessAdaptive garbled circuitLaconic oblivious transfer
- Contact author(s)
- ryo nishimaki @ gmail com,kitagaw1 @ is titech ac jp,yamakawa takashi @ lab ntt co jp
- History
- 2019-02-13: last of 3 revisions
- 2018-10-15: received
- See all versions
- Short URL
- https://ia.cr/2018/974
- License
-
CC BY