Advances in Functional Encryption for Secure Data Handling
Explore the evolution from Cryptomania to Obfustopia through Secret-Key Functional Encryption, Public-Key Encryption, and the power of Secret-Key Functional Encryption. Discover the significance of different encryption schemes such as Public-Key Functional Encryption, Secret-Key Functional Encryption, and more in ensuring data security and privacy.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
From Cryptomania to Obfustopia through Secret-Key Functional Encryption Nir Bitansky Ryo Nishimaki Alain Passel gue Daniel Wichs (MIT) (NTT) (ENS) (NEU)
public-key encryption ?????? ??????(?) ?? ? 1/19
functional encryption [SW 05] ?????? ? ?????(?) ??? ??? ?(?) ?(?) = 1/19
secret-key functional encryption [SW 05] ?????? ??????(?) ??? ??? ?(?) ?(?) = - FE:????(???) independent of ? ,#??? - weak FE: grows with either or both 1/19
the power of secret-key functional encryption 2/19
minicrypt cryptomania obfustopia weak PKFE, restricted PKFE weak SKFE PKFE [AJ 15] [BV 15] [GPSZ 16] [SS 10] [GVW 12] [SS 10] [GPSW 06] ... ? ? ? SKFE 3/19
minicrypt cryptomania obfustopia weak PKFE, restricted PKFE weak SKFE PKFE [AJ 15] [BV 15] [GPSZ 16] [SS 10] [GVW 12] [SS 10] [GPSW 06] ... evidences [AS 15] constructions SKFE 3/19
this work iO [AJ 15] [BV 15] [GPSZ 16] public-key functional encryption (plain) secret-key + public-key encryption functional encryption 4/19
? 6/19
its all about the size [BV15], [AJ15], [LPST16], [Lin16] ? compression, compression, compression... 7/19
exponentially-efficient iO (XiO) [LPST 16] ?(0?) ?(1?) XiO ? ? 2? 1 ? ? = poly ? for any ? = (1), XiO + LWE PKFE 8/19
exponentially-efficient iO (XiO) [LPST 16] ?(0?) ?(1?) XiO ? ? 2? 1 ? ? = poly ? for any ? = (1), XiO + LWE PKFE 8 /19
for any ? = (1), XiO + LWE PKFE 1-key succinct PKFE for Boolean functions [GKPVZ 13] 1-key sublinear PKFE for ?/???? [AJ 15],[BV 15] ? ? = ? ?1 ? ? ??? ?????(?) ?1 ? 9 /19
Boolean function ?????? ? ?? ?????(?,?) |???| = |?| 9 /19
Boolean function ?????? ? ?? ???[?] ? ??????,? |???| XiO ???1 ?= ?1 ? security follows immediately from that PKFE for Boolean functions and XiO via standard hybrid gymnastic... 9 /19
two steps [LPST 16] PKFE from XiO + LWE step 1: XiO from SKFE corollary: PKFE from SKFE and LWE 10 /19
two steps [LPST 16] PKFE from XiO + LWE step 1: XiO from SKFE step 2: (plain) PKE instead of LWE main result: corollary: PKFE from SKFE and (plain) PKE PKFE from SKFE and LWE 10 /19
XiO from SKFE ?: 0,1? {0,1} ?: 0,1?/2 0,1?/2 {0,1} ? ? ?(?||?) 2?/2 ?(?) 11 /19
XiO from SKFE ?: 0,1?/2 0,1?/2 {0,1} ? ?????(?) overall size: 2?/2 ???? ? ???( ||?) ? ?(?||?) 11/19
XiO from SKFE ?: 0,1?/2 0,1?/2 {0,1} ?????(?) ?????(?(?||.)) ?????(? (?||.)) ? ? overall size: 2?/2 ???? ? ???( ||?) ???? ?(?||?) ? (?| ? = ?(?||?) ??? = ?(?) 11 /19
two steps [LPST 16] LWE PKFE from XiO + LWE 1-key succinct PKFE for Boolean functions [GKPVZ 13] step 1: XiO from SKFE corollary: PKFE from SKFE and LWE 12/19
two steps [LPST 16] LWE PKFE from XiO + LWE step 2: 1-key succinct PKFE for Boolean functions 1-key succinct PKFE for Boolean functions [GKPVZ 13] from XiO and (plain) PKE step 1: XiO from SKFE corollary: main result: PKFE from SKFE and LWE PKFE from SKFE and (plain) PKE 12 /19
construction [SS 10] less weak PKFE weak PKFE from PKE XiO ?1 ? ????(1) ???? ??? |?| sufficient [AJ 15],[BV 15] 13/19
? ?(?) ? ? 14 /19
? ?(?) ? ? ?? ? 14 /19
?????(?) ??? 0??1 0?1 0?2 1 1 ??1 ?1 ?1 ?2 ??1 0??2 ?2 1 1 ??2 ??2 ~ ? = ? ? ?? ?? 0?? 1 ?? ???0???1 ?? ??? encrypted labels ?? 14 /19
?????(?) input garbler ??? circuit garbler 0??1 0?1 0?2 1 1 ??1 ?1 ?1 ?2 ??1 0??2 ?2 1 1 ??2 ??2 ~ ? = ? ?? 0?? 1 ?? ???0???1 ?? ??? encrypted labels ?? garbled circuits are decomposable! 14 /19
input garbler circuit garbler 0??1 0?1 0?2 1 1 ??1 ?1 ?2 XiO 0??2 1 1 ??2 ~ ?~ ?? ?? ? ?? ? ?,? ?? ?? 0?? 1 ?? ?? ???0???1 encrypted labels ?? garbled circuits are decomposable! 14 /19
input garbler circuit garbler 0??1 1 ??1 XiO 0??2 1 ?? ??2 ? (?,?) ??? ?~ ? ?? ?? ? ?,? ?? ?? ?? ?? ???0???1 encrypted labels ?? garbled circuits are decomposable! 14 /19
?????(?) ??? what about security? ?1 ? if good enough XiO built from ?(1)-input SKFE (obtained from 1-input SKFE via [BKS 16]) ? 2?/? ? = ?(1) 1-input SKFE 2-input SKFE 2?/2 ??? 2?/3 ??? 15 /19 2?/3 ??? 2?/2 ???
?????(?) ?????(? ) ? ??? ??? ? ? = ?(? ) to rely on XiO security: need ???? have ???? ? ??? ? ? ? ??? ? ? ? want to rely on indistinguishability of decomposable GC 16 /19
problem: compressing garbled circuit hybrids related: succinct randomized encodings compress to ????? (or ???? ) [BGLPT 15] too much: ???? |?| ?? |?| other SREs [KLW 15, CH 16, ] not with XIO solution: strategy from adaptive garbled circuits compress to ???? ?????? [HJOSW 16] 17 /19
two steps step 2: 1-key succinct PKFE for Boolean functions from XiO and (plain) PKE step 1: XiO from SKFE main result: PKFE from SKFE and (plain) PKE 18 /19
on removing PKE negative result: [AS 15] - no black-box construction from SKFE to PKE - even assuming subexponential SKFE... positive result: [this work] - PKE from subexponential SKFE and OWF - only quasi-polynomially secure... (not enough for iO) - non-black box transform [BKS 16] 19 /19
