Blind Evaluation Protocol

The Verifiable Blind Evaluation Protocol

The Verifiable Blind Evaluation Protocol Assume that our HH is the mapping E ( x ) = x ⋅ g for a generator g of G as above. For simplicity, we present the protocol for this particular E : Ted chooses a random α ∈ F ∗ p , and sends to Jennifer the hidings g , s ⋅ g , … , s d ⋅ g (of 1 , s , … , s d ) and also the hidings α ⋅ g , α s ⋅ g , … , α s d ⋅ g (of α , α s , … , α s d ). Jennifer computes a = P ( s ) ⋅ g and b = α P ( s ) ⋅ g using the elements sent in the first step, and sends both to Ted. Ted checks that b = α ⋅ a , and accepts if and only if this equality holds. First, note that given the coefficients of P , P ( s ) ⋅ g is a linear combination of g , s ⋅ g , … , s d ⋅ g ; and α P ( s ) ⋅ g is a linear combination of α ⋅ g , α s ⋅ g , … , α s d ⋅ g . Thus, similarly to the protocol of Part II, Jennifer can indeed compute these values from Ted’s messages for a polynomial P that she knows. Second, by the d-KCA if Jennifer sends a , b such that b = α ⋅ a then almost surely she knows c 0 , … , c d ∈ F p such that a = ∑ d i = 0 c i s i ⋅ g . In that case, a = P ( s ) ⋅ g for the polynomial P ( X ) = ∑ d i = 0 c i ⋅ X i known to Jennifer. In other words, the probability that Ted accepts in Step 3 while at the same time Jennifer does not know such a P is negligible. To summarize, using the d-KCA we’ve developed a protocol for verifiable blind evaluation of polynomials.