Instructor: Daniele Micciancio (UCSD)

Functional Encryption

A Functional Encryption (FE) scheme is defined by three efficient algorithms (KeyGen,Eval,Enc,Dec) where

• KeyGen(t) is a probabilistic key generation algorithm that, on input a security parameter t, outputs a pair of keys (pk,sk)
• Enc(pk,msg) is a probabilistic encryption algorithm that on input a public key pk and a message msg, outputs a ciphertext ct
• Fun(sk,f) is a function evaluation algorithm that on input the (master) secret key sk and a function f, outputs a derived key fk.
• Dec(fk,ct) is a (typically deterministic) decryption algorithm that on input a derived key fk and ciphertext ct, outputs the value of the fuction at the encrypted message f(msg).

The algorithms should satisfy the following correctness condition:

Pr{ Dec(Fun(sk,f),Enc(pk,m)) = f(m) | (pk,sk) ← KeyGen(t) } ≡ 1

Warning: In most papers, the key generation algorithm KeyGen is called Setup, and the name KeyGen (or KDer) is used for the functional key derivation algorithm.

Functional encryption schemes may be parametrized by the class of functions that can be passed as input to the key derivation algorithm, as well as the method to represent these functions. For example, if we restrict F = id to just the identity function, then we get the standard notion of public key encryption, where Fun(sk,id) = sk outputs the unmodified secret key.

Security

As for PKE, one can define both an indistinguishability and simulation based notion of security, and each comes in several variants depending on the order in which the adversary can issue its queries. Here we focus on a specific non-adaptive formulation, and then describe some of its variations.

Intistinguishability under chosen plaintext attack (IND-CPA). For any functional encryption scheme FE = (KeyGen,Fun,Enc,Dec) and adversarial algorithm A = (A0,A1) define the following experiment (parametrized by a bit b):

GameFE[b,FE,A] = { (pk,sk) ⟵ KeyGen();
                    (msg[0], msg[1], z) ⟵ A0(pk);
                    ct ⟵ Enc(pk,msg[b]);
                    A1{O(.)}(z,ct) }
where O(f) = if (f(msg[0]) = f(msg[1])) then Fun(sk,f) else nothing.

(Notation A{O(.)}(x) represents an algorithm A taking x as input, and with oracle access to O(.).) The advantage of adversary A against the scheme is defined as AdvINDFE[FE,A] = GameFE[0,FE,A] - Game[1,FE,A]. The scheme FE is IND-secure if any efficient (probabilistic polynomial time) adversary A has negligible advantage AdvINDFE[A,E] ≡ 0.

Informally, the above definition says that no adversary can efficiently tell the difference between the encryption of any two messages m₀, m₁, without getting a functional key that tells the two messages apart.

Semantic Security under chosen plaintext attack (SIM) Α functional encryption scheme FE=(KeyGen,Fun,Enc,Dec) is semantically secure if for any PPT adversary A there is a PPT simulator (SimC, SimF) such that for any PPT sampling algorithm M, the probability distributions

Real  = { A{Fun(sk,.)}(z,ct) | (pk,sk) ⟵ KeyGen(t); (msg,z) ⟵ M(pk); ct ⟵ Enc(pk,msg)}
Ideal = { A{O(.)}(z,ct)   | (pk,sk) ⟵ KeyGen(t); (msg,z) ⟵ M(pk); (ct,w) ⟵ SimC(pk,sk,|msg|) }
where O(f) = SimF(sk,f,f(msg)).

are computationally indistinguishable, that is for any PPT predicate D (the distinguisher) we have Pr{D(Real)} ≡ Pr{D(Ideal)}

The above definitions are semi-adaptive, in the sense that the challenge message(s) must be chosen before seeing any functinal decryption key. One may also consider

• a fully non-adaptive definition where the message(s) must be chosen even before seeting the public key
• an adaptive definition where the adversary may require function keys before choosing the challenge message(s)

In the most general setting, the adversary/simulator may mix/interleave encryption and key derivation queries arbitrarily, and also ask for the encryption of multiple challenge messages.

Warning: In the literature, the non-adaptive notion of security is called adaptive, in reference to the fact that the function queries may depend on the ciphertext. Similarly, the term 'non-adaptive' is occasionally used for security definitions where the adversary is not allowed to make any key queries after seeing the challenge ciphertext.

For the simulation-based security definition one may also consider different types of simulators:

• We considered a "non-rewinding" simulator, that answers the queries as they are asked by the adversary, and is required to make A produce an output indistinsuighable from a real execution
• One may consider a more relaxed variant, where the Ideal distribution is produced by the simulator. This can be further classified based on how the simulator depends on A: one may require that for any adversary, there is an associated simulator, or require the existence of a universal simulator that is given (black-box) access to the adversary.

Exploring how results translates to different definitional variants is left as an exercise.

Separating IND and SIM

Differently from PKE, IND and SIM security for functional encryption are not equivalent.

Claim: Assuming the existence of public key encryption, there is a functional encryption scheme that is IND-secure, but not SIM-secure.

Proof: Let (KeyGen,Enc,Dec) be any public key encryption schene, and p an injective one-way function. We define a simple functional encryption scheme supporting only one possible function query p. The scheme is defined by (KeyGen,Fun,Enc,Dec1) where Fun(sk,p) = sk and Dec1(sk,ct) = p(Dec(sk,ct)). The scheme is IND-secure because, unless msg[0]=msg[1], the adversary is not allowed to make any functional key derivation queries. However, it is easy to come up with a SIM-adversary such that any simulator is required to invert the one-way function. [QED]

Equivalence of IND and SIM

Claim Any SIM-secure functional encryption scheme is also IND-secure.

The separation result shows that the implication in the other direction does not hold. Still, if the functional encryption scheme supports a sufficiently powerful class of functions, and one is allowed to modify the encryption scheme, then one can also prove a converse implication.

Claim: If there is a functional encryption scheme for the class of all polynomial sized circuits achieving IND-security, then there is a functional encryption scheme satisfying SIM-security.

Proof: Starting from an IND-secure scheme (KeyGen,Fun,Enc,Dec), we build a SIM-secure scheme as follows. The scheme makes use of a private key encryption scheme (E,D) with keyspace K. In order to support a message space M1, we start from a (IND-secure) functional encryption scheme supporting two types of messages M = Real M1 | Fake K, i.e., one can encrypt either a real message or a "fake" message consisting of a random key.

• KeyGen1() = {(pk,(sk,k)) | (pk,sk) ⟵ KeyGen(), k ⟵ $}, where k is a randomly chosen key for (E,D).
• Enc1(pk,m) = Enc(pk,Real m)
• Dec1(fk,ct) = Dec(fk,ct)

• Fun1((sk,k),C) = Fun(sk,C[E(k,0)]) where E(k,0) is a random encryption of some fixed message 0 under the private key encryption scheme, and for any (private key) ciphertext r, C[r] is the modified circuit defined as follows:

  • C[r](Real m) = C(m)
  • C[r](Fake k) = D(k,r)

The security of the new scheme is proved using the following simulator:

• SimC(pk,(sk,k)) = Enc(pk,(Fake k))
• SimF((sk,k),C,y) = Fun(sk,C[r]) where r = E(k, y)