Postpone SPCOT consistency check after exchange of GGM tree

emp-toolkit / emp-zk

Efficient and Interactive Zero-Knowledge Proofs

Other

77 stars 18 forks source link

Postpone SPCOT consistency check after exchange of GGM tree #10

Closed weikengchen closed 3 years ago

weikengchen commented 3 years ago

The current implementation has a lot of rounds because for each SPCOT,

the sender sends the GGM tree and then receives the challenge
the receiver receives the GGM tree and then sends the challenge

Therefore, this creates a real round for each tree.

This PR fixes this issue by deferring SPCOT consistency check message generation to be after the exchange of the GGM tree.

This PR closes #9. This PR closes #7.

weikengchen commented 3 years ago

Actually one question:

SPCOT indeed computes the secret_sum. In Ferret, something similar to secret_sum has been used for generating the challenge, so there is no need to wait for the receiver to send the challenge.
Is it because the secret_sum may be too short so that it is insufficient for Fiat-Shamir to work securely?

wangxiao1254 commented 3 years ago

Actually one question:

SPCOT indeed computes the secret_sum. In Ferret, something similar to secret_sum has been used for generating the challenge, so there is no need to wait for the receiver to send the challenge.

Is it because the secret_sum may be too short so that it is insufficient for Fiat-Shamir to work securely?

Yes. the challenge space is p^r when the authentication is in F_p^r. For Boolean, this is about 2^128 and thus FS is secure. For Arithmetic, we have a 61-bit p and r=1. so FS is not computationally secure. Of course, we can do the check twice to boost up the probability, then FS is secure. This could be faster if we SIMD these two checks.

weikengchen commented 3 years ago

Adding that for this PR, since the checks have been delayed, it seems also totally okay to not let all the threads each exchange a random number for each tree, but---let the receiver send one seed which derives the challenges of all the trees.

weikengchen commented 3 years ago

If that sounds reasonable, I can edit this PR for that.

(At this moment I need QuickSilver to be as many times faster than running the same computation in SPDZ as possible.)

wangxiao1254 commented 3 years ago

Adding that for this PR, since the checks have been delayed, it seems also totally okay to not let all the threads each exchange a random number for each tree, but---let the receiver send one seed which derives the challenges of all the trees.

Make sense to me!

weikengchen commented 3 years ago

Adding that for this PR, since the checks have been delayed, it seems also totally okay to not let all the threads each exchange a random number for each tree, but---let the receiver send one seed which derives the challenges of all the trees.

Hi, Chenkai, do you want to make changes regarding this one further optimization?