Tuesday, January 29, 2013

Study Group: Functional Encryption


Last week's study group was on Functional Encryption and was given by  Georg and Joop.

In traditional Public-Key Encryption (PKE), a user Alice encrypts a message x using the public key of the recipient Bob. Bob then uses his corresponding secret key to decrypt the ciphertext y to recover the message x. In some scenarios, the recipient of the ciphertext is not yet known at the time of the encryption or there are more than one recipient who should be able to decrypt the ciphertext, e.g. according to some policy. Functional Encryption (FE), formalized recently by Boneh, Sahai and Waters [PDF], is a generalization of many recent encryption primitives, e.g., Attribute-Based Encryption (ABE) [PDF] and Predicate Encryption (PE) [PDF] which extend traditional PKE to provide fine-grained access to encrypted data.
A FE scheme for a family of circuits C assigns a secret key skC for every circuit  C∈C.
The holder of a secret key skC is able to decrypt a ciphertext y to obtain C(x) and learns nothing more about x.
An FE scheme is formally defined by four algorithms (Setup, KeyGen, Enc, Dec) which are defined as follows:
  • Setup(1λ) this PPT algorithm takes a security parameter λ as input and outputs a pair of master public\secret keys (mpk,msk).
  • KeyGen(msk,C) this PPT algorithm takes as input the master secret key msk and a circuit C∈ and outputs a secret key skC.
  • Enc(mpk,x) this PPT algorithm takes as input the master public key mpk and a message x from the message space X and outputs a ciphertext y.
  • Dec(skC,y) this deterministic algorithm takes as input the secret key skC and the ciphertext y and outputs C(x).
Gorbunov, Vaikuntanathan and Wee [PDF] provide a construction for the class of all polynomial-size circuits secure under a simulation-based bounded collusion definition in which the adversary can make bounded number of KeyGen queries and gets a single challenge ciphertext. The definition ensures that any information that the adversary learns from the keys and ciphertext can be obtained by a simulator from only the keys and the output of the circuit.

In the real world the challenge ciphertext is produced by encrypting the challenge message x* using mpk, whereas in the ideal world, the simulator is equipped with the length of the the challenge message as well as {Ci(x*), skCi, Ci} resulting from the q KeyGen queries the adversary is allowed to make. In the adaptive variant, the adversary is allowed to make further KeyGen queries after it has received the challenge ciphertext.
 Gorbunov, Vaikuntanathan and Wee [PDF]  show that their simulation-based definition for a single message implies the indistinguishability definition in both the adaptive and non-adaptive cases. The single-message indistinguishability definition also  implies the many-messages indistinguishability definition in both the adaptive and non-adaptive settings. However, while the non-adaptive single-message simulation definition implies the many-messages non-adaptive simulation definition,  the same does not hold for the adaptive case.

The idea of their construction for the NC1 class of circuits and a message space X =Fis based on a scheme that is secure under a single key query and is summarized as follows:
The system parameters are  t, v, N and S.
 A new family G is defined from as GC,Δ(x,Z1,…, ZS) = C(x) + Σi∈ Δ , where Zi∈ F and Δ ⊆[S].
The setup algorithm independently runs N times the single key query Setup algorithm for the same circuit family. The master public key is then set to MPK={mpk1,…, mpkN}, whereas the master secret key is MSK={msk1,…,mskN}.
The KeyGen algorithm then on input (C,MSK) randomly chooses a set Γ ⊆  [N] of size tD+1, where D is the degree of the circuits. It also chooses a set  Δ⊆  [S]  of size v. It then runs the KeyGen of the  single key query scheme with input (mski,GC,Δ ) for all i∈ Γ and returns skC= ( Γ, Δ, {skC,Δ,i}i∈Γ) . 
To encrypt a message (x1,… , xn), choose n random degree t polynomials μi(.) such that xi is the constant term in polynomial μi(.). Also, S random degree tD polynomials ζ(.) whose constant term is 0 are chosen. To encrypt the message encrypt (μ1(i),…μn(i),ζ1(i),…ζS(i)) to obtain ciphertexts yi for i=1,…,N.
To decrypt, compute a degree tD polynomial χ(.)  such that  χ(i)=SKQDec(skC,Δ,i,, yi) for all i ∈ Γ, where SKQDec is the decryption algorithm of the single key query scheme.   The decryption algorithm then outputs  χ(0).

No comments:

Post a Comment