Beyond Public-Key: Functional Encryption

Traditional public-key encryption follows a simple model: encrypt under a public key, decrypt with the corresponding private key. The decryptor learns the entire plaintext message. This all-or-nothing model is too coarse for many applications: a medical database might want to allow a doctor to learn only whether a patient has a specific condition, not the entire medical record. Functional encryption addresses this limitation.

Identity-Based Encryption (IBE), proposed by Shamir in 1984 and constructed by Boneh and Franklin in 2001, allows using an identity string (email address, domain name, employee ID) as a public key. A trusted key authority generates private keys for specific identities. IBE eliminates the need for public key certificates and enables simple key distribution. IBE is the simplest form of functional encryption.

Functional encryption (FE), formally defined by Boneh, Sahai, and Waters in 2011, generalizes IBE. In an FE scheme, a key authority can generate a function key sk_f for any function f. Given an encryption Enc(x) and a function key sk_f, a decryptor can compute f(x) but learns nothing else about x beyond what f(x) reveals. The function f can be any computable function within the scheme's supported class.

Inner product functional encryption allows a decryptor holding sk_y to compute the inner product from an encryption of vector x. This enables private machine learning inference: encrypt a user's feature vector x, give the model owner sk_y for their weight vector y, and they learn only the dot product (the raw prediction score) without learning the user's features. Multiple practical FE for inner product schemes exist (ABDALLA et al. 2016).

FE for equality testing allows a party to check if an encrypted value matches a specific value v, learning only whether the equality holds. This enables privacy-preserving database queries: a server holds encrypted records and a user queries for records matching specific values without the server learning what the user is searching for or learning the results beyond a yes/no match. Practical constructions use bilinear pairings.

The most powerful form of FE supports arbitrary boolean or arithmetic circuits as functions. A decryptor with sk_f for any polynomial-time function f can compute f(x) from Enc(x). General-circuit FE was theoretically constructed by Garg, Gentry, Halevi, Raykova, Sahai, and Waters (2013) using multilinear maps, but existing general FE constructions are impractical due to their reliance on imperfect multilinear map assumptions.

Indistinguishability Obfuscation (iO) is the strongest known cryptographic primitive and is closely related to functional encryption. An iO scheme takes a circuit C and produces an obfuscated version O(C) that computes the same function but reveals nothing about C beyond its input-output behavior. iO implies most known cryptographic primitives, including general FE. Candidate constructions from lattice problems exist but are far from practical.

Attribute-Based Encryption (ABE) is a practically realizable form of functional encryption where the function f is restricted to a policy evaluation: f(x) = 1 if the attribute set x satisfies a policy, 0 otherwise. ABE enables fine-grained access control where decryption rights depend on a user's attributes. ABE is the most practically deployed form of functional encryption, with implementations in cloud storage, healthcare, and IoT.

The history of FE constructions progresses from simple to powerful: IBE (Boneh-Franklin 2001) → FE for equality (various 2005-2010) → FE for inner product (ABDALLA 2016) → FE for bounded-depth circuits (based on multilinear maps, 2013) → general FE (conjectured from iO). Each step is more powerful but also more complex and less efficient. Practical deployment uses the simplest form that achieves the desired functionality.

FE security is defined by the indistinguishability of encryptions of two messages x0 and x1, even given function keys for arbitrary functions f, as long as f(x0) = f(x1) for all queried functions. This ensures the decryptor learns exactly f(x) and nothing more. There are two security levels: selective security (adversary commits to challenge messages before seeing the public key) and adaptive (full simulation-based) security.

General FE remains impractical, but inner product FE and ABE are deployable today. Challenges include: the need for a trusted key authority (single point of failure), key revocation complexity, performance overhead from pairing operations, and limited standardization. Research directions include multi-authority FE (no single trusted authority), decentralized key generation, and FE for larger function classes without multilinear maps.

What distinguishes functional encryption from traditional public-key encryption?

Functional encryption (Boneh-Sahai-Waters 2011) generalizes IBE by allowing function keys sk_f that enable computing f(x) from Enc(x) without learning x fully. Practical constructions exist for inner product FE (private ML inference) and equality testing. ABE is a practically deployed special case for access policy evaluation. General-circuit FE requires multilinear maps (impractical). iO is the strongest related primitive. The key challenge is moving from theory to efficient practice.