# Homomorphic Hiding and Blind Evaluation

# Background Needed
- Modular Arithmetic
- Number Theory

# 1. Homomorphic Hiding (HH)
HH is one of the most crucial components in ZK-SNARKS, it has several traits.

## Traits

Suppose that $E(x)$ is a HH function:

1. It's **hard to find** $x$ and $x'$ such that $E(x) = E(x')$.
2. It's **hard to find** $x$ from $E(x)$.
3. If someone knows $E(x)$ and $E(y)$, she can generate $E(x+y)$ from $E(x)$ and $E(y)$

## Example

Alice wants to prove to Bob that she knows $x$ and $y$ such that $x+y=7$.

1. Alice send $E(x)$, $E(y)$ to Bob.
2. Bob use $E(x)$ and $E(y)$ to compute $E(x+y)$.
3. Then, Bob also compute $E(7)$ to check if $E(x+y) = E(7)$.

Through the HH function, A**lice does not reveal $x$ and $y$, yet Bob is still able to verify the statement** ($x + y = 7$) sent by Alice.

## How's a HH constructed?

let $p$ be a prime number, then $Z_p^*$ has 3 properties.

1. It's a cyclic group, which exists a generator $g$ such that all elements can be expressed via $g$ ($\{ 0, 1, ... , p-2\}$).
2. Based on Discrete Logarithm Problem (DLP), it's hard to find the integer $a \in Z_p$ such that $g^a = h (mod \ p)$.
3. As "exponents add up when elements are multiplied", $g^a * g^b = g^{a + b} (mod \ p)$

For example, suppose
> Claim: $E(x) = g^x$ is an HH
1. According to 1st trait: **different x would have different output**. ($g^x \ne g^{x'}$)
2. Due to DLP, it's **hard to find** x when given $g^x$.
3. By using the 3rd trait, we **can compute** $g^x * g^y = g^{x + y}$ $\equiv$ $E(x) * E(y) = E(x+y)$

This is actually a great HH function that can hide the exponents yet still can be calculate directly.

## A python implementation

n = 101  # prime number
g = 3  # generator

x = 3
y = 4

ans = 7  # x+y

"""
We want to prove that E(x) * E(y) = E(x+y) without revealing x and y
"""

def E(r):  # HH function: E()
    return (g ** r) % n

def modularMultiply(a, b):  # Multiply in modulo n
    if a * b < n:
        return a * b
    return (a * b) % n

print(modularMultiply(E(x), E(y)) == E(ans))

## Summary for HH
Homomorphic Hiding (HH) is a vital component in ZK-SNARKS that **allows for computations on hidden values**.

Utilizing the cyclic group properties of $Z^*_p$ and the Discrete Logarithm Problem (DLP), the HH function $E(x) = g^x$ conceals the exponents but supports direct calculations, enabling verification without revealing underlying values. As a result, statements like $x + y = 7$ can be verified without disclosing the values of $x$ and $y$.

***

# 2. Blind Evaluation of Polynomials

The concept of "blind evaluation of polynomials" is to calculate some point on an unknown polynomial.

i.e. $f(x) = ax^2 + bX + c$, through blind evaluation, we can compute $f(3)$ without telling what $f(x)$ actually is.

This is also a central component in ZK-SNARKs.

## Polynomials & linear combinations

Recap: a polynomial $P$ of degree $d$ over $F_p$ can be expressed as:

$$
P(X) = a_0 + a_1X + a_2X^2 + ... + a_dX^d
$$

We can evaluate $P(X = s), s \in F_p$

$$
P(s) = a_0 + a_1s + a_2s^2 + ... + a_ds^d
$$

**Linear Combination**: $P(s)$ is actually a **weighted sum** of $\{1, s, ... ,s^d\}$, which the "weights" are $\{a_0, ..., a_d\}$.

Let $E(x) = g^x$ ($g$ is the generator of a group with hard DLP), and according to the 3rd trait ($g^x * g^x = g^{x+y}$) of this function, it also supports "linear combination":

$$
E(ax + by) = g^{ax+by} = g^{ax} * g^{by} = (g^x)^a * (g^y)^b = E(x)^a * E(y)^b
$$

## Combine HH & blind evaluation

Suppose **Alice** has a polynomial $P$ of degree $d$. **Bob** has $s \in F_p$ (randomly chose) and he wants to learn $E(P(s))$ from Alice.

In this case, we actually **don't want**:
1. Bob learns $P$
2. Alice learns $s$

,it will be explained in the future.

Therefore, we can perform evaluation:
1. Bob sends the hidings $E(1), E(s), ... E(s^d)$.
2. Alice compute $E(P(s))$ by the hidings.

### What does Alice do?
Alice knows the coefficients ($a_0, a_1, ..., a_d$) of $P$ and by using the linear combination, she can compute:

$$
\begin{align}
E(P(s)) &= E(a_0 + a_1s^1+ a_2s^2+ a_ds^d) \\
&= (by \ E(ax + by) = E(x)^a * E(y)^b) \\
&= E(1)^{a_0} * E(s)^{a_1} * E(s^2)^{a_2} * ... * E(s^d)^{a_d} \\
\end{align}
$$

By doing so, Bob learns $E(P(s))$ yet
- Alice does not know what $s$ is.
- Bob does not know what $P$ is.

## A python implementation

import random
n = 101  # prime number
g = 3  # generator

# coefficients of P(x)
a_0 = 12
a_1 = 13
a_2 = 18

def P(x):
    return a_0 * 1 + a_1 * x + a_2 * (x ** 2)

def E(r):  # HH function: E()
    return (g ** r) % n


def modularMultiply(a, b):  # Multiply in modulo n (if a*b > n)
    if a * b < n:
        return a * b
    return (a * b) % n

def modularExpo(a, b):
    return (a ** b) % n 

# 1. Bob pick a random num s
s = random.randint(1, 100)

# 2. Bobs gives E(1), E(s), E(s^2)
E_1 = E(1)
E_s = E(s)
E_s2 = E(s ** 2)

# 3. Alice evaluate E(P(s)) via given info
E_1_a_0  = modularExpo(E_1, a_0)  
E_s_a_1  = modularExpo(E_s, a_1)  
E_s2_a_2 = modularExpo(E_s2, a_2)

result = modularMultiply(modularMultiply(E_1_a_0, E_s_a_1), E_s2_a_2)

# Verify
print(result == E(P(s)))

## Summary of Blind Evaluation

The word **"Blind"** actually means that Alice doesn't learn what $s$ is, yet she can evaluate the value of $E(P(s))$, which is able to make the proof **zero-knowledge** to Bob (Verifier) since it do not reveal any infomation from Alice.

In SNARK, where we want the proof to be "Succinct", **and this is the reason why Bob cannot learn $P$ from the above case**.

:::warning
s and E(s) should follow d-power Diffie-Hellman Assumption (needed in some SNARK security proofs)

- given $g^a, g^b$ it's hard to get $g^{ab}$
:::

# Reference
- []()
- [zkSnark (Homomorphic Hiding)](https://asecuritysite.com/zero/zksnark01)
- [zkSNARK (Blind evaluation problem)](https://asecuritysite.com/zero/zksnark02)