Add support for subfield VOLE about libote

[ladnir]

https://eprint.iacr.org/2019/1159
https://1drv.ms/p/s!AmQ6D7DVFTx8gYZLJewtP6qRkpTXrw

If that doesn't help I can try to explain it.

[ladnir]

great! I'll review the code soon.

1. A good field to test is a 64-bit prime field. eg Fp for p=2^64-59
2. yes, it processes 8 trees at a time as an optimization. The idea is that we want to take advantage of CPU vectorization and pipelining. It's more efficient to perform the same operation to multiple pieces of data at a time. You could try to do this on one tree but its a bit more complicated. The way i did it was to simply generate 8 trees at a time.
3. Correct, the internals of the tree will remain the same. We will first generate leaf values as a block and then there should be some way to construct an F from block. This should be some customization point that the user can specify. There are a few options on how to implement this. One option is the member function static F F::fromBlock(const block& b). Another could just be a free template function tempate<typename F> F fromBlock(const block& b). Users can then specialize this function for their own F.

For the last layer, you will need to do the summation of it using F as opposed to using block and XOR.

[yyy977]

Maybe I can try if it's not an urgent task.

[ladnir]

great! Let me know if you have questions.

[yyy977]

I have some questions:

1. What is the application scenario of arbitrary field VOLE?
2. It seems that class block only supports gf128 operations now, are other field operations like gf64 needed as well?
3. A related question, the choice bits of silent ROT are LSB of B, but in IKNP or softspoken the choice bits are input value, are there some differences between silent ROT and others?

[ladnir]

1. There are the zero knowledge protocols (wolverine). Some psi protocols want the field to be different (blazing fast psi). Sometime you might want, say, 1 out of three ot. It's. More efficient to do this with a vole than two one out of two OTs. I'm sure there are many more applications.

2. Yes, you would need to task as input the field that is being considered. This should be a template parameter.

3. The lsb choice bit thing is an optimization that you can sometimes use. You can't always do it depending on what you want as output. In general the choice but isn't the lsb of B, but is OTs own bit vector.

By default the silent protocol picks the choice bits at random. This makes sense because the silent protocols do not sent enough data to even communicate what the choice bits should be.

You can derandomize the choice bits by sending the difference between what you have and what you want.

Iknp and softspoken work differently. They always send a message that fixes the choice bits.

[yyy977]

Got it!
Let me dive into it!

[lzjluzijie]

I can try to help, but I am uncertain how PPRF implemention worked in libOTe(specifically I don't understand how the tree is generated/shared) . Which paper should I read?

[lzjluzijie]

Sorry I was working on other tasks last week. The PPT is very helpful and I also found (https://www.youtube.com/watch?v=uJ2NWmdt0AQ&t=934s) very helpful. I created a draft PR #127 on this with Noisy subfield VOLE and I will work on PPRF next.

I have a few more questions:

1. Which fields I should test with? For simplicity I chose u64 and u128 for current test, but these are not really fields.
2. SlientPprf.h says there are 8 indepenendent trees that are being processed together. Could you explain this?
3. For https://github.com/osu-crypto/libOTe/blob/master/libOTe/Tools/SilentPprf.cpp#L524-L525, we need to generate random elements from pprf.mBaseOTs (using hashBlocks from AES)? Also, we should not modify the intermediate levels and keep them blocks, only change the leaves in the last level to the extension field F?

[ladnir]

done