Homomorphic Hiding

A refresher on zk-SNARKs: Homomorphic Hiding (HH) is a very important element in constructing a zk-SNARKs proving system and it allows for computation on encrypted data without revealing the underlying values. Furthermore, it can be extended to use this cryptographic technique to evaluate computational correctness. This article servers as a concise overview of its workings.

Homomorphic Hiding Basics

We can define the properties of Homomorphic Hiding and the math behind it as follows:

Encryption function \(E\) \[ E(x)=g^x\ mod\ p \]
Homomorphic Property \[ E(x+y)=E(x)\cdot E(y) \]
Cyclic groups and modular arithmetic \[ \Bbb{Z}^*_p = \{1,2,\dots, p-1\}\ \]

The relevant homomorphic properties arise from the characteristics of the selected group and its generator \(g\). Specifically, an encryption function that we previously defined will have the property that \(E(x+y)=g^{x+y\ mod \ p-1}=g^x\cdot g^y=E(x)\cdot E(y)\) due to the properties of exponents in a cyclic group.

Toy Example

Supose Alice wishes to demonstrate to Bob that she knows the numbers \(x, y\) satisfying \(x + y = 11\), without disclosing the actual numbers. You can use cryptographic protocol to achieve this while preserving Alice's selected value.

Setup:
\begin{eqnarray} p&=&23\notag \\ g&=&5\notag \\ \end{eqnarray}
Alice's Encryption: We can pick \(x, y\) such that \(x=4,\ y=7\) for example and computes the followings and sends the outputs to Bob
\begin{eqnarray} E(x)&=&5^4\ mod\ 23 \notag \\ &=&4 \notag \\ E(y)&=&5^7\ mod\ 23 \notag \\ &=&17 \notag \end{eqnarray}
Bob's Verification: Bob also computes \(E(11)\), and now he can check if \(E(x+y)=E(11)\)
\begin{eqnarray} E(11)&=&5^{11}\ mod\ 23 \notag \\ &=&22 \notag \\ E(x+y)&=&4\cdot 17\ mod\ 23 \notag \\ &=&22 \notag \end{eqnarray}

The simple example provided above is not secure enough, as Bob could potentially discover Alice's secret through brute force attack by randomly picking \(x'\) and check if \(E(x) = E(x')\). So in practical application, it's essential to select a a very large prime number \(p\) to enhance security.

Blind Evaluation

The previous HH example not only supports addition but also linear combination. We can now extend this technique to even further.

Assume we have given outputs of encryption function from the previsous example, \(E(s), E(s^1),\cdots, E(s^n)\) for secret value \(s \in \Bbb{F}_p \) that Bob holds. Nobody can compute this \(s\) from the given outputs except Bob because of \(E\) is based with a hard discrete log problem.

However, Alice can compute \(E(P(s))\) for polynomial \(P(x):=\sum_ic_ix^i\) as follows ¹ using HH technique:

\[ E(P(s))=g^{P(s)}=g^{\sum_ic_is^i}=\prod_i(g^{s^i})^{c_i}=\prod_iE(s^i)^{c_i} \]

In other words, even if \(s\) is unknown, \(P(x)\) can be blindly evaluated at \(s\) (which holds for \(E\)) because \(E\) supports linear combinations and \(P(s)\) is a linear combinations of Bob's output from his secret.

Toy Example

Let's use the same setup from previous toy example.

Setup:
\begin{eqnarray} p&=&23\notag \\ g&=&5\notag \\ s&=&7\notag \\ d&=&3\notag \\ P(x)&=&5+3x+4x^2+9x^3\notag \end{eqnarray}
Bob's Challenge: Bob send to Alice the hidings
\begin{eqnarray} E(1)&=&5^1\ mod\ 23\notag \\ &=&5 \notag \\ E(s)&=&5^7\ mod\ 23 \notag \\ &=&17 \notag \\ E(s^2)&=&5^{7^2}\ mod\ 23 \notag \\ &=&2 \notag \\ E(s^3)&=&5^{7^3}\ mod\ 23 \notag \\ &=&4\notag \\ \end{eqnarray}
Alice's Evaluation: Alice computes \(E(P(s))\) and send it to Bob
\begin{eqnarray} E(P(x))&=&E(1)^{c_0} \cdot E(s)^{c_1} \cdot E(s^2)^{c_2} \cdot E(s^3)^{c_3} \notag \\ &=&5^5\cdot 17^3 \cdot 2^4 \cdot 4^9 \ (mod\ 23) \notag \\ &=&4 \notag \end{eqnarray}

This technique called Blind Evaluation since neither Alice learned Bob's secret input value \(s\), nor Bob learned Alice's polynomial \(P\).

Pairing

We can also apply the HH property to Pairing. In Pinocchio, the very first practical zk-SNARKs protocol, uses \(G_1 = G_2\) cyclic group and it holds the following ² :

\[ e(g^a,g^b)=e(g,g)^{ab} \]

And this holds for HH \(E(x)\) as follows:

\[ e(E(ax), E(y))=e(g^{ax},g^y)=e(g,g)^{axy}=e(g^x,g^{ay})=e(E(x),E(ay)) \]

In simple terms, the coefficient of the product can be shifted to either side of the equation. This property will play very important role when we need to use Knowledge of Coefficient.

Knowlede of Coefficient

Now we know that Alice can blindly evalue Bob's secret value using Blind evaluation. However, what if Alice randomly calcurate or pick a value and use it as her output? In other words, Bob doesn't really know if Alice run the correct computation that he wants Alice to compute.

There is a cryptographic technique for this situation, called Knowledge of Coefficient³, to force Alice to follow the protocol.

KC Basics

We call \(\alpha\)-pair if a pair of elements of \(E\) have a "\(\alpha\) times". The followings are an example of an \(\alpha\)-pair:

\(E(1)\) and \(E(\alpha)\)
\(E(s)\) and \(E(\alpha s)\)
\(E(s^2)\) and \(E(\alpha s^2)\)

More generally, a pair \((a, b)\) in \(G\) is called \(\alpha\)-pair if \(a,b \neq 0\) and \(b=\alpha \cdot a\).

KCA

Then we can define Knowledge of Coefficient Assumption as follows:

Bob chooses \(\alpha \in \Bbb{F}^*_p\) randomly for \(a\in G\), \(b=\alpha \cdot a\)
He sends \((a,b)\) \(\alpha\)-pair to Alice
Alice responds with her new \(\alpha\)-pair \(a',b'\)
Bob accepts Alice's response only if \(a',b'\) is an \(\alpha\)-pair

So, how can Alice calculate her \(b'\) without knowledge of \(\alpha\)? She can simply choose her random \(\gamma \in \Bbb{F}^*_p\) and compute her new pair \((a',b')=(\gamma\cdot a,\gamma\cdot b)\).

Since:

\[ b'=\gamma\cdot b =\gamma\alpha\cdot a = \alpha(\gamma\cdot a) =\alpha\cdot a' \]

So in this case, Alice can compute her \(\alpha\)-pair as required.

d-KCA: Extention of KCA

Now we can extend this KCA for the case Bob wants to send multiple \(\alpha\)-pairs to Alice.

Basics of d-KCA

Let's assume Alice's computed outputs based on \(s\) and \(\alpha\) from Bob's choice are as folows:
\begin{eqnarray} A&:=&E(f(s)) \notag \\ B&:=&E(f(\alpha s))\notag \end{eqnarray}
Then Bob can check the computational correctness using pairing function \(e\):
\begin{eqnarray} e(A, g^\alpha)=e(g^{f(s)}, g^\alpha)=e(g,g)^{\alpha f(s)} \notag \\ e(B, g)=e(g^{\alpha f(s)}, g)=e(g,g)^{\alpha f(s)} \notag \end{eqnarray}
Now we could possible to verify that Alice computes the value using correct polynomial with pairing. More formally, it's called d-power Knowledge of Assumption.

Summary

In this article, I try to summarize how we can construct computational correctness evaluation technique in privacy preserving manner, introducing zk-SNARK building blocks from Homomorphic Hiding to Pairing. I hope this article sheds light on the underlying mechanisms. Please leave feedback if you find any errors or have questions.

A polynomial \(P\) of degree \(d\) over Finite Field can be expressed as \(P(x)=a_0+a_1\cdot x+a_2\cdot x^2 + \cdots +a_d\cdot x^d\). And we can evaluate \(P\) at point \(s\) by substituting \(s\) for \(x\).

\(g\) is a generator of \(G_1=G_2\) and \(e\) is a pairing function.

In the original Pinocchio paper, it's called Knowledge of exponent.