Interpolation in the Exponent (Shamir Shared PRF)

Question

Trying to implement the Diffie-Hellman distributed PRF mentioned by Cachin : https://cachin.com/cc/papers/abba.pdf.

It makes sense to me... just use the same Lagrange coefficient I'm using to combine shamir shares, but instead use exponentiation and multiplication ... so the interpolation is happening in the exponent.

But something isn't working out.

Right now I'm simply doing this for each share:

shares[i].data = pow(gen, shares[i].data, prime)

Then (essentially) this to combine:

comb = 1
for share in shares:
   comb *= pow(share.data, lagrange[share.index], prime)

I'm using pycryptodome's implementation of SSS and pulling out the coefficient calculations. I know that when I do this on the unmodified secrets they recombine just fine, so the L vals are OK:

comb = 0
for share in shares:
   comb += share.dat * lagrange[share.index] % prime

I think the issue is doing all this exponentiation in a prime field breaks things... maybe I need to choose the generator (base) more carefully... but it doesn't seem to matter what I choose.

I tried using ECC instead instead of g^secret (which is probably better anyway, since some generators could fail to explore the prime field properly and need to be chosen correctly)... I'm using the secp256k1 field prime. Shares are modified (Gen * share) and combined via:

comb = [None,None]
for share in shares:
   comb = curve.add(comb, curve.mult(curve.import(share.data), lagrange[share.index])

But I get the same issue (nondeterministic results).

Does anyone know of a library in any language that does this sort of "combination of modified secrets"? The Cachin paper seems to address it as a pretty trivial solution to the distributed PRF problem. I'm fine with the random oracle model assumptions.

(If I could see a working example of any version, it would probably be obvious what I'm doing wrong.)

Answer 1

The answer to this is that you need to select "gen" not randomly, but specifically as a generator of order P (your modulus prime used for shamir).

For secp256k1 field of size P this works:

• Select R = P*4-1.
• Select a gen=H(w) such that pow(gen, P, R) == 1
• During reconstruction choose R as the modulus

Now you've basically chosen a field R of order P, and everything will reconstruct correctly.

With ECC, you'd need to use curve.n as your modulus during sharing, but then you'll run into trouble with "hashing into the curve". See: https://eprint.iacr.org/2009/226.pdf to use ECC.