Efficient VOLE for one-shot zero-knowledge proofs

[weikengchen]

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]

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]

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]

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