is using a TCR hash with KOS safe?

[themighty1]

Hi, libOTe currently uses a TCR hash for breaking correlations in KOS acc.to this line https://github.com/osu-crypto/libOTe/blob/ad07f27b9ab229fa1d64ee642798c16ea5d8813f/libOTe/TwoChooseOne/Kos/KosOtExtReceiver.cpp#L385

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 TCR hash? Or is this a liberty that libOTe is taking without relying on a formal proof?

Thanks.

[ladnir]

https://eprint.iacr.org/2019/074.pdf section 4.1, 7.4

It requires modeling AES as an ideal random permutation which is very similar to RO when used in this context.

[ladnir]

Why not just implement/use Softspoken ?

[themighty1]

https://eprint.iacr.org/2019/074.pdf section 4.1, 7.4

It requires modeling AES as an ideal random permutation which is very similar to RO when used in this context.

@ladnir , Please correct me if I'm wrong, but I thought that starting from the strongest notion for a hash function H: Random Oracle > Random Permutation > Correlation robustness i.e. Correlation robustness is the weaker notion

GKWY19 shows how to use AES as RP as an ingredient to create H which is CR. This does not automatically make the resulting H a RP, even though it was created with RP as an ingredient. Or am I wrong?

Thanks.

[themighty1]

Why not just implement/use Softspoken ?

Yes, good idea. This is on our roadmap. But may take many months until production, so we are still interested in implementing KOS correctly.

[ladnir]

OK, so we assume the construction H is tcr. This means that for any query H(x, i) the adv makes, then H(x+r, i) is uniform, where r is some fixed global key. This is essential saying that for the other input, x+r, H acts like a random oracle.

So tcr is extreme close to a random oracle but falls a bit short all inputs are indistinguishable, only the subset (x+r) where x has been queried by the adversary.

That is, imagine you has a black box O that on input (x, i) outputs H(x + r, i) where r is a internal secret to O.

Then, by the tcr definition, we could switch the O to simply returning random outputs. Or we could switch it to returning a random oracle of (x, r, i).

All of these are indistinguishable.

What makes tcr weaker than an random oracle is that once you query H(x, i), it's easy to come up with more inputs that you can distinguish. However, you can't come up with the ones corresponding to these special x+r queries.

Put in the context of kos, it's not so simple. In particular the adversary might be able to get the honest party to query H(x), and H(x+r, i) where they know x+f(r) for some f. This could break the security guarantee.

Given a strong enough consistency check, lance showed https://eprint.iacr.org/2022/192 that just queries are in fact still secure. That f(r) will be sufficient close to 0 or r that it's equivalent to just knowing x or x'=x+r.

But what is "strong enough"? Lance showed his check is strong enough as well as the oos check. However, as you are aware it's unclear how strong the kos check is. So we do not know if kos is secure in general (for the current parameters, with a random oracle or a tcr) and therefore we don't know if it's OK to use a tcr hash. If you are willing to risk using the KOS consistency check, then my subjective opinion is that tcr is conservative enough.

I also suspect that if you instantiate kos with the very large parameters Ben Dimond https://eprint.iacr.org/2022/1371 proposed that a tcr hash will be OK. But at that size we don't have suitable permutations to implement the tcr.

So if you are implementing something new and you want it to be easier to implement, you have a third option to use the oos consistency check. Lance showed that this one is strong enough.

[ladnir]

@ldr709 anything you'd like to add?

[themighty1]

@ladnir , thank you for the detailed explanation which makes sense.

However, it seems that using a tcr hash for both standard and random OT KOS is secure due to the finding in GKWY19. Even though that paper only explicitely mentions in Table 2 that tcr is secure for standard OT KOS, we can infer from Appendix A that it is also secure for random OT KOS as well.

Related discussion https://github.com/GaloisInc/swanky/issues/25#issuecomment-1690338786

Please let me know if you agree with that. Thanks.

[ladnir]

Well I'd say my assessment is still the most accurate. We both agree that kos should be secure with tcr is the consistency check is good enough. Gkwy assumes this in their paper.

However, as lance and ben showed, the proof is flawed. Any proof showing that the tcr hash is OK must show (or assume) that the consistency check is good enough. Otherwise it doesn't match the definition of tcr.

[ldr709]

I agree that a TCR should be fine if you assume that the consistency check is secure. My main hesitation is that this may depend on exactly what is meant by "the consistency check is secure", as there are several ways that it could be formalized, and some may depend on how the hash is instantiated. E.g., Ben Diamond's proof assumes an RO, and would require some work to adapt to a TCR. And, e.g., the flaw in the KOS hashing analysis in https://eprint.iacr.org/2019/706 comes from assuming too strong of a property from the consistency check.

On the other hand it's hard to see how the particular TCR construction here could fail when the RO would succeed, for any reasonable interpretation of "the consistency check is secure".