Implement miTCCR

[sinui0]

Rereading https://eprint.iacr.org/2019/1168.pdf it occurs to me that we never implemented the recommendation to randomly sample the initial gate id while garbling a circuit. We should do this to achieve multi-instance TCCR.

[themighty1]

My understanding is that we don't need to worry about miTCCR, here's why:
Edit: wrong understang, see newer comment below

GKWY19 (https://eprint.iacr.org/2019/ analyzes half-gates's notion "circular correlation robustness for naturally derived keys” in Section 5 and says that this notion "can be viewed as a form of tweakable circular correlation robustness (tccr)".
Then it says that tccr for half-gates "is overkill, and we show now that a family of hash functions satisfying the notion can be constructed from any H that is ccr".
Thus, we don't need tweakable ccr but just ccr. Since it is the re-use of a tweak that is the premise of the miTCCR paper, using ccr instead of tccr means the attack from the paper does not apply aymore.

I will double check about this line of reasoning with the emp-tool authors.

[themighty1]

I realized that the emp-tool author hasn't responded to my q about this matter: emp-toolkit/emp-tool#179
EDIT: he did respond

I think we should play it safe and implement the random sampling

[themighty1]

There are 3 things I learned from the "multi-instance (MI)" paper (https://eprint.iacr.org/2019/1168)

1. There is an attack on GKWY19's TCCR hash where security degrades with the amount of AND gates garbled (even across multiple independently garbled circuits), quoting

They [GKWY19] did not focus on obtaining better concrete security, and indeed, in Appendix C we show that using their hash function [TCCR] in the half-gates scheme would admit an attack similar to the one described above.

2. Then the paper shows a more secure miTCCR hash.

3. Then they show that miTCCR hash's security is tight only when 1 circuit is garbled.When multiple circuits are garbled, they suggest the tweak to randomize gate ids.

In light of this, we should both:

• replace TCCR with miTCCR
• add gate id randomization

[themighty1]

miTCCR explained by one of the authors: https://www.youtube.com/watch?v=MKGqA0K9d8M

[themighty1]

We need to examine how findings of this paper https://eprint.iacr.org/2024/163 apply to us.

[themighty1]

The latest paper 2024/163 proves some security bounds when using miTCCR hash with a leaky delta (like the delta in KOS).
In the leaky-delta setting miTCCR security is worse than in the original miTCCR paper 2019/1168, but I couldn't exactly figure out how much worse it is.

Regardless of the 2024/163 findings, we still need to

• replace TCCR with miTCCR
• add gate id randomization

[themighty1]

The attack on the TCCR hash shown in the miTCCR paper also applies to multiple circuits with different deltas. To quote:

the "shift R" is the delta.