search

emp-toolkit / emp-zk

Efficient and Interactive Zero-Knowledge Proofs
Other
76 stars 18 forks source link

Efficient VOLE for one-shot zero-knowledge proofs #5

Open weikengchen opened 3 years ago

weikengchen commented 3 years ago

This issue is just to leave a note. It is mainly an engineering addition.

Currently, we generate the offline materials in big batches of N. This is because efficient LPN map K -> N is often "big". Therefore, even if two parties are proving very small statements, the one-shot time is not small.

There are many solutions to this:

  1. When computing the LPN map K -> N, we instead just compute K -> N' where N' < N. The limitation is that it does not fully use K, and K could be smaller if one computes the parameters more carefully.

  2. Use the original OT extension.

Both might be worthwhile of looking.

wangxiao1254 commented 3 years ago

Using IKNP would be bad because the communication would be high (as high as ZKGC). It is possible to reconfigure the parameter to target smaller parameters but I don't think the improvement would be that high. Are you looking at a setting where parties just come, compute and leave? (which means the one-time setup also needs to be included in the overall cost?)

weikengchen commented 3 years ago

Yes, I was thinking about a one-time setup. (Note: indeed in my application the circuit would be already large, so K -> N' where N' < N may be the best solution).

wangxiao1254 commented 3 years ago

N is 10^7, and K is ~500000, I suppose your N' is between these two numbers then.