Parallelizing gcm powers circuits

[themighty1]

Hi, Im investigating if there is a way to parallelize garbling/evaluation of "gcm powers" circuits.

Does the underlying math allow to first obtain H and H^2 and then build on top of those to get H*H^2=H^3, H^2*H^2=H^4 and then build on top of those to get all other powers etc...?

Or is there no other way but to serially multiply by H one power at a time? Thanks.

[weikengchen]

Technically yes, and doing so allows you to save the online execution time of the protocol, because now the number of "round" is no longer N, but log(N).

However, I want to point out that, in many of today's garbling protocols, such as EMP-AGMPC, the computation consists of an offline phase and an online phase. The offline phase dominates the cost.

The offline phase generates a pool of cryptographic materials, called AND triples, which will later be used in the online phase for garbling. Such generation dominates the overhead. The good thing is that AND triples do not depend on the circuit. That is, the AND triples can always be generated in parallel.

Therefore, you can get the same benefit by parallelizing the offline phase. The only challenge is that it needs some implementation over the existing EMP-AGMPC library, as the current version does not implement this.