Homomorphic signatures for network coding: Difference between revisions

Revision as of 04:14, 5 July 2023

Revision as of 21:34, 6 July 2023

Line 141:

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>{{cite journalbook |last1=Boneh |first1=Dan |last2=Lynn |first2=Ben |last3=Shacham |first3=Hovav |title=Advances in Cryptology — ASIACRYPT 2001 |chapter=Short Signatures from the Weil Pairing |journal=Advances in Cryptology – ASIACRYPT 2001 |series=Lecture Notes in Computer Science |date=2001 |volume=2248 |pages=514–532 |doi=10.1007/3-540-45682-1_30 |chapter-url=https://hovav.net/ucsd/dist/sigs.pdf |access-date=17 November 2022 |language=en|isbn=978-3-540-45682-7}}</ref> Here it is shown that forging a signature is at least as hard as solving the [[elliptic 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==