Homomorphic Hiding

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≠y, then E(x)≠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 simple example of why HH is useful for Zero-Knowledge proofs: Suppose Jennifer wants to prove to Ted she knows numbers x,y such that x+y=7.

1. Jennifer sends E(x) and E(y) to Ted.

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

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

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 mod N for an integer A , we mean taking the remainder of A after dividing by N. For example, 9 mod 7 = 2 and 13 mod 12 = 1. We can use the mod N operation to define an addition operation on the numbers { 0 , … , N − 1 } :

We do regular addition but then apply ( mod N ) on the result to get back a number in the range { 0 , … , N− 1 } . We sometimes write (mod N ) on the right to clarify we are using this type of addition. For example, 2 + 3 = 1 ( mod 4 ) .

We call the set of elements { 0 , … , N − 1 } together with this addition operation the group 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 , … , p − 1 }.

For example, 2 ⋅ 4 = 1 ( m o d 7 ) .

This set of elements together with this operation is referred to as the group Z ∗ P . Z ∗ P has the following useful properties:

It is a cyclic group; which means that there is some element g in Z ∗ P called a generator such that all elements of Z ∗ P can be written as G a for some a in { 0 , . . , P − 2 } , where we define G0 = 1.

The discrete algorithm problem is believed to be hard in Z ∗ P . This means that, when p is large, given an element h in Z ∗ p it is difficult to find the integer a in 0 , . . , p − 2 such that g a = h ( m o d p ) .

As ”exponents add up when elements are multiplied”, we have for a , b in 0 , . . , p − 2 g a ⋅ g b = g a + b ( m o d 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 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 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 x ⋅ g y = E ( x ) ⋅ E ( y ) .