Add support for subfield VOLE

[ladnir]

Add proper support for general subfield VOLE over arbitrary field G,F=G^m.

Whats currently implemented is

silent OT,   G = {0,1},     F={0,1}^128
silent Vole, G = {0,1}^128, F={0,1}^128

However, we want to support arbitrary G, F=G^m.

First, how does silent OT work where G={0,1}?

• The sender samples a scaler d in field F
• The receiver samples a sparse binary vector A' in G^{n'}
• The parties use a PPRF to get secret shares of d * A' which we will denote as B',C'. Note that dA'=B-C
• The parties use an LPN-friendly matrix M to compute
• A=MA'
• B=MB'
• C=MC'
• We now have uniformly random A,B,C such that dA = B-C. In particular, A is no longer sparse.
• The receiver outputs Choice bits A and messages m_{i,A_i}=H(B_i)`
• The sender outputs messages , m_i0=H(C_i), m_i1=H(C_i+d)

Where does this fail for subfield VOLE? Well the definition of VOLE is to have d*A=B-C where A is over G and the rest are over the field F. However, the basic protocol for silent OT only works when A is binary.

Why? The functionality of PPRF allows one party to choose an index i and another to choose a value d in F. They then get to learn two random vector B',C' such that B'-C' is a unit vector with the value d' at position i. e.g.

B'-C' = 0000000000000d0000
                     ^
                     i'th position.                                     

You can repeat this several times, once for each non-zero of A' and add the results together.

Since A' is binary for silent OT where G={0,1}, this is exactly what we want. A'_i*d=1*d=d. For VOLE, we need the A' vector to be a sparse vector over a larger G, not binary. For example, G={0,1,...,10}. So now A'_i is some random non-zero element in G and we want B'-C' to have the value A'_i * d at the position i. The idea for doing this is clever.

We first perform another VOLE (noisy vole), where the inputs are a vector A'' and the scaler d, where A'' are the t non-zero values of A'. This gives us a secret sharing of A''*d. Instead of using d as the value to be used in the PPRF, this party (sender) will use their jth share of A''*d for the jth PPRF input scaler. The parties then get vectors B'-C' which is sparse and at the non-zero locations holds the sender's shares of A''*d. We can translate these shares to be what we want (i.e. dA'=B'-C') by having the receiver add their shares of A''*d to B' at the positions that they know the non-zeros are at. That is, they chose A' so know where the non-zeros are.

So what needs to change in libOTe:

• Change the noisy vole protocol to work over arbitrary subfield G, and field F. This protocol is pretty simple.
• Change the PPRF to support subfield G, and field F. Currently, it is hard-coded to be F={0,1}^128. In particular, the PPRF works by expanding a tree of random seeds. One party, P1, will know the whole tree while the other party, P2, knows all of it but the root-to-leaf path to the leaf index by i. There is then a final step that allows the P2 to learn the i'th leaf value plus P1's share of d*A_i''. I think mostly what needs to change is the plus which is currently XOR to be whatever plus means for G,F. Likely want to turn the PPRF into a template that takes F as a type. This way we can know what plus to use.
• Change the VOLE code to understand G,F. This might not be too conceptually hard but my guess is that there are quite a few places that assume F is {0,1}^128. Again, it might make sense to turn this into a template.
• Change the linear code M to work with any F. This code is pretty heavily optimized so it might look a bit intimidating but should be relatively ok to make a non-optimized implementation for an arbitrary F. We will definitely want this to be a template on F.

We can start by simply making copies of the NoisyVole, PPRF, Vole, linear code ExConv and modifying them as needed. Later, these can be merged as a template if that makes sense.

[changtong9]

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

[ladnir]

great! Let me know if you have questions.

[changtong9]

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.

[changtong9]

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?

[ladnir]

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

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

[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]

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.

[ladnir]

done