The KC Test
For α ∈ F ∗ p , let us call a pair of elements ( a , b ) in G an α -pair if a , b ≠ 0 and
b = α ⋅a .
The KC Test proceeds as follows.
Ted chooses random α ∈ F ∗ p and a ∈ G . He computes b = α ⋅ a .
He sends Jennifer the “challenge” pair ( a , b ) . Note that ( a , b ) is an α -pair.
Jennifer must now respond with a different pair ( a ′ , b ′ ) that is also an α -pair.
Ted accepts Jennifer’s response only if ( a ′ , b ′ ) is indeed an α -pair. (As he knows α he can check if b ′ = α ⋅ a ′ .)
Now, let’s think how Jennifer could successfully respond to the challenge. Let’s assume for a second that she knew α . In that case, she could simply choose any a ′ in G , and compute b ′ = α ⋅ a ′ ; and return ( a ′ , b ′ ) as her new α -pair.
However, as the only information about α she has is α ⋅ a and G has a hard discrete log problem, we expect that Jennifer cannot find α .
So how can she successfully respond to the challenge without knowing α ?
Here’s the natural way to do it: Jennifer simply chooses some γ ∈ F ∗ p , and responds with ( a ′ , b ′ ) = ( γ ⋅ a , γ ⋅ b ) .
In this case, we have:
b ′ = γ ⋅ b = γ α ⋅ a = α ( γ ⋅ a ) = α ⋅ a ′ ,
so indeed ( a ′ , b ′ ) is an α -pair as required.
Note that if Jennifer responds using this strategy, she knows the ratio between a and a ′.
That is, she knows the coefficient γ such that a ′ = γ ⋅ a .
The Knowledge of Coefficient Assumption (KCA) states that this is always the case, namely:
KCA: If Jennifer returns a valid response ( a ′ , b ′ ) to Ted’s challenge ( a , b ) with non-negligible probability over Ted’s choices of a , α , then she knows γ such that a ′ = γ ⋅ a .
What does “Jennifer knows” mean exactly
You may wonder how we can phrase the KCA in precise mathematical terms; specifically, how do we formalize the notion that “Jennifer knows γ ” in a mathematical definition?
This is done roughly as follows: We say that, in addition to Jennifer, we have another party which we call Jennifer’s Extractor. Jennifer’s Extractor has access to Jennifer’s inner state.We then formulate the KCA as saying that: whenever Jennifer successfully responds with an α -pair ( a ′ , b ′ ) , Jennifer’s Extractor outputs γ such that a ′ = γ ⋅ a .