Functional Encryption

Functional Encryption (FE) lets a key holder learn a function of the plaintext without revealing the plaintext itself. From a ciphertext of $y$ and a functional key for a function $f$, decryption returns only $f(y)$.

A common CTF instantiation is FE for inner products, where a key for a vector $x$ reveals only $\langle x, y \rangle$. It is often built on an elliptic curve, following the paper Simple Functional Encryption Schemes for Inner Products on a NIST curve.

Inner-product scheme

The setup samples two secret scalar vectors $s, t$ and publishes $h_i = s_i g + t_i h$ for two generators $g, h$ of the curve.

• Encryption of a binary vector $y$ uses a random scalar $r$: $$C = r g, \qquad D = r h, \qquad E_i = y_i g + r h_i$$
• A functional key for a vector $x$ is the pair $(s \cdot x,\ t \cdot x)$ (dot products over $GF(\text{ord})$).
• Decryption with that key returns only $\langle x, y \rangle \cdot g$, never $y$ directly: $$\textstyle\sum_i x_i E_i - (s \cdot x) C - (t \cdot x) D = \langle x, y \rangle \cdot g$$

Attacks

• Key oracle leaking the master key

  If the key-generation oracle returns both the query vector $x$ and its key $(s \cdot x,\ t \cdot x)$, every query is a linear equation over $GF(\text{ord})$ in the unknown $s$ and $t$. Collecting $n$ queries (where $n$ is the vector length) gives two invertible systems $Y s = (s \cdot x)$ and $Y t = (t \cdot x)$, where $Y$ is the matrix of the query vectors. Recovering $(s, t)$ lets you decrypt each bit directly:

  $$E_i - s_i C - t_i D = y_i \cdot g \in \lbrace \mathcal{O},\ g \rbrace$$

  so $y_i = 0$ if the result is the point at infinity and $y_i = 1$ if it equals $g$ (no discrete log needed, just a point equality).

• Per-ciphertext blinding defeated by collinearity

  A patched scheme masks every bit with a fresh scalar $\alpha$ ($E_i = y_i \cdot \alpha g + r h_i$), so the residue becomes $\langle x, y \rangle \cdot \alpha g$ and the $\lbrace \mathcal{O}, g \rbrace$ test no longer works. But for each known $(x_i, s\cdot x_i, t\cdot x_i)$ the partial decryption

  $$Q_i = \textstyle\sum_j x_i[j] E_j - (s \cdot x_i) C - (t \cdot x_i) D = \langle x_i, y \rangle \cdot \alpha g = c_i \cdot P$$

  is a small integer multiple ($c_i = \langle x_i, y \rangle \in [0, N]$) of the same hidden point $P = \alpha g$. Recovering the small $c_i$ is not a discrete log: tabulate $\lbrace a \cdot Q_0 \rbrace$ for a reference $Q_0$ and match $b \cdot Q_i$ against it (a baby-step over small multiples) to read each ratio $c_i / c_0$, then lift to integers with an $\text{lcm}$. If the secret $y$ persists across re-keys, aggregating enough rounds yields far more than $N$ linear equations $\langle x_i, y\rangle = c_i$ and $y$ is the unique solution over $\mathbb{Q}$.