Functional Encryption:
Understanding Inner Product

• Discrete Logarithm Problem
• Diffie–Hellman key exchange
• ElGamal Encryption
• Decisional Diffie–Hellman (DDH)
• Simple Functional Encryption Schemes for Inner Products
• Functional Encryption scheme for Inner product using DDH

Consider a generator \(G\), modulus \(P\) and order \(Q\) for a cyclic group \(Z^*_P\). Using ElGamal encryption scheme we define the masterSecretKey \(mSk\) as,

\begin{equation} mSk_i = x_i \;\;\; where \;\; x_i \in \{ 1, \dots , Q-1 \} \end{equation}

and masterPublicKey \(mPk\) as,

\begin{equation} mPk_i = G^{x_i} \; \mathsf{mod} \; P \end{equation}

Now we consider private message \(A = \prod_i a_i\) which is encrypted using the \(mPk\) and available publically i.e.,

\begin{align} C_A &= \Bigl\{ G^r \; \mathsf{mod} \; P, \prod_i mPk^r_i \cdot G^{a_i} \; \mathsf{mod} \; P \Bigr\} \\ &= \Bigl\{ G^r \; \mathsf{mod} \; P, \prod_i G^{x_i r} \cdot G^{a_i} \; \mathsf{mod} \; P \Bigr\} \\ \end{align}

where \(r\) is a random sample. For ease of notation we use,

\begin{align} C_{A} \{0\} &= G^r \; \mathsf{mod} \; P \\ C^i_{A} \{1\} &= G^{x_i r} \cdot G^{a_i} \; \mathsf{mod} \; P \end{align}

So,

\begin{equation} C_A = \Bigl\{ C_{A} \{0\}, \prod_i C^i_{A} \{1\} \Bigr\} \end{equation}

Consider a client which would like to calculate \(A \cdot B\) where \(B = \prod b_i\) . Since \(A\) is private the client has only access to \(C_A\) which is the cipthertext form of \(A\). In order to calculate \(A \cdot B\) the client sends \(B\) to over to party which holds \(mSk\) and request a decryption token for the dot product and receives the following,

\begin{align} TK^{mSk}_B &= \sum_i mSk_i \cdot b_i = \sum_i x_i \cdot b_i \\ &= x \cdot B \; \mathsf{mod} \; Q \end{align}

With \(mPk\), \(TK^{mSk}_B\) and \(B\) the client is now decrypt \(A \cdot B\) as follows,

\begin{align} N &= \prod_i \Bigl( C^i_A \{1\} \Bigr)^{b_i} \; \mathsf{mod} \; P \\ &= \prod_i \Bigl( G^{x_i r} \cdot G^{a_i} \Bigr)^{b_i} \; \mathsf{mod} \; P \\ &= \prod_i G^{x_i b_i r} \cdot \prod_i G^{a_i b_i} \; \mathsf{mod} \; P \\ &= G^{r \sum_i x_i b_i} \cdot G^{\sum_i a_i b_i} \; \mathsf{mod} \; P \\ &= G^{r \cdot x \cdot B} \cdot G^{A \cdot B} \; \mathsf{mod} \; P \end{align}

Notice, the above we have obtatined \(A \cdot B\) in the form of \(G^{A \cdot B}\). In order to be able to extract the inner product from the above equation we need to eliminate \(G^{r \cdot x \cdot B}\). This can be achieved using the functional decryption key \(TK^{mSk}_B\) as follows,

\begin{align} D &= \Bigl( C_A \{0\} \Bigr)^{TK^{mSk}_B} \\ &= \Bigl( G^r \Bigr)^{x \cdot B} \; \mathsf{mod} \; P \\ &= G^{r \cdot x \cdot B} \; \mathsf{mod} \; P \end{align}

Finally we calculate \(N D^{-1}\),

\begin{align} N D^{-1} &= G^{r \cdot x \cdot B} \cdot G^{A \cdot B} G^{-r \cdot x \cdot B} \; \mathsf{mod} \; P \\ &= G^{A \cdot B} \; \mathsf{mod} \; P \end{align}