Closed ladnir closed 7 months ago
Maybe I can try if it's not an urgent task.
great! Let me know if you have questions.
I have some questions:
block
only supports gf128
operations now, are other field operations like gf64
needed as well?B
, but in IKNP or softspoken the choice bits are input value, are there some differences between silent ROT and others? 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.
Yes, you would need to task as input the field that is being considered. This should be a template parameter.
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.
Got it! Let me dive into it!
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?
https://eprint.iacr.org/2019/1159 https://1drv.ms/p/s!AmQ6D7DVFTx8gYZLJewtP6qRkpTXrw
If that doesn't help I can try to explain it.
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:
u64
and u128
for current test, but these are not really fields.SlientPprf.h
says there are 8 indepenendent trees that are being processed together
. Could you explain this?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
?great! I'll review the code soon.
p=2^64-59
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.
done
Add proper support for general subfield VOLE over arbitrary field
G,F=G^m
.Whats currently implemented is
However, we want to support arbitrary
G, F=G^m
.First, how does silent OT work where
G={0,1}
?d
in fieldF
A' in G^{n'}
d * A'
which we will denote asB',C
'. Note thatdA'=B-C
A=MA'
B=MB'
C=MC'
A,B,C
such thatdA = B-C
. In particular, A is no longer sparse.A
and messagesm_{i,A_i}=H(B_i
)`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
whereA
is overG
and the rest are over the field F. However, the basic protocol for silent OT only works whenA
is binary.Why? The functionality of PPRF allows one party to choose an index
i
and another to choose a valued in F
. They then get to learn two random vectorB',C'
such thatB'-C'
is a unit vector with the valued'
at positioni
. e.g.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 whereG={0,1}
, this is exactly what we want.A'_i*d=1*d=d
. For VOLE, we need theA'
vector to be a sparse vector over a largerG
, not binary. For example,G={0,1,...,10}
. So nowA'_i
is some random non-zero element inG
and we wantB'-C'
to have the valueA'_i * d
at the positioni
. The idea for doing this is clever.We first perform another VOLE (noisy vole), where the inputs are a vector
A''
and the scalerd
, whereA''
are thet
non-zero values ofA'
. This gives us a secret sharing ofA''*d
. Instead of usingd
as the value to be used in the PPRF, this party (sender) will use theirj
th share ofA''*d
for the jth PPRF input scaler. The parties then get vectorsB'-C'
which is sparse and at the non-zero locations holds the sender's shares ofA''*d
. We can translate these shares to be what we want (i.e.dA'=B'-C'
) by having the receiver add their shares ofA''*d
toB'
at the positions that they know the non-zeros are at. That is, they choseA'
so know where the non-zeros are.So what needs to change in libOTe:
G
, and fieldF
. This protocol is pretty simple.G
, and field F. Currently, it is hard-coded to beF={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 byi
. There is then a final step that allows the P2 to learn thei
'th leaf value plus P1's share ofd*A_i''
. I think mostly what needs to change is the plus which is currently XOR to be whatever plus means forG,F
. Likely want to turn the PPRF into a template that takesF
as a type. This way we can know what plus to use.G,F
. This might not be too conceptually hard but my guess is that there are quite a few places that assumeF
is{0,1}^128
. Again, it might make sense to turn this into a template.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 arbitraryF
. We will definitely want this to be a template onF
.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.