Decoupling Encryption Overhead from Circuit Complexity

24 concepts13 papers1 proposal

In traditional public-key encryption, security guarantees an all-or-nothing proposition: a user with the private key can read the entire message, while a user without it learns nothing. Functional Encryption (FE) fundamentally changes this paradigm. In an FE scheme, a central authority can issue functional secret keys $SK_f$ associated with a specific function $f$. When a user applies $SK_f$ to a ciphertext encrypting a message $x$, they learn the evaluation output $f(x)$ and absolutely nothing else about $x$.

However, early formulations of Functional Encryption suffered from a severe structural bottleneck: the size of the ciphertexts or the runtime of the encryption algorithm scaled with the size and complexity of the functions being evaluated. This dependency undercuts the core value proposition of secure computation outsourcing. If an encryptor must expend computational effort proportional to the size of the program being run by a downstream user, the efficiency gains of outsourcing are lost.

To solve this, a major line of cryptographic research focuses on compact and succinct functional encryption. The goal is to completely decouple the encryption overhead from the size of the evaluation circuits, ensuring that data transmission and storage remain highly efficient regardless of how complex the downstream analysis becomes.

The Core Mechanics of Compactness and Succinctness

To understand why compact FE is a breakthrough, we must look at how it redefines the boundaries of the encryption algorithm.

As defined by Ananth et al., a functional encryption scheme is considered compact if the runtime of the encryption algorithm depends strictly on the security parameter and the length of the input message—not on the complexity of the functions to be evaluated. This means an encryptor can secure a piece of data once, and a decentralized network can subsequently issue an arbitrary number of analytical keys without requiring the ciphertext to grow or the original data to be re-encrypted (Goldwasser et al.).

When total independence from the function cannot be achieved, cryptography aims for succinctness. In a succinct FE scheme, the ciphertext size scales not with the total number of gates in an evaluation circuit, but only with the circuit's depth (its maximum number of sequential operations).

Traditional FE:  [Message x] ---> Encryption ---> Ciphertext Size ∝ Total Gates in f(x)
Succinct FE:     [Message x] ---> Encryption ---> Ciphertext Size ∝ Depth of f(x)
Compact FE:      [Message x] ---> Encryption ---> Ciphertext Size ∝ |x| + Security Parameter

How do we achieve this decoupling? The breakthrough introduced by Goldwasser et al. relies on a layered composition of three distinct cryptographic primitives:

  1. Fully Homomorphic Encryption (FHE): The message $x$ is encrypted under an FHE scheme. FHE allows an untrusted party to evaluate any circuit $f$ directly on the ciphertext, producing an encrypted output $FHE(f(x))$. Crucially, the size of this evaluated ciphertext does not grow with the size of $f$.
  2. Attribute-Based Encryption (ABE): ABE is used to enforce access control over who is allowed to decrypt the final result, ensuring that only users with valid functional keys can proceed.
  3. Reusable Garbled Circuits: To safely transition from $FHE(f(x))$ to the plaintext output $f(x)$ without revealing the underlying FHE decryption key, the system uses a garbled circuit. Because the garbled circuit only needs to perform the decryption operation of the FHE scheme (which is fixed and independent of $f$), its size depends solely on the FHE decryption circuit's depth.

By nesting these primitives, the authors ensured that the initial ciphertext size remains completely insulated from the scale of the computation. This exact mechanism of inheriting succinctness through layered composition has also been adapted to Secure Multi-Party Computation (MPC). As shown by Ananth et al., integrating decomposable FE combiners into MPC protocols allows the communication complexity of the protocol to scale strictly with circuit depth rather than total circuit size.

Algebraic Optimizations for Specific Function Families

While general-purpose compact FE for all polynomial-time circuits often requires heavy cryptographic machinery, researchers have developed highly practical, specialized variants for simpler mathematical structures, such as linear and quadratic functions. Here, compactness is achieved by replacing generic obfuscation tools with direct matrix operations and pairing-based cryptography.

For instance, in Function-Private Inner Product Encryption (IPE)—where both the data vector $x$ and the function vector $y$ must remain hidden—traditional methods required master keys that scaled quadratically with the vector dimensions. Kim et al. bypassed this by avoiding complex dual pairing vector spaces, reducing master key sizes to a linear relationship with input dimensions.

For quadratic functions ($f(x) = x^T A x$), the optimization challenge is even more pronounced because evaluating polynomial terms naturally threatens to blow up ciphertext sizes. To counter this, Gong introduced a direct matrix inner-product framework that yields constant-size secret keys, completely severing the link between message length and decryption key size. In a parallel optimization track highlighted by Li et al., structural refinements reduced the ciphertext overhead from a multiplicative complexity to an additive complexity relative to input dimensions, making these schemes viable for resource-constrained decentralized networks.

Breaking the Circuit Bottleneck: The RAM Model

Even when an FE scheme is succinct or compact, evaluating functions using a circuit model introduces an inherent inefficiency: circuits are rigid. To evaluate a function on a circuit, every single gate must be processed, meaning the parameters and evaluation time must always scale with the worst-case runtime of the function.

To achieve true efficiency, Ananth et al. shifted the paradigm from circuit-based FE to Random Access Machine (RAM) based FE.

Circuit FE:  [Input x] ---> Must execute every gate ---> Worst-case Runtime
RAM-based FE: [Input x] ---> Dynamic memory lookups  ---> Input-specific Runtime

In the RAM model, a program can dynamically read and write to specific memory locations without scanning the entire memory array. By designing a generic transformation that maps circuit-based FE primitives onto a RAM architecture, the authors achieved input-specific decryption times. If a program terminates early on a given input $x$, the decryption process reflects that brief runtime immediately, preventing cryptographic parameters from bloating due to unvisited execution paths.

Why Compactness Matters: Bootstrapping to iO

The quest for compact functional encryption is driven by more than just practical efficiency; it is also a vital theoretical bridge. One of the most sought-after primitives in modern cryptography is Indistinguishability Obfuscation (iO)—a mechanism that can turn any computer program into an unreadable "black box" while preserving its functionality.

For years, constructing iO required highly complex and potentially unstable algebraic structures like high-degree multilinear maps. However, Ananth et al. demonstrated a profound theoretical equivalence: compact functional encryption is sufficient to construct indistinguishability obfuscation.

The intuition behind this bootstrapping is that a compact FE scheme already possesses the ability to hide the underlying structure of an evaluation during execution. By leveraging this property, researchers can build iO schemes from much simpler, lower-degree cryptographic assumptions. For example, Ananth et al. utilized Projective Arithmetic Functional Encryption (PAFE) to drastically lower the mathematical requirements for iO, dropping the necessary complexity from infinite or high-degree maps down to standard degree-5 multilinear maps.

Ultimately, whether applied to building advanced obfuscation tools, optimizing decentralized access control (Damgård et al.; Li et al.), or minimizing communication bounds in bounded-collusion settings (Ananth et al.), the core insight remains the same: by mathematically isolating the act of encryption from the act of computation, we can process private data at scale without paying a continuous cryptographic tax.

Key Foundational Work

Multi-Input Functional Encryption (2013) — contributed 2 concept elements to this direction.
Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond (2012) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compact_functional_encryption_a15cd790,
  title = {compact functional encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compact-functional-encryption/rdr_a15cd790896b4bbe8cfb469e80fe9242},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compact_functional_encryption_a15cd790_v1,
  title = {compact functional encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compact-functional-encryption/rdr_a15cd790896b4bbe8cfb469e80fe9242/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake