Report

eill Adam O’Neill Georgetown University Joint work with Dana Dachman-Soled (Univ. of Maryland), Georg Fuchsbauer (IST Austria), and Payman Mohassel (Univ. of Calgary) 1 The talk will consist of three parts: Definitions. Randomness-recovering PKE and enhanced chosen-ciphertext (ECCA) security. Constructions. Achieving ECCA security from adaptive trapdoor functions. Applications. Public-key encryption with non- interactive opening (time permitting). 2 3 In encryption, we typically think of decryption as a way for the receiver to recover a sender’s message. In a randomness-recovering scheme, the receiver is able to recover a sender’s random coins as well. 4 llision Probability Argument Collision Probability Argument Gen Collision Enc Dec Rec Probability Argument Collision Probability Argumen KeyGen Gen Enc Dec pk Dec Rec Abstract Abstract Enc Enc (pk, sk) Dec public-key encryption (RRCollision Probability Argument Collision Probability Argument sk Collision Probability Argument PKE) of fourAbstract algorithms: llision Probability Argument (pk, sk)scheme consists Abstract K Enc A randomness-recovering Abstract sk Abstract K eyGen Enc Dec K Rec Dec Enc, Dec, Dec Rec) (KeyGen, Dec 1k K eyGen Enc Dec Rec sk K eyGen Enc(pk,Dec Rec sk k sk) 1 K eyGen Enc Dec Rec m Abstract K 1k r Abstract pk K Abstract c Abstract PRF K pk f r −1 sk pk sk Dec Recx K eyGen Enc x + i mod M m K eyGen Enc Dec Rec K eyGen Enc Dec cRec Dec c sk r sk k r sk 1 Enc(f , b): + i mod M r 5 Abstract sk k 1 We require that Enc(pk, m; r ) = c. We say that randomness recovery is unique if in addition r f=− r1 . Some applications of RR-PKE require uniqueness, for r others (e.g. PKENO) non-unique is OK as long as Enc(f , b): there is no decryption error. x ←⊥ While hc(x) = b do: $i x ← { 0, 1} k 6 Abstract Abstract Collision Probability Argument Abstract Collision Probability Argu Abstract Enc(pk, m; r Dec ) = c Rec eyGen Enc Abstract Encb (pk, sk) K eyGen Enc Dec Rec Require c = c∗ c∗ Enc(pk, = Enc(pk, m; mb) r Abstract ) = c(pk, sk) Repeats! K eyGen Enc Dec Rec Enc(f , b): $ (m0 , m 1) x ← { 0, 1} k Dec(sk, c) b Enc(f , b): Return (f (x), hc(x)) Enc sk sk $ k x← pk{ 0, 1} Return (f (x),Verify(pk, hc(x)) c, m, r ) : Enc(f , b): Hard to guess b Encb Verify(pk, c, m, r ) : 7 Abstract Abstract Collision Probability Argument Abstract Collision Probability Arg Collision Probability Argu Abstract Dec∗ Enc(pk, m; r Dec ) = c Rec eyGen Enc Abstract Encb (pk, sk) Require c = c∗ c∗ = Enc(pk, m Enc(pk, m;b) r Abstract )= c Abstractb Enc Repeats! K eyGen Enc Dec Rec Enc(f , b): Rec(sk, c) $ (m0 , m 1) k x ← { 0, 1} Dec(sk, c) b Enc(f , b): (m 0 , m 1) Return (f (x), hc(x)) Enc sk $ k x← pk{ 0, 1} Return (f (x),Verify(pk, hc(x)) c, m, r ) : Encb Enc(f , b): Hard to guess b Encb Verify(pk, c, m, r ) : 8 Abstract Abstract Abstract Abstract Theorem. Let (KeyGen, Enc, Dec, Rec) be a CCA-secure RR-PKE scheme. Then there is a modified scheme (KeyGen , Enc, Dec , Rec) that remains CCA-secure but K eyGen Enc, Dec , Rec) K eyGen Enc, Dec , Rec) is not ECCA-secure. PRF Proof idea: (pk, sk) K eyGen : Dec (sk, c): Dec $ ∗ If Enc(pk, 0; c) = c (pk, sk) ← K eyGen $ Then return sk c∗ ← Enc(pk, 0) sk Else return Dec(sk, c) Return ((pk, c∗ ), sk) K K eyGen To prove CCA-security 1; now, :assuming K eyGen : switch c* to encrypt no decryption 1kerror, it’s impossible to make Dec’ return sk! 9 Abstract Abstract Theorem. Let (KeyGen, Enc, Dec, Rec) be a CCA-secure RR-PKE scheme. Then there is a modified scheme (KeyGen , Enc, Dec , Rec) that remains CCA-secure but is not ECCA-secure. PRF (pk, sk) Motivates finding new (or Decexisting) constructions that can be proven ECCA-secure! sk K 1k 10 11 Abstract Abstract Abstract f A trapdoor function generator F is such that (f , f −1 $ ) ← F (1k ) where f describes a function on k-bits and f − 1 its inverse. Dec (sk, c): If Enc(pk, 0; c) = c∗ Dec (sk, c): ∗ f −1 Then0;return If Enc(pk, c) = sk c Dec (sk, c): Else return c) Then return sk Dec(sk, If Enc(pk, 0; c) = c∗ Else return Dec(sk, c) Then return sk K eyGen : Else return Dec(sk, c KeyGen : Dec (sk, c): 12 If Enc(pk, 0; c) = c∗ Abstract Rec(sk, c) f , f (x) Hard to guess x 13 $ (pk, sk) ← K eyGen Rec(sk, c) Introduced by [KMO’10] Enc(pk, Constructions m b) from lossy [PW’08] and f −1 correlated-product [RS’09] TDFs. Require Implies CCA-secure PKE. y = y∗ r (m 0 , m 1) Repeats! (f , y = f (x)) Enc(f , b): $ x ← { 0, 1} k Return (f (x),Enc(f hc(x)) , b): x←⊥ (pk,xc, m, r ) : HardVerify to guess While hc(x) = b10do: Theorem. ATDFs implies (unique) ECCA-secure RR-PKE. Previously [KMO’10] constructed CCA-secure PKE from ATDFs, so let’s start there. The approach of [KMO’10] is as follows: First construct a “one-bit” CCA-secure scheme from ATDFs. Then compile the “one-bit” scheme to a “many-bit” scheme using [MS’09]. 15 Abstract Abstract Let F be a TDF generator with hardcore bit hc . Define the one-bit encryption algorithm via: c (sk, c): If Enc(pk, 0; c) = c∗ Then return sk Else return Dec(sk, c) f −1 Hardcore bit Enc(f , b): ⊥ But trivially assumed K eyGen : malleable no matter whatxis← While hc(x) = b do: about the hardcore bit $ x ← { 0, 1} k 16 Abstract Abstract f −1 Let F be a TDF generator with hardcore bit hc. Define the one-bit encryption algorithm via: Enc(f , b): Rejection sampling − 1 x←⊥ f c (sk, c): While hc(x) = b do: $ If Enc(pk, 0; c) = c∗ x ← { 0, 1} k Then return sk Return f (x) Else return Dec(sk, c) Enc(f ,because: b): But this approach is not K sufficient for us eyGen : x ← ⊥ K eyGen : • It gives non-unique randomness recovery While hc(x) = b do: • [MS’09] compiler preserves neither randomness $ 17 recovery nor “enhanced” security x ← { 0, 1} k Abstract Abstract Collision Probability Argument Abstract CCA security relative toCollision a relation R Probability on ciphertexts. Argu Abstract Enc(pk, m; r Dec ) = c Rec eyGen Enc Abstract K eyGen Enc Dec Rec Require c = c∗ AND R(c∗ , c) = 0 Encb ∗ Abstract c = Enc(pk, m ) Enc(pk, m; r ) = c b (pk, sk) (pk, sk) [HLW’12] (building on [MS’09]) shows that any Repeats! KDCCA-secure eyGen Encscheme Dec (for Rec Enc(f , b): a “suitable” relation R) Enc(f , b): $ k can be compiled into a CCA-secure scheme. x ← { 0, 1} $ (m0 , m 1) x ← { 0, 1} k Return (f (x), hc(x)) Dec(sk, c) b Enc(f , b): Return (fEnc (x), hc(x)) sk sk $ k x← Verify(pk, c, m, r ) : pk{ 0, 1} Verify(pk, m, r ) : Return (f (x),c,hc(x)) Enc(f , b): Hard to guess b Encb 18 We now construct ECCA (uniquely) RR-PKE from ATDFs in three steps: Show the “naïve” one-bit scheme is (1) randomnessrecovering and (2) “enhanced” DCCA-secure. Get a multi-bit “enhanced” DCCA-secure RR-PKE scheme by showing (1) and (2) are preserved under parallel composition. Finally, show the compiler of [HLW’12] also preserves both (1) and (2) while boosting DCCA to CCA security. 19 20 Allows a receiver to non-interactively prove a ciphertext c decrypts to a claimed message m. We observe that security of this suggestion fundamentally requires ECCA-security! Our techniques lead to the first secure (and even efficient) instantiations. Suggestion of [DT’08]: use RR-PKE where the recovered coins are the proof. 21 We gave definitions, constructions, and applications of enhanced CCA (ECCA) security. Not covered (see paper): Using ECCA to prove equivalence of tag-based and standard ATDFs. Efficient constructions of ECCA and PKENO. Open problems: Relation between ATDFs and TDFs. Other ECCA-secure constructions (e.g. using non- black-box assumptions?) 22 23