4 Homomorphic-based BKEM

Pr[Exp^IND_BKEM(A, r) = 1]−1/2 ,

where the experimentExp^IND_BKEM(A, r)is given in Figure6(right).

The valuerrepresents the number of recipients in the OAGKE protocol of BDGJ – in practice this will often be fairly small, and certainly bounded by the number of users of the system.

We now show how to turn a homomorphic encryption scheme with certain properties into a BKEM, and analyze the security requirements of such a

Exp^IND-^CPA

PKE (A) : b←− {^$ 0,1} (pk,sk)←KGPKE

(m0,m1,state)←− A^$ (pk) C_b ←Encpk(mb)

b⁰ ← A(state, C_b) returnb⁰ =^? b

Exp^IND_BKEM(A, r) : b←− {^$ 0,1} (ek,dk)←KG (C, k1)←Encap_ek k₀ ←− K^$ F

forj∈ {1, . . . , r}do ( ˜C_j,uk_j)←Blindek(C)

˜k_j ←Decap_dk( ˜C_j)

b⁰← A(ek, C, k_b,{( ˜C_j,k˜_j)}1≤j≤r) returnb⁰ =^? b

Figure 6: IND-CPA experiment Exp^IND-^CPA

PKE (A) for a PKE scheme PKE(left). Indistinguishability experiment Exp^IND_BKEM(A, r)for a BKEM schemeBKEM(right).

BKEM. We eventually prove that the homomorphic-based BKEM is post-quantum secure as long as the underlying homomorphic encryption scheme is post-quantum secure.

4.1 Generic homomorphic-based BKEM

We look for PKE schemes with the following homomorphic property: sup-poseC andC⁰ are two ciphertexts, thenDecsk(C⊕1C⁰) = Decsk(C)⊕2

Decsk(C⁰), where⊕1 and⊕2denote two group operations.

We construct blinding and unblinding algorithms using this homomor-phic property. Suppose the underlying PKE scheme has1−-correctness.

To blind an encapsulationC(with corresponding file encryption keyk) the Blindalgorithm creates a fresh encapsulationC⁰(with corresponding blind-ing valuek⁰) using theEncap_ek algorithm, the blinded encapsulationC˜ is computed asC˜ ←C⊕1C⁰. The unblinding keyuk is the inverse element of k⁰with respect to⊕2, that is,uk ← k⁰⁻¹. The blinding algorithms outputs C˜ and uk. The decapsulation algorithm can evaluate the blinded encap-sulation because of the homomorphic property. The blinded key ˜kis the output of this decapsulation algorithm, that is, ˜k ← Decap_dk( ˜C). Hence, k˜ = k⊕2 k⁰ with probability1−2+². To unblind k˜ the unblinding

algorithm outputs˜k⊕2uk, which iskexcept for probability2−², and so the BKEM scheme has(1−2+²)-correctness. Formally, we define the BKEM scheme constructed above as follows.

Definition 10(Homomorphic-based BKEM). LetBKEMbe a PKE-based BKEM, as in Definition 7. Suppose the underlying public key encryp-tion scheme is a homomorphic encrypencryp-tion schemeHE= (KGHE,Enc,Dec) such that for any ciphertextsC, C⁰ ∈ Cand any key pair(sk,pk)←−^$ KGHE

it holds that

Decsk(C⊕1C⁰) =Decsk(C)⊕2Decsk(C⁰),

where(M,⊕2)is the plaintext group and(C,⊕1) is the ciphertext group.

Furthermore, let the blinding and unblinding algorithms operate according to Figure7. We call such a schemeBKEMahomomorphic-based BKEM.

Blindek(C) :

(C⁰, k⁰)←Encap_ek C˜ ←C⊕1C⁰ uk ←k⁰⁻¹ returnC,˜ uk

Unblinduk(˜k) : k←k˜⊕2uk returnk

Figure 7: Blinding and unblinding algorithms of the homomorphic based BKEM.

We stress that all BKEM schemes we consider in the rest of this paper are homomorphic-based BKEMs. The homomorphic encryption scheme HEdoes not need to be fully homomorphic, since we only need one opera-tion in the blinding algorithm: a somewhat group homomorphic encrypopera-tion scheme is sufficient.

4.2 Security requirements

In the indistinguishability game IND for BKEMs the adversary A has r blinded samples. If the decryptions of blinded encapsulations output the correct blinded keys, then theser blinded samples are the following two sets:{C˜_i=C⊕1C_i⁰}1,...,rand{˜k_i =k⊕2k⁰_i}i=1...r, where the encapsula-tion isCand the real file encryption key isk. We want the blinded samples

and the encapsulation to be random looking such that the combination of all these values does not reveal any information about the underlying file encryption keykthat is being transported.

First, we show how to choose the blinding valuesk_i⁰to make the blinded keys˜k_i look random. Then, we show how to make the blinded encapsula-tionsC˜_ilook random, which is achievable whenC˜_ilooks like a fresh output of the encapsulation algorithm: this idea is similar to circuit privacy [24].

Finally, we show how anIND-CPA-secure HE scheme ensures that the en-capsulation does not reveal any information about the file encryption key.

With these steps in place, we provide the main theorem in this paper stating how to achieve an INDsecure BKEM scheme. In particular, if the under-lying HE scheme is post-quantumIND-CPAsecure then the corresponding homomorphic-based BKEM scheme is post-quantumINDsecure.

Random-looking blinded keys. We want the blinded key to look like a random element of the space containing blinded keys. In theINDgame the adversary is given several blinded keys of the form k˜ = k⊕2 k⁰, where k is the file encryption key andk⁰ is a blinding value, and wishes to gain information aboutk.

Letkbe sampled uniformly at random from the file encryption key set, denotedKF, and letk⁰ be sampled uniformly at random from the blinding value set, denotedKR. We would like that the size ofKF is large enough to prevent a brute force attacker from guessingk, say|KF|= 2^λ for some security parameterλ. IfKRis a small set then the value of any blinded key k˜=k⊕2k⁰will be located within a short distance aroundk, so the adversary can successfully guesskwith high probability. We always assume thatKR

is at least as large asKF.

If a given blinded keyk˜can be expressed as a result of any file encryp-tion key kand a blinding valuek⁰, with respect to an operation, then our goal is to ensure that the adversary cannot get any information of the true file encryption key hidden ink: ideally we wish it to be indistinguishable˜ from a random element.

Definition 11(-blinded blinded key). LetBKEMbe a blinded KEM with blinded key set KB. Let k be sampled uniformly random from the file encryption key set KF and letk⁰ be sampled uniformly random from the blinding value setKR. We define a -blinded blinded key set S := {˜k ∈

KB | ∀k∈ KF,∃1k⁰ ∈ KRsuch that˜k=k⊕2k⁰}: we say thatBKEMhas -blinded blinded keys if

Prh

˜k=k⊕2k⁰∈S|k←− K^$ F, k⁰ ←− K^$ R

= 1−.

Suppose the adversary is given any number of-blinded blinded keys fromSwith the same underlying file encryption keyk. By the definition of the-blinded blinded set the file encryption keyk can be any value in KF and all values are equally probable. In other words, guessingk, given -blinded blinded keys, is the same as guessing a random value fromKF. To prevent giving the adversary a better chance at guessing the keyk we wish the blinded keys to be located inside the-blinded blinded key set S with high probability, which means we wantto be small.

Fresh-looking blinded encapsulations. In theINDgame for BKEMs the adversaryA gets r blinded samples and has knowledge of the set{C˜_i = C⊕1C_i⁰}1,...,r, whereC is an encapsulation of a file encryption keykand C_i⁰ is an encapsulation of a blinding value. We cannot guarantee that the set of the blinded encapsulations do not reveal any information about the encapsulationC. However, if each of these blinded encapsulations looks like a fresh output of the encapsulation algorithm then they are indepen-dent and random-looking compared to the encapsulationC. Therefore we want this set to be indistinguishable from the output set of the encapsulation algorithm.

Definition 12(-blinded blinded encapsulation). LetHE-BKEM be a ho-momorphic based BKEM. Let ek be any encapsulation key and C0 be an encapsulation with the underlying file encryption keyk₀. We say that HE-BKEM has -blinded blinded encapsulation if the statistical distance between the following distributions is at most:

X={C0⊕1C⁰ |k⁰ ←− K^$ R, C⁰ ←Enc_ek(k⁰)}, Y ={C|k⁰ ←− K^$ R, C←Encek(k0⊕2k⁰)}.

This property ensures that the output of the blinding algorithm looks like a fresh encapsulation except for probability. Note that the BKEM

constructions in [10],DH-BKEM [10, Section 4.1] and RSA-BKEM [10, Section 4.2], both have 0-blinded blinded encapsulation.

In most fully homomorphic encryption schemes the product of two ci-phertexts is much larger in size compared to the sum of two cici-phertexts, hence, it is easier to achieve-blinded blinded encapsulation for one addi-tion compared to one multiplicaaddi-tion. In our construcaddi-tions we use addiaddi-tion.

Indistinguishability of BKEMs. Furthermore, if we want to achieve in-distinguishability of blinded KEMs. We require the underlying homomor-phic encryption scheme have some kind of semantic security to protect the message (the file encryption key) in the ciphertext (the encapsulation).

Theorem 5(Main Theorem). For negligible₃, letBKEMbe a homomor-phic based BKEM designed as in Definition 10 from a (1− ₃)-correct homomorphic encryption schemeHE. Let the file encryption keykand the blinding valuek⁰ be sampled uniformly random from the large setsKF and KR, respectively. Suppose BKEM has ₁-blinded blinded encapsulations and2-blinded blinded keys. For any adversaryAagainstBKEMgetting r blinded encapsulations and their blinded decapsulation samples, there exists anIND-CPAadversaryBagainstHEsuch that

Adv^IND_BKEM(A, r)≤2(r+ 1)(₁+₂+₃) +Adv^IND-^CPA

HE (B) Proof. The proof of the theorem consists of a sequence of games.

Game 0

The first game is the experimentExp^IND_BKEM(A, r), given in Figure6(right).

LetE0be the event that the adversary’s guessb⁰ equalsb(and letEibe the corresponding event for Gamei). From Definition9we have that

Adv^IND_BKEM(A, r) = 2|Pr[E₀]−1/2|. Game 1

We consider a modified game which is the same as Game 0 except that blinded key given to the adversary is the sum of the file encryption key and the blinding value instead of the decryption of the blinded encapsulation.

More precisely, supposeCis the encapsulation with corresponding file en-cryption keyk. For 1 ≤ j ≤ r, letC_j⁰ +C is the blinded encapsulation where C_j⁰ is a fresh encapsulation with corresponding blinding value k_j⁰. WhenAqueries for the blinded key of userj, the game outputsk⊕2k⁰_j.

By the homomorphic property of PKE, ifCandC₁⁰, . . . , C_r⁰ all decrypt to the correct messages, then the output of blinded keys are the same in both Game1and Game0. Hence the difference between Game1and Game0is upper bounded by the decryption error of PKE as follows.

Pr[E₁]−Pr[E₀]≤1−(1−₃)^r+1 ≈(r+ 1)₃. Game 2

We consider a modified game which is the same as Game 1 except that blinded encapsulation and blinded key pairs given to the adversary are now independent and random compared to the file encryption key. More pre-cisely, for1≤j≤r:

• When Aqueries the blinded encapsulation of userj, the game first chooses a random -blinded blinded key (Definition 11), ˜k_j ←−^$ S, and computes an encapsulation of this random key,C˜_j ←Encek(˜k_j), which is given toA.

• WhenAqueries for the blinded key of userj, the game outputs˜k_j. Step 1. We first prove that a real pair of blinded key and blinded encap-sulation in Game1is(₁+₂)-statistically close to the modified values in Game2.

Supposek₀ ∈ KF is the file encryption key andC₀←Encek(k₀)is the encapsulation withk₀, letX = {(k₀⊕2k⁰, C₀⊕1C⁰) | k⁰ ←− K^$ R, C⁰ ← Enc_ek(k⁰)}be the statistical distribution of the real pair of blinded key and blinded encapsulation output in Game1, andY = {(˜k,C)˜ |k˜ ←−^$ S,C˜ ← Encek(˜k)} be the statistical distribution of the modified values output in Game 2. We define a middle distribution Z = {(k₀ ⊕2 k⁰, C) | k⁰ ←−^$ KR, C ← Encek(k₀ ⊕2k⁰)}.We compute the statistical distance between XandY as follows.

∆(X, Y)≤∆(X, Z)+∆(Z, Y)

Note that in (1) we split the summation into two parts, namely˜k ∈ S and˜k 6∈ S. Fork˜ ∈ Swe have Pr[Z= (˜k,C)˜ |k /˜ ∈ S]·Pr[˜k /∈ S] = 0, and for k˜ 6∈ S we have Pr[Z = (˜k,C)˜ | k˜ ∈ S]·Pr[˜k ∈ S] = 0and Pr[Y= (˜k,C)] = 0. Furthermore, (2) holds because distributions˜ ZandY over setSare equal. Forrsamples:

Pr[E₂]−Pr[E₁]≤r(₁+₂).

Step 2. Next, we claim that there exists an adversaryBagainstIND-CPA security ofHEsuch that

We construct a reduction B that plays the IND-CPA game by running A, that simulates the responses of Game2toAas follows.

1. Bflips a coinb←− {^$ 0,1},

2. Bqueries itsIND-CPAchallenger to get the public key of itsIND-CPA game, and forwards this public key as the encapsulation key toA, 3. B simulates the encapsulation by randomly choosing two group key

k0, k1, sends challenge query with input(k0, k1)to itsIND-CPA chal-lenger, and forwards the responseCtoA,

4. Bsimulates the output ofBlindandDecapby using theEncap algo-rithm.Bsamplesk˜←−^$ S, computesC˜ ←Encek(˜k), and outputsC˜as the blinded encapsulation and k˜as the decapsulation of the blinded encapsulation,

5. WhenAasks for a challenge,Bsendsk_btoA,

6. AfterAreturnsb⁰,Bsends1⊕b⊕b⁰ to the challenger.

If the challenge ciphertextBreceived inExp^IND-^CPA

HE (B)isC_b, thenB perfectly simulates the inputs ofAin Game2when the output of the key is a real key. Otherwise (the challenge ciphertextBreceived inExp^IND-^CPA

HE (B) isC₁-b),k_bis a random key toAandBperfectly simulate the inputs ofA in Game2when the output of the key is a random key.

Remark 1. As a specific case of Theorem5, the DH-BKEMconstruction of BDGJ has 0-blinded blinded encapsulations and 0-blinded blinded keys, and the indistinguishibility ofDH-BKEM is upper bounded by DDH ad-vantage (defined in the real-or-random sense instead of left-or-right). That is

Adv^IND_DH-^BKEM(A, r)≤Adv^DDH(B).

This observation matches with the result of Boyd et al. [10, Theorem 1].

In document Cryptographic Tools for Cloud Security (sider 78-86)