# An Extended KCA

If Ted gives Jennifer some α -pair ( a , b = α ⋅ a ) and then Jennifer generates another α -pair ( a ′ , b ′ ) , then she knows c such that a ′ = c ⋅ a . In other words, Jennifer knows the relation between a ′ and a . Now, suppose that instead of one, Ted sends Jennifer several α -pairs ( a 1 , b 1 ) , … , ( a d , b d ) (for the same α ); and that again, after receiving these pairs, Jennifer is challenged to generate some other α -pair ( a ′ , b ′ ) . Recall that the main point is that Jennifer must do so although she does not know α .\
\
A natural way for Jennifer to generate such an α -pair, would be to take one of the pairs ( a i , b i ) she received from Ted, and multiply both elements by some c ∈ F ∗ p ; if ( a i , b i ) was an α -pair, then ( c ⋅ a i , c ⋅ b i ) will be one too. But can Jennifer generate α -pairs in more ways now that she’s received multiple α -pairs? Perhaps using several of the received α -pairs simultaneously to get a new one?\
\
The answer is yes: For example, Jennifer can choose two values c 1 , c 2 ∈ F p and compute the pair ( a ′ , b ′ ) = ( c 1 ⋅ a 1 + c 2 ⋅ a 2 , c 1 ⋅ b 1 + c 2 ⋅ b 2 ) . An easy computation shows that, as long as a ′ is non-zero, this is also an α -pair: b ′ = c 1 ⋅ b 1 + c 2 ⋅ b 2 = c 1 α ⋅ a 1 + c 2 α ⋅ a 2 = α ( c 1 ⋅ a 1 + c 2 ⋅ a 2 ) = α ⋅ a ′ . \
\
More generally, Jennifer can take any linear combination of the given d pairs – that is choose any c 1 , … , c d ∈ F p and define ( a ′ , b ′ ) = ( ∑ d i = 1 c i a i , ∑ d i = 1 c i b i ) . \
\
Note that, if Jennifer uses this strategy to generate her α -pair she will know some linear relation between a ′ and a 1 , … , a d ; that is, she knows c 1 , … , c d such that a ′ = ∑ d i = 1 c i ⋅ a i . The extended KCA states, essentially, that this is the only way Jennifer can generate an α -pair; that is, whenever she succeeds, she will know such a linear relation between a ′ and a 1 , … , a d . \
\
More formally, suppose that G is a group of size P with generator G written additively.\
\
The d-power Knowledge of Coefficient Assumption (d-KCA) in G is as follows: d-KCA: Suppose Ted chooses random α ∈ F ∗ p and s ∈ F p , and sends to Jennifer the α -pairs ( g , α ⋅ g ) , ( s ⋅ g , α s ⋅ g ) , … , ( s d ⋅ g , α s d ⋅ g ) . Suppose that Jennifer then outputs another α -pair ( a ′ , b ′ ) . \
\
Then, except with negligible probability, Jennifer knows c 0 , … , c d ∈ F p such that ∑ d i = 0 c i s i ⋅ g = a ′ . Note that in the d-KCA Ted does not send an arbitrary set of α -pairs, but one with a certain “polynomial structure”. This will be useful in the protocol below.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://priceai.gitbook.io/priceai-whitepaper/priceai-protocol/an-extended-kca.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.