mpz icon indicating copy to clipboard operation
mpz copied to clipboard

Published 20 hours ago • verified publisher icon privacy-scaling-explorations

Implement miTCCR

Open sinui0 opened this issue 2 years ago • 5 comments

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.

sinui0 avatar Dec 12 '22 07:12 sinui0

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 avatar Dec 13 '22 07:12 themighty1

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

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

themighty1 avatar Apr 06 '23 14:04 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.

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

  2. 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 avatar Sep 21 '23 06:09 themighty1

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

themighty1 avatar Sep 21 '23 07:09 themighty1

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

themighty1 avatar Feb 12 '24 07:02 themighty1