This blog post is intended to give a high-level, partly mathematical perspective on inner product functional encryption (FE) schemes, along with multi-client and decentralized variants.

1. An Outline

It starts with a brief introduction to functional encryption and its inner product use case, then walks through the math behind below schemes:

• Inner Product Functional Encryption (a single-client scheme).
• Multi-Client Functional Encryption for Inner Product (an extension to multiple senders).
• Decentralized Multi-Client Functional Encryption for Inner Product (removing the need for a centralized authority).

Disclaimer: This blog is just the little bit of my mathematical understanding of the following research papers. For deeper security proofs, please refer to the papers or contact a cryptographer:

• Simple Functional Encryption Schemes for Inner Products
  by Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval
• Decentralized Multi-Client Functional Encryption for Inner Product
  by Jérémy Chotard, Edouard Dufour-Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval

I have used this understanding for the Rust implement here: https://github.com/dev0x1/functional-encryption-schemes

2. Functional Encryption Introduction

Functional Encryption (FE) is an advanced cryptographic paradigm where decryption keys allow users to learn only specific functions of underlying plaintexts, rather than the plaintexts themselves. In a traditional public-key or symmetric-key scheme, once a user has the decryption key, they can recover the entire plaintext. In FE, each key corresponds to a function $ f $ and decryption only reveals $ f(\text{plaintext}) $.

2.1. Difference With Homomorphic Encryption

Functional encryption may seem like homomorhpic encryption in terms of some use cases but there is difference. In homomorhpic encryption, if the data owner is the sole holder of the encryption key, then homomorphic encryption effectively allows them to offload computations on encrypted data to a third party but still requires them, and only them, to perform the final decryption of the result. In other words, the third party can carry out any valid operations on the ciphertext but never learns the underlying data, and the owner must decrypt the output at the end to see the plain result. By contrast, with functional encryption, the data owner can generate special “function keys” that let others directly learn the value of a specific function of the encrypted data—without revealing the data itself. In this setup, the data owner still controls the master secret key that creates these function keys, so only those operations for which the owner has issued a function key can be “partially decrypted” by others. This means that homomorphic encryption ensures all computations remain encrypted until the data owner alone decrypts, while functional encryption selectively grants decryption power for specific functions to whoever holds the corresponding function key.

Inner Product Functional Encryption (IPFE) is a special case of FE where the function $ f $ is the inner product of two vectors.

3. Use Case for Inner Product Functional Encryption

One of the most common real-world use cases for inner product FE is secure data analysis. Suppose each client encrypts their data vector. An analyst obtains a functional key corresponding to a specific vector $ \mathbf{y} $. When decrypting, the analyst only learns the inner product $ \langle \mathbf{x}, \mathbf{y} \rangle $, not the individual components of $ \mathbf{x} $. This is crucial in scenarios like:

• Privacy-preserving statistics: Summarizing user data in aggregate form, without revealing personal information.
• Machine learning inference: Computing weighted sums or predictions on encrypted feature vectors. Secure linear classification steps, where a model and a data vector are protected.
• Searching on encrypted data: Finding the best match to a query vector, without exposing the raw data or the exact query details.
• Pattern matching: Checking if a certain pattern matches a feature vector (e.g., in biometric recognition).
• Threshold checks: Determining if $ \sum_i x_i y_i \geq t $ without revealing the entire vector $ \mathbf{x} $.

In all these cases, the inner product is revealed only in a restricted sense (often, it is $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $), thus maintaining confidentiality of underlying inputs.

4. Inner Product Functional Encryption

Below is an explanation of the DDH-IP (Decisional Diffie–Hellman Inner-Product) functional encryption scheme for computing inner products in the exponent.

4.1. The Scheme

The functional encryption scheme $ \mathsf{FE} $ supporting an inner-product functionality is, given a ciphertext of some vector $ \mathbf{x} \in \mathbb{Z}_{p}^l $ and a secret key corresponding to a vector $ \mathbf{y} \in \mathbb{Z}_{p}^l $, the decryption recovers (in the exponent) the value $ \langle \mathbf{x}, \mathbf{y} \rangle = \sum_{i=1}^l x_i , y_i $. More concretely, it recovers $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $ for a generator $ g $ of a prime-order group $ G $.

The scheme $ \text{DDH-IP} = (\textsf{Setup}, \textsf{KeyDer}, \textsf{Encrypt}, \textsf{Decrypt}) $ is as follows:

1. Setup$(1^\lambda, 1^l)$

   • Sample $ (G, p, g) \leftarrow \mathsf{GroupGen}(1^\lambda) $. Here, $ G $ is a cyclic group of prime order $ p $, and $ g $ is a generator of $ G $.
   • Choose a secret vector $ \mathbf{s} = (s_1, s_2, \dots, s_l) $ uniformly at random in $ (\mathbb{Z}_{p})^l $.
   • Define $ h_i = g^{s_i} $ for $ i \in [l] $.
   • Output:
     $$ \mathsf{mpk} = (h_1, \dots, h_l), \quad \mathsf{msk} = \mathbf{s}. $$

2. Encrypt$(\mathsf{mpk}, \mathbf{x})$

   • Given $ \mathbf{x} = (x_1, x_2, \dots, x_l) $,
   • Choose a random $ r \in \mathbb{Z}_{p} $.
   • Compute $$ \mathsf{ct}_0 = g^r, \quad \mathsf{ct}_i = h_i^r \cdot g^{x_i} = (g^{s_i})^r \cdot g^{x_i} = g^{s_i r} \cdot g^{x_i} = g^{s_i r + x_i}, \quad \text{for each } i \in [l]. $$
   • Output ciphertext:
     $$ \mathsf{Ct} = \bigl(\mathsf{ct}_0,; (\mathsf{ct}_i)_{i\in[l]}\bigr). $$

3. KeyDer$(\mathsf{msk}, \mathbf{y})$

   • Given $ \mathbf{y} = (y_1, y_2, \dots, y_l) $,
   • Compute the dot product with $ \mathbf{s} $: $$ \mathsf{sk}_{\mathbf{y}} = \langle \mathbf{y}, \mathbf{s} \rangle = \sum_{i=1}^l y_i , s_i. $$
   • Output secret key:
     $$ \mathsf{sk}_{\mathbf{y}}. $$

4. Decrypt$(\mathsf{mpk}, \mathsf{Ct}, \mathsf{sk}_{\mathbf{y}})$

   • Given $ \mathsf{Ct} = (\mathsf{ct}_0, (\mathsf{ct}_i)_{i\in[l]}) $ and $ \mathsf{sk}_{\mathbf{y}} = \sum_{i=1}^l y_i , s_i $,

   • Compute: $$ \prod_{i=1}^l \bigl(\mathsf{ct}_i\bigr)^{y_i} = \prod_{i=1}^l \bigl(g^{s_i r + x_i}\bigr)^{y_i} = g^{ \sum_{i=1}^l (y_i s_i r + y_i x_i) }. $$

   • Then divide out above by using $ \mathsf{ct}_0^{\mathsf{sk}_{\mathbf{y}}} $.

   • Output: $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $.

Hence decryption yields $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $.

4.2. Why It Works

1. In the ciphertext, each component $ \mathsf{ct}_i = g^{s_i r + x_i} $.

2. When raising $ \mathsf{ct}_i $ to $ y_i $ and multiplying over $ i $,

   $$ \prod_{i=1}^l \bigl(g^{s_i r + x_i}\bigr)^{y_i} = g^{\sum_{i=1}^l (y_i s_i r + y_i x_i)}. $$

3. Meanwhile, $ \mathsf{ct}_0^{\mathsf{sk}_{\mathbf{y}}} = (g^r)^{\sum_{i=1}^l y_i s_i} = g^{ r \sum_{i=1}^l y_i s_i} $.

4. Dividing out this factor leaves $ g^{\sum_{i=1}^l y_i x_i} $. Therefore, the decryption algorithm recovers $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $.

4.3. The Limitation (Discrete Log)

Notice that the raw decryption result is $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $. To obtain that from $ g^{ \langle \mathbf{x}, \mathbf{y} \rangle } $, one would need to compute the discrete logarithm with respect to the base $ g $. However, taking a discrete log in a large prime-order group $ G $ is generally assumed to be hard (this is the cryptographic security assumption). This can be acceptable in scenarios where inner product sum is not a big value.

5. Multi Client Functional Encryption for Inner Product

Below is an explanation of multi-client functional encryption scheme for inner products (extending on the scheme outlined previously).

5.1. The Scheme

1. Setup$(\lambda)$

   • Generate $ (G, p, g) \leftarrow \mathsf{GGen}(1^\lambda) $, where:
     • $ G $ is a (prime-order) cyclic group,
     • $ p = |G| $ is the prime order,
     • $ g $ is a generator of $ G $.
   • Let $ H $ be a full-domain hash function $ H: {\text{labels}} \to G^2 $.
   • For each client $ i \in {1, \dots, n} $, pick a secret key $ \overrightarrow{s}_i \in \mathbb{Z}_{p}^2 $.
   • The public parameters are $ \mathsf{mpk} = (G, p, g, H) $.
   • The encryption key for client $ i $ is $ \mathsf{ek}_i = \overrightarrow{s}_i $.
   • The master secret key is $ \mathsf{msk} = (\overrightarrow{s}_1, \ldots, \overrightarrow{s}_n) $.

2. Encrypt$\bigl(\mathsf{ek}_i, x_i, \ell\bigr)$

   • Input: the value $ x_i \in \mathbb{Z}_{p} $ to encrypt (say, from client $ i $), the encryption key $ \overrightarrow{s}_i $, a label $ \ell $.
   • Compute $ \overrightarrow{u}_\ell = H(\ell) \in G^2 $.
   • Form $ [c_i] = [\langle \overrightarrow{u}_\ell, \overrightarrow{s}_i \rangle + x_i] \in G $.
   • Output ciphertext: $ [c_i] \in G $.

3. DKeyGen$\bigl(\mathsf{msk}, \overrightarrow{y}\bigr)$

   • Input: $ \mathsf{msk} = (\overrightarrow{s}_1, \dots, \overrightarrow{s}_n) $ and a vector $ \overrightarrow{y} = (y_1, \dots, y_n) $.
   • Compute $$ d_{\overrightarrow{y}} = \sum_{i=1}^n y_i\overrightarrow{s}_i \in \mathbb{Z}_{p}^2. $$
   • Output the functional decryption key: $$ \mathsf{dk}_{\overrightarrow{y}} = \bigl(\overrightarrow{y}, d_{\overrightarrow{y}}\bigr). $$

4. Decrypt$\bigl(\mathsf{dk}_{\overrightarrow{y}}, \ell, ([c_i])_{i=1}^n\bigr)$

   • Input: $ \mathsf{dk}_{\overrightarrow{y}} = (\overrightarrow{y}, d_{\overrightarrow{y}}) $, a label $ \ell $, ciphertexts $ ([c_i])_{i=1}^n $.
   • Compute $ \overrightarrow{u}_\ell = H(\ell) \in G^2 $.
   • Form $$ [\alpha] = \sum_{i=1}^n \bigl([c_i]\bigr)^{y_i} - \bigl[\overrightarrow{u}_\ell^T\bigr]^{d_{\overrightarrow{y}}} \in G. $$
   • Solve the discrete logarithm base $ g $ to extract $ \alpha $.

5. Why This Yields the Inner Product

   • Each ciphertext is $ [c_i] = g^{\langle \overrightarrow{u}_\ell, \overrightarrow{s}_i \rangle + x_i} $.
   • Raising to $ y_i $ and multiplying across $ i $ yields $ g^{\sum_i y_i(\langle \overrightarrow{u}_\ell,\overrightarrow{s}_i \rangle + x_i)} $.
   • Subtracting out $ g^{\sum_i y_i \langle \overrightarrow{u}_\ell, \overrightarrow{s}_i \rangle} $ removes the $ \overrightarrow{u}_\ell \cdot \overrightarrow{s}_i $ term, leaving $ g^{\sum_i x_i y_i} $.

Hence the only recoverable function is the dot product $ \sum_i x_i y_i $. One must still do a discrete log to get the integer value.

6. Decentralized Multi Client Functional Encryption for Inner Product

6.1. Motivation and High-Level Idea

• In a multi-client FE (MCFE) scheme for inner products, a single master secret key $ \mathbf{s} $ is held by a trusted authority. Each client $ i $ holds a fragment of $ \mathbf{s} $, denoted $ \mathbf{s}_i $.
• In a decentralized setting, the idea is to avoid having any single authority that knows the entire master secret key. Instead, each party can produce partial decryption keys (shares), which others can combine to enable functional decryption only.
• A main challenge:
  • The need to combine partial shares to compute $ \langle \mathbf{x}, \mathbf{y} \rangle $ (or rather $ g^{\langle \mathbf{x}, \mathbf{y} \rangle} $) without ever revealing $ \mathbf{s} $ or $ \sum_i \mathbf{s}_i y_i $ in the clear.
  • In regular MCFE schemes “in the exponent,” one can rely on discrete logs, which is fine for small plaintexts but becomes problematic if try to exponentiate large secrets or large partial sums.

Pairing-based approach:

• The researchers take advantage of a bilinear map (pairing) $ e: G_1 \times G_2 \to G_T $ on an asymmetric pairing-friendly group.
• Encryption occurs in $ G_1 $, partial decryption keys live in $ G_2 $, and the final functional result (inner product) is obtained in $ G_T $.
• This way, only small values like $ \langle \mathbf{x}, \mathbf{y} \rangle $ need to undergo a discrete-log extraction in $ G_T $, avoiding large discrete logs for the secret combination $ \langle \mathbf{s}, \mathbf{y} \rangle $.

6.2. Setup and Key Material

1. Pairing Group Generation

   $ \mathsf{PGGen}(1^\lambda) \to (G_1, G_2, p, P_1, P_2, e) $: generates two groups $ G_1 $ and $ G_2 $ of prime order $ p $, with generators $ P_1 \in G_1 $, $ P_2 \in G_2 $. The bilinear map $ e $ maps $ G_1 \times G_2 $ into $ G_T $.

2. Hash Functions

   • Two full-domain hash functions: $$ H_1 : {\text{labels}} \to G_2, \quad H_2 : {\text{vectors } \mathbf{y}} \to G_2. $$

3. Secret Splitting

   • Each sender $ i $ has $ \mathbf{s}_i \in \mathbb{Z}_{p}^2 $. The combined secret is $ \mathbf{s} = \sum_i \mathbf{s}_i $ (but no single party sees it).

4. Additional “T-matrices”

   • Random matrices $ T_i \in \mathbb{Z}_{p}^{,2\times 2} $ such that $ \sum_i T_i = 0 $. This ensures individual partial decryption keys do not reveal $ \mathbf{s}_i$.

5. Resulting Keys

   • Master public key: $ \mathsf{mpk} = (G_1, G_2, p, P_1, P_2, e, H_1, H_2) $.
   • Sender $ i $ encryption key: $ \mathsf{ek}_i = \mathbf{s}_i $.
   • Sender $ i $ secret key: $ \mathsf{sk}_i = (\mathbf{s}_i, T_i) $.

6.3. Encryption

A sender $ i $ wants to encrypt a scalar $ x_i \in \mathbb{Z}_{p} $ under label $ \ell $. The steps:

1. Compute $ [\mathbf{u}_\ell]_1 := H_1(\ell) \in G_2 $ (in practice, the indexing clarifies which group is used).
2. Output ciphertext $$ [c_i]_1 = \bigl[\langle \mathbf{u}_\ell,\mathbf{s}_i\rangle + x_i\bigr]_{1} \in G_1. $$

6.4. Generating Partial Decryption Keys (Shares)

For a function $ f_{\mathbf{y}} (\mathbf{x}) \to \langle \mathbf{x}, \mathbf{y} \rangle $ on input $ \mathbf{y} $, each $ \mathsf{sk}_i = (\mathbf{s}_i, T_i) $ produces a partial decryption key:

1. Hash $ \mathbf{y} $ to $ [\mathbf{v}_{\mathbf{y}}]_2 := H_2(\mathbf{y}) \in G_2 $.
2. Compute $$ [\mathbf{d}_i]_2 = [y_i,\mathbf{s}_i + T_i ,\mathbf{v}_{\mathbf{y}}]_2. $$
3. Return partial key $ \mathsf{dk}_{\mathbf{y}, i} = [\mathbf{d}_i]_2 $.

When summed over $ i $, the $ T_i $ parts cancel out, leaving $ \sum_i y_i \mathbf{s}_i $.

6.5. Combining Partial Keys

Summing all partial shares: $$ [\mathbf{d}]_2 = \sum_{i=1}^n [\mathbf{d}_i]_2 $$ which becomes the functional decription key $ \mathsf{dk}_{\mathbf{y}} $.

6.6. Decryption via Pairing

Given ciphertexts $ {[c_i]_1} $ in $ G_1 $ and $ [\mathbf{d}]_2 $ in $ G_2 $, plus label $ \ell $:

1. Compute $ [\mathbf{u}_\ell]_1 = H_1(\ell) \in G_2 $.
2. Combine in $ G_T $: $$ [\alpha]_T := \sum_{i=1}^n e\bigl([c_i]_1, [y_i]_2\bigr) - e\bigl([\mathbf{u}_\ell]_1, [\mathbf{d}]_2\bigr). $$ By bilinearity, this yields $ \bigl[g^{\sum_{i=1}^n x_i y_i}\bigr]_T $.
3. Compute discrete log in $ G_T $ to recover $ \alpha = \sum_{i=1}^n x_i y_i $.

6.7. Why It Works

6.7.1. Summing Up the Partial Decryption Keys

Each party $i$ produces a partial key

$$ [\overrightarrow{d}_i]_2 = \bigl[y_i\overrightarrow{s}_i + T_i \overrightarrow{v}_{\mathbf{y}}\bigr]_2 $$

where:

• $\overrightarrow{s}_i$ is the secret share held by party $i$.
• $y_i$ is the component of the vector $\overrightarrow{y}$ that describes the function $\langle \overrightarrow{x},\overrightarrow{y}\rangle$.
• $T_i$ is a matrix chosen so that $\sum_i T_i = 0$.
• $\overrightarrow{v}_{\mathbf{y}}$ is a hash of the vector $\overrightarrow{y}$.

When these partial decryption keys are summed:

$$ \sum_{i=1}^n [\overrightarrow{d}_i]_2 = \sum_{i=1}^n \bigl[y_i \overrightarrow{s}_i + T_i \overrightarrow{v}_{\mathbf{y}}\bigr]_2. $$

1. The linearity in the exponent (inside the bracket) means

   $$ \sum_{i=1}^n \bigl[y_i \overrightarrow{s}_i + T_i \overrightarrow{v}_{\mathbf{y}}\bigr]_2 = \bigl[\sum_{i=1}^n y_i \overrightarrow{s}_i \bigr]_2 +\ [\overrightarrow{v}_{\mathbf{y}}]_2 \sum_{i=1}^n T_i. $$

2. By construction, $\sum_{i=1}^n T_i = 0$, so the second term cancels out.

3. Hence,

   $$ [\overrightarrow{d}]_2 = \sum_{i=1}^n [\overrightarrow{d}_i]_2 = \bigl[\sum_{i=1}^n y_i \overrightarrow{s}_i \bigr]_2. $$

This shows that only by combining all partial shares does one obtain $\sum_i y_i \overrightarrow{s}_i$ in the exponent (in group $G_2$).

6.7.2. Decryption in the Target Group via Pairing

Each ciphertext $[\mathbf{c}_i]_1$ in group $G_1$ is of the form

$$ [\mathbf{c}_i]_1 = \bigl[\langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle + x_i\bigr]_1, $$

where:

• $\overrightarrow{u}_\ell$ is derived from a label $\ell$ (via a hash function).
• $x_i$ is the scalar message encrypted by party $i$.

To decrypt an inner product $\langle \overrightarrow{x}, \overrightarrow{y}\rangle$, the scheme uses the pairing map

$$ e: \quad G_1 \times; G_2 \longrightarrow G_T. $$

The functional decryption key for $\overrightarrow{y}$ is

$$ [\overrightarrow{d}]_2 = \bigl[\sum_{i=1}^n y_i \overrightarrow{s}_i\bigr]_2. $$

Consider the expression

$$ [\alpha]_T := \sum_{i=1}^n e\bigl([\mathbf{c}_i]_1,\ [y_i]_2\bigr) - e\bigl([\overrightarrow{u}_\ell]_1, [\overrightarrow{d}]_2\bigr). $$

Using bilinearity and linearity in exponents:

1. First sum
   $$ \sum_{i=1}^n e\bigl([\mathbf{c}_i]_1, [y_i]_2\bigr) = \sum_{i=1}^n e\Bigl(\bigl[\langle \overrightarrow{u}_\ell, \overrightarrow{s}_i\rangle + x_i \bigr]_1, [y_i]_2\Bigr). $$

   Pairing “multiplies” exponents:

   $$ e\bigl([z]_1, [w]_2\bigr) = [zw]_T. $$

   Hence,

   $$ e\bigl([\langle \overrightarrow{u}_\ell, \overrightarrow{s}_i\rangle + x_i]_1, [y_i]_2\bigr) = \Bigl[\bigl(\langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle + x_i\bigr),y_i\Bigr]_T. $$

   Summing over $i$ gives

   $$ \Bigl[\sum_{i=1}^n \bigl(\langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle + x_i\bigl)y_i\Bigr]_T = \Bigl[\sum_{i=1}^n \langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle y_i + \sum_{i=1}^n x_i,y_i \Bigr]_T. $$

2. Second term
   $$ e\bigl([\overrightarrow{u}_\ell]_1, [\overrightarrow{d}]_2\bigr) = e\bigl([\overrightarrow{u}_\ell]_1, [\sum_i y_i \overrightarrow{s}_i]_2\bigr) = \Bigl[\sum_{i=1}^n y_i \langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle\Bigr]_T. $$

3. Subtracting
   Subtracting removes the $\sum_i \langle \overrightarrow{u}_\ell,\overrightarrow{s}_i\rangle y_i$ part, leaving:

   $$ [\alpha]_T = \Bigl[\sum_{i=1}^n x_iy_i\Bigr]_T. $$

Thus, decryption obtains $g^{\sum_i x_iy_i}$ in $G_T$. If $\sum_i x_iy_i$ is sufficiently small, the discrete logarithm can be computed.

6.8. Notes

• No single entity holds the entire secret $ \mathbf{s} = \sum_i \mathbf{s}_i $.
• Each partial share $ [\mathbf{d}_i]_2 $ alone is “masked” by $ T_i $.
• Only when all partial decryption keys are combined do the random matrices sum to zero, revealing $ \sum_i y_i \mathbf{s}_i $ in $ G_2 $.
• The scheme is pairing-based, so large discrete logs (for $ \sum_i y_i \mathbf{s}_i $) are never done; only the final small inner product $ \sum_i x_i y_i $ is extracted via discrete log in $ G_T $.