is using a TCCR hash with random OT KOS safe?

[themighty1]

Hi, ocelot currently uses a TCCR hash for breaking correlations after the KOS check acc.to this line

swanky/ocelot/src/ot/kos.rs

Line 106 in bf632db

let y0 = self.ot.hash.tccr_hash(Block::from(j as u128), q) ^ input.0;

However, the security proof of the KOS paper uses a random oracle.

Since we are also implemting a KOS OT extension, we're trying to understand has there been any recent work which proves KOS security with a TCCR hash? Or is this a liberty that ocelot is taking without relying on a formal proof?

Thanks.

[jprider63]

Hi @themighty1. The person familiar with this code is currently out, but they'll get back to you once they return.

[Isweet]

The paper that the current TCCR implementation is based on is: https://eprint.iacr.org/2019/074.pdf.

See: https://github.com/GaloisInc/swanky/blob/master/scuttlebutt/src/hash_aes.rs#L52

There's been some research since that suggests that a TCCR with tighter concrete security is necessary, see: https://eprint.iacr.org/2019/1168.pdf.

Does that help?

[themighty1]

Hi, thank you for the response and the link. Sry, I did not originally specify that I had random OT KOS in mind.

Indeed, the GKWY19 paper shows that a tcr hash can be used with KOS15's standart OT. GKWY19 does not show that tcr is ok for KOS15 random OT. (we go from random OT to standard OT by performing derandomization as per Fig.9 of the KOS15 paper).

But in ocelot, a tcr hash is used directly for random OT here:

swanky/ocelot/src/ot/kos.rs

Line 156 in bf632db

let x0 = self.ot.hash.tccr_hash(Block::from(j as u128), q);

I was trying to better understand if maybe I was misunderstanding something or there was some other work I missed. I would appreciate you sharing your thoughts on this, @Isweet .

[amaloz]

Looking through the implementation (in kos.rs) and Figure 7 in GKWY19, it does appear that the random OT implementation matches the protocol proven secure using tcr in the paper (Theorem 7 in the Appendix). I'm not sure if this is equivalent to KOS15 random OT as specified in their paper though.

When you say:

GKWY19 does not show that tcr is ok for KOS15 random OT.

Are you referring to Table 2 or somewhere else in the paper where they make that explicit? I may have missed that.

[themighty1]

Are you referring to Table 2 or somewhere else in the paper where they make that explicit? I may have missed that.

Thanks for pointing that out.
Yes, I was simply looking at Table 2 and assumed that since random OT KOS is not explicitely mentioned in Table 2, then it must be that the paper does not prove that tcr can be used with random OT KOS.
However, looking at Appendix A, I do agree that it seems like there is a proof that using a tcr hash is indeed secure.

[ladnir]

FYI, here's Lance's and my take on this question osu-crypto/libOTe#116