Homomorphic signatures for network coding: Difference between revisions

Revision as of 17:26, 9 March 2013

Revision as of 17:30, 9 March 2013

Line 137:

Then as long as <math>\sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p</math>, we can solve for the discrete log of Q. But the <math>r_i</math>’s are unknown to the oracle for Hash-Collision and so we can interchange the order in which this process occurs. In other words, given <math>b_i</math>, for <math>2 \leq i \leq r</math>, not all zero, what is the probability that the <math>r_i</math>’s we chose satisfies <math>\sum_{2 \leq i \leq r} (b_ir_i) = 0</math>? It is clear that the latter probability is <math>1 \over p</math> . Thus with high probability we can solve for the discrete log of <math>Q</math>.

We have shown that producing hash collisions in this scheme is difficult. The other method by which an adversary can foil our system is by forging a signature. This scheme for the signature is essentially the Aggregate Signature version of the Boneh-Lynn-Shacham signature scheme.<ref>http://cseweb.ucsd.edu/~hovav/dist/sigs.pdf</ref> Here it is shown that forging a signature is at least as hard as solving the [[Ellipticelliptic curve Diffie–Hellman]] problem. The only known way to solve this problem on elliptic curves is via computing discrete-logs. Thus forging a signature is at least as hard as solving the computational co-Diffie–Hellman on elliptic curves and probably as hard as computing discrete-logs.

==See also==