proof checking in KosOtExtSender sometimes fails and throws runtime error

[haibren]

The check at the end of KosOtExtSender::send() sometimes does not pass and throws a runtime error. This occurs only on very specific terms.

This error can be produced by the tests supplied in libOTe. Repeat it by: bin/frontend_libOTe -kos -n <numOTs> but where numOTs is congruent to 1023 modulo 1024.
This error occurs for all values which are congruent to 1023 modulo 1024, and only for these values.
Also, It seems that this failure occurs only at about (or maybe exactly?) 50% of the times. This means that the test mentioned above might pass. But repeating it is bound to fail finally.

I’ve tried to identify why this problem occurs, but, alas, I do not know how the KOS scheme works and I cannot really understand it from code. The results of the KOS scheme are determined by these values:
the base OTs (as placed by setBaseOts and genBaseOts. In the test they just happen to be simulated and randomized without actually applying a full base OT protocol).
prng given as input to the KosOtExtReceiver (which is the party actually sending stuff to the other party)
the Receiver’s choice vector
Both the prng and the choice vector determine the contents of a vector called choice2, but that’s about all I could follow.

Tried repeating the error by manipulating the data put into the KOS send and receive functions.
It seems that the base OT part has no impact on whether the process fails or not. I.e. by determining the choices vector and the send-message and recv-message of the base, the process either always passes or always fails regardless of the baseRecv baseSend and baseChoice arrays (and also the flipping of the choice bits (by the delta bits) in setBaseOts and genBaseOts.
But determining the output of the base OTs (i.e. setting the baseRecv, baseSend, baseChoice and choice bit flipping) it seems that manipulating either the prng-seed of the KOS-receiver and/or the choice vector of the KOS Receiver, the process might pass or fail with about 50% chance, according to these specific inputs.
I could not manage to squeeze any more valuable info about what’s goes wrong.

The relevant cmake parameters I've used:
ENABLE_SSE=ON
ENABLE_BOOST=ON
OTE_KOS_HASH = OTE_DAVIE_MEYER_AES (but I think I've tried it with OTE_RANDOM_ORACLE as well and it did not help. I am not fully sure by now)
OTE_KOS_FIAT_SHAMIR = ON (Again, I believe I tried it OFF as well, but not sure)

The details of the machine I use are: kabylake-apple-darwin20.2.0 MacOS Big-Sur

[ladnir]

Ill look into this.

[ladnir]

fixed. thanks for pointing this out.

[haibren]

Thank you for the fix!

[haibren]

Once again, thank you.

Can you please point out if the fix only affected the case of 1023 mod 1024.
My team and I have been using an edited version of the code (basically the same, but handling of the channel communication was extracted outside to be handled somewhere else in the code, and also the separation to classes is different). We always only use even number(*) of OTs each time, and so we are wondering if the code before this fix is good enough for our needs, or we need to re-factor the libOTe code again for our purposes.

(*) Indeed I found this issue by mistake...

[ladnir]

Yes, the bug appeared to be an error only for the edge case of 1023. The issue was as follows,

When generating the OTs, the parties generate a matrix of size (n+128) x 128. The extra 128 rows are for a malicious security check that's performed. When the first extra row was at index 1023 mod 1024, there was a bug that resulted in the choice bit of this extra OT being assigned randomly. This resulted in the malicious proof of correctness failing with
Pr 1/2. I rewrote the logic to avoid this edge case.

You should be fine if you always perform an even number of OTs.

Cheers,
Peter

[ladnir]

Out of curiosity, how is your networking performed? I have recently been reworking my networking framework and I'm wondering if the new framework would enable you to use libOTe out of the box.

Thanks,
Peter

[haibren]

Hi Peter.

Thanks for pointing that out! I'll have a look.

But due to requirements of our development teams, we've so far separated completely the computation from the networking into different layers. The OT functions receives full messages (single round full memory buffers) and returns full round messages. Uncompromisingly, communication is done separately in other locations in the system.

Can the the renewed networking framework support such a requirement? It's not a big deal if not, because the code was flexible enough for us to extract the thing we wished for. Thanks!

[ladnir]

yes, it can but the API is not totally stable so maybe best to not switch yet. The new networking is based on the idea of c++20 coroutines but is written in c++11.

Roughly, all networking calls "pauses" the current function and returns to the caller. Once the networking is performed, you can resume the protocol where it was paused. All this is single threaded. This allows you to collect all messages for a single round of the protocol and send/receive them in a group. Or you can send/receive messages eagerly using a blocking socket or fully asynchronously.

Here is the branch which has everything but the silentOT protocol working https://github.com/osu-crypto/libOTe/tree/coproto

And here is how the networking works in detail. https://github.com/ladnir/coproto

[haibren]

Oh wow...
All this is still way beyond my expertise. I do not know anything about the newer c++ standards. This coroutine behavior that you mentioned sounds quite like the python yield command with generators. But I am not sure, I'll definitely have to study this before we can use such behavior.

It could have saved me the effort of doing my own refactoring of the KOS code, that's for sure.
But as long as it works for now (until I figure out the coproto thing), I am definitely pleased.

Thanks!