Add (R)OLE to mpz

[th4s]

This PR adds OLE and ROLE to mpz by introducing two new crates and creates the building blocks, like e.g. traits and module structure, for future OLE flavors and additional implementations.

~~I still need to do some small improvements here and there, but thought it is a good idea to get it out now.~~ Ready for review.

[th4s]

This will need to be adapted/rebased to the new architecture for IO.

[th4s]

Rebased and adapted to new IO design. Should be ready for review.

[th4s]

Rebased onto threading-refactor. Ready for review.

[themighty1]

Im happy to review this once we all agree on what specific approach we will be taking for E2F and GHASH. For now, we only tentatively agreed to use the PADO's approach with modifications to work around the 0 input issue. I have not examined PADO's protocols in detail yet. So, Im expecting the following sequence of events:

• Jordan ACKs that he's ok with using PADO's E2F and GHASH with our 0-input fix
• I'll review PADO's E2F and GHASH to make sure they make sense
• I'll analyze the ROT->ROLE protocol again with greater scrutiny
• I'll review the rest of this PR

[sinui0]

I haven't gone very deep in review here yet, but lets address some high level points:

1. I don't think it is appropriate to describe this protocol as Random OLE. That would imply the protocol deals random shares to both parties, which is not the case here.

2. Looking at your write up, it appears that "Random OLE" is exactly MASCOT (COPEe KOS16) with an additional step where the parties adjust their shares. AFAICT this share adjustment is superfluous, as they already choose them once and can sample them randomly if that is what they want, eg for offline preprocessing. I suggest we remove this step and just implement KOS16 verbatim.

   It recently occurred to me that the best approach is likely to just re-use the PRG seeds shared during the base OT for OT extension. Using the messages from ROT to seed the PRGs in COPEe seems unnecessary, and prevents us from preprocessing the OLEs in parallel with the OT extension.

3. We should stick with common nomenclature: OLE Sender and Receiver. Renaming these parties to Provider and Evaluator is bound to cause confusion. To help grok these terms: The Sender sends a linear function to the protocol and the Receiver receives an evaluation of that function at the index of their choice.

4. Regarding the "0-input fix" that should exist outside this OLE implementation entirely. It would be a sub-protocol of GHASH. Let's discuss that later, elsewhere.

5. The "with errors" suffix should not be present in any of the traits. We should just have an OleSender and OleReceiver trait, and users must understand the real functionality of the protocol they use which implements these traits.

[th4s]

Thanks for the review.

1. Can you explain why you think that the parties are not dealt random shares?

2. The difference between KOS16 (which is a VOLE) and this ROLE implementation is that in KOS16 the Delta is fixed. So the "Extend" calls cannot be used as a basis for an OLE, because only one party can choose the input. But for E2F or Ghash we need this degree of freedom. Am I missing something?

3. Agree

4. The 0-fix is not implemented. It only exists in the research write-up and we probably won't need it.

5. Agree

[th4s]

I went the route of using PRNGs for ROLE. So that you also have a Setup call and Extend calls. I don't think that this works. Relevant PR https://github.com/tlsnotary/docs-mdbook/pull/65

[sinui0]

Can you explain why you think that the parties are not dealt random shares?

In steps 1 and 2 of your Extend the parties sample their target shares, then subsequently use them to adjust the VOLE from COPEe. The functionality is not dealing these shares, the parties are choosing them. There is no constraint on the distribution from which these shares are sampled. I suggest we just skip this step, which is equivalent to COPEe.

The difference between KOS16 (which is a VOLE) and this ROLE implementation is that in KOS16 the Delta is fixed. So the "Extend" calls cannot be used as a basis for an OLE, because only one party can choose the input. But for E2F or Ghash we need this degree of freedom. Am I missing something?

KOS16 indeed does implement VOLE, or in our case $l = 1$ which is a single OLE. You're correct though, we can't reuse the base OTs as I was suggesting earlier, so we can stick with using ROT from OT extension to sample/transfer the PRG seeds.

I'm not quite sure that your protocol is secure. Re-iterating, it looks to me to be COPEe where each extend call to COPEe is then followed by a share adjustment to convert the VOLE into an OLE. This would imply you can get n-OLE from VOLE simply with this share adjustment. Maybe that's true, but it's not self-evident to me that it's secure.

[th4s]

In steps 1 and 2 of your Extend the parties sample their target shares, then subsequently use them to adjust the VOLE from COPEe. The functionality is not dealing these shares, the parties are choosing them. There is no constraint on the distribution from which these shares are sampled. I suggest we just skip this step, which is equivalent to COPEe.

I'm not quite sure that your protocol is secure. Re-iterating, it looks to me to be COPEe where each extend call to COPEe is then followed by a share adjustment to convert the VOLE into an OLE. This would imply you can get n-OLE from VOLE simply with this share adjustment. Maybe that's true, but it's not self-evident to me that it's secure.

I am not sure what you mean by Extend. For ROLE in the current construction (https://github.com/tlsnotary/docs-mdbook/blob/main/research/ole-flavors.typ#L29-L43) there is no Extend call. The construction is pretty different from COPEe, which was only the starting point.

KOS16 indeed does implement VOLE, or in our case which is a single OLE. You're correct though, we can't reuse the base OTs as I was suggesting earlier, so we can stick with using ROT from OT extension to sample/transfer the PRG seeds.

When I designed this, I tried to come up with with a Setup, Extend approach for ROLE, too, but couldn't get this to work in a way which made me feel safe about it. I did not invest too much time into this, because we have preprocessed random OTs available, so I felt that the performance impact was negligible. I tried using PRG seeds for ROLE, but I was not sure that this is safe.

[th4s]

Alright, I tried it out and it seems to work out quite nicely.

[th4s]

Closing in favor of #135.