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 .