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.