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 sk

_{C}for every circuit C∈

**C.**

The holder of a secret key sk

_{C}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∈**C**and outputs a secret key sk_{C}.**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(sk**this deterministic algorithm takes as input the secret key sk_{C},y)_{C}and the ciphertext y and outputs C(x).

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 {C

_{i}(x

^{*}), sk

_{Ci}, C

_{i}} 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**=F

^{n }is 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

**C**as G

_{C,Δ}(x,Z

_{1},…, Z

_{S}) = C(x) + Σ

_{i∈ Δ }, where Z

_{i}∈ 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={mpk

_{1},…, mpk

_{N}}, whereas the master secret key is MSK={msk

_{1},…,msk

_{N}}.

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 (msk

_{i},G

_{C,Δ}) for all i∈ Γ and returns sk

_{C= }( Γ, Δ, {sk

_{C,Δ,i}}

_{i∈Γ})

_{ . }

_{1},… , x

_{n}), choose n random degree t polynomials μ

_{i}(.) such that x

_{i}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 y

_{i}for i=1,…,N.

To decrypt, compute a degree tD polynomial χ(.) such that χ(i)=SKQDec(sk

_{C,Δ,i,}, y

_{i}) for all i ∈ Γ, where SKQDec is the decryption algorithm of the single key query scheme. The decryption algorithm then outputs χ(0).