Constructions of zk-SNARKs involve a careful combination of several ingredients; fully understanding how these ingredients all work together can take a while.

If I had to choose one ingredient whose role is most prominent, it would be what I will call here Homomorphic Hiding (HH)[1]. In this post we explain what an HH is, and then give an example of why it is useful and how it is constructed.

An HH $E(x)$ of a number $x$ is a function satisfying the following properties:

• For most $x$'s, given $E(x)$ it is hard to find $x$.
• Different inputs lead to different outputs - so if $x \neq y$, then $E(x)\neq E(y)$.
• If someone knows $E(x)$ and $E(y)$, they can generate the HH of arithmetic expressions in $x$ and $y$. For example, they can compute $E(x+y)$ from $E(x)$ and $E(y)$.

Here's a toy example of why HH is useful for Zero-Knowledge proofs: Suppose Alice wants to prove to Bob she knows numbers $x,y$ such that $x+y=7$ (Of course, it's not too exciting knowing such $x,y$, but this is a good example to explain the concept with).

• Alice sends $E(x)$ and $E(y)$ to Bob.
• Bob computes $E(x+y)$ from these values(which he is able to do since $E$ is an HH).
• Bob also computes $E(7)$, and now checks whether $E(x+y) =$ $E(7)$. He accepts Alice's proof only if equality holds.

As different inputs are mapped by $E$ to different hidings, Bob indeed accepts the proof only if Alice sent hidings of $x, y$ such as $x + y = 7$. On the other hand, Bob does not learn $x$ and $y$, as he just has access to their hidings.[2]

Now let's see an example of how such hidings are constructed. We actually cannot construct them for regular integers with regular addition, but need to look at finite groups:

Let $n$ be some integer. When we write $A \: \mathrm{mod} \: n$ for an integer $A$, we mean taking the remainder of $A$ after dividing by $n$. For example, $9 \: \mathrm{mod} \: 7 = 2$ and $13 \: \mathrm{mod} \: 12 = 1$. We can use the $\mathrm{mod} \: n$ operation to define an addition operation on the numbers $\{0,\ldots, n-1\}$ We do regular addition but then apply $(\mathrm{mod} \: n)$ on the result to get back a number in the range $\{0,\ldots, n-1\}$. We sometimes write $(\mathrm{mod} \: n)$ on the right to clarify we are using this type of addition. For example, $2+3 = 1 (\mathrm{mod} \: 4)$. We call the set of elements $\{0,\ldots, n-1\}$ together with this addition operation the group $\mathbb{Z}_n$.

For a prime $p$, we can use the mod $p$ operation to also define a multiplication operation over the numbers {1,...,$p$ - 1} in a way that the multiplication result is also always in the set $\{1,\ldots,p-1\}$, by performing regular multiplication of integers, and then taking the result mod $p$[3]. For example, $2 \cdot 4 = 1(mod \: 7)$.

This set of elements together with this operation is referred to as the group $\mathbb{Z}_p^* \mathbb{Z}_p^*$ has the following useful properties:

• It is a cyclic group; which means that there is some element $g$ in $\mathbb{Z}_p^*$ called a generator such that all elements of $\mathbb{Z}_p^*$ can be written as $g^a$ for some $a$ in {0,...,$p$ - 2}, where we define $g^0 = 1$.
• The discrete logarithm problem is believed to be hard in $\mathbb{Z}_p^*$. This means that, when $p$ is large, given an element $h$ in $\mathbb{Z}_p^*$ it is difficult to find the integer $a$ in {0,...,$p$-2} such that $g^a = h$ (mod $p$).
• As "exponents add up when elements are multiplied", we have for $a, b$ in {0,...,$p$ - 2},$g^ag^b = g^{a + b \: mod \: p - 1}$

Using these properties, we now construct an HH that 'supports addition', meaning that $E(x + y)$ is computable from $E(x)$ and $E(y)$. We assume the input $x$ of $E$ is from $\mathbb{Z}_{p - 1}$, so it is in the range {0,...,$p - 2$}. We define $E(x) = g^x$ for each such $x$, and claim that $E$ is an HH: The first property implies that different x's in $\mathbb{Z}_{p - 1}$ are mapped to different outputs. The second property implies that given $E(x) = g^x$ it is hard to find $x$. Finally, using the third property, given $E(x)$ and $E(y)$ we can compute $E(x + y)$ as $E(x + y) =$ $g^{x + y \:mod\: p - 1} = g^xg^y =$ $E(x)E(y)$.