# The Knowledge Coefficients Assumption (KCA)

If you haven't read [Homomorphic Hiding and Blind Evaluation](/m8oWQ4WpQlaWc14IEmFLeA), please go to the link above and have a quick look at it.

# KCA

## What's KCA?
When we were calculating the homomorphic hiding function $E$, where $E(x) * E(y) = E(x + y)$, it's hard to say that Alice indeedly knows what $x$ and $y$ are.

In the reality, this value can be easily concocted, i.e. $x + y = 7$ => $x = 2, y = 5$, yet this proof would be accepted since $E(2) * E(5) = E(2 + 5) = E(7)$.

Therefore, we should introduce the "knowledge of coefficient"/ "knowledge of exponent" to improve our protocol.

##
As the note shown before, Alice can evaluate $E(P(s))$ from $E(1), E(s), E(s^2), ... , E(s^d)$ provided by Bob.

However, it don't guarentee that Alice would send the value $E(P(s))$ to Bob. In other words, Alice needs to prove that $E(P(s)$ **is really the hiding of** $P(X)$.

## Steps
Let $(G, +)$ be the cyclic group with order $|G| = p$ and generator $g$ where discrete log is hard. **Addition is used here to be more convenient.**

This time, Bob would choose **a pair** of elements $(a, b) \in G$ such that $for \ \alpha \in F_p^*, b = \alpha * a$ and send to Alice to calculate another value.

> This pair is called an $\alpha$ pair.

**KC Test**:
1. Bob choose a random $\alpha \in F_p^*$ and $a \in G$, compute $b = \alpha * a$, and send $(a,b)$ to ALice.
2. Alice must respond with another $\alpha$ pair: $(a', b')$.
3. Bob accepts Alice's response only if $(a',b')$ is an $\alpha$ pair. (use value of $\alpha$ to check).

However, Alice does not know what exactly $\alpha$ is since Bob only sends $(a, b)$, and **due to DLP, it's really hard to find $\alpha$ from $(a, b)$**

Therefore, Alice can use another method to generate another $\alpha$ pair by using a new number $\gamma \in F_p^*$.

$$
(a', b') = (\gamma * a, \gamma * b)
$$

we can check:

$$
b' = \gamma * b = \gamma * \alpha * a = \alpha * (\gamma * a) = \alpha * a'
$$

which implies $(a', b')$ is a $\alpha$ pair.

## KCA
> The knowledge of Coefficient Assumption (KCA)

KCA states that *If Alice returns a valid response $(a', b')$ to Bob's challenge with non-negligible probability over Bob's choice of $a, \alpha$*, then she knows $\gamma$ such that $a' = \gamma * a$.

***

# A New Protocol - verifiable blind evaluation