storage overhead in the offline-online model

[weikengchen]

Not really an issue, but likely a direction. The offline-online model allows us to reduce online latency, but it also means that the servers must store the offline preprocessed result (e.g., the many garbled circuits in AG-MPC).

This result is still a little bit big. For 10 parties, the first server stores ~400MB per SHA-256 circuit, mostly the garbled circuits. Other servers only need to store little data, such as the MAC keys for the input/output wires.

So it seems that applications might desire a way to "compress" the offline preprocessed result somehow, such as an alternative offline phase that has fewer copies of circuits, since it seems unavoidable but also kind of unideal for the first party to keep $N-1$ circuits.

[wangxiao1254]

In general, I think we can just send garbled circuits online, which means no need to store the garbled circuit. This increases the online latency slightly, but I think should not be a big issue...

[weikengchen]

While, in the case, it is just that all the parties now have to store 1/N of the first party's data? So, in total, it is still the same.

And there is another way to balance the storage among all the parties: let each party have a chance to be the first party.

[wangxiao1254]

No, GC is pipelined, no one store any GC.

[weikengchen]

Then, would storing the preprocessing result of AND gate triples, which would be consumed during the circuit generation, be large?

[weikengchen]

Adding to this note.

One potential storage reduction of ~50% is to observe that all the MAC keys are generated by the OT, so they are somehow the results of a PRG.

One may envision that we could just keep the seed and not store the MAC keys.

This seems challenging but likely possible: all the "sacrifice" checks in AG-MPC is not cut-and-choose. As always, the first $\ell$ elements are kept, which implies a deterministic order.

Yet, more attention is needed here.