Golden apple ``obliv if``?

I recently want to run Circuit ORAM on EMP-AGMPC (ah, both come mostly from you), so the main challenge is to write prepare_deepest and so on.

In Obliv-C, writing prepare_deepest would be simpler due to obliv if, in which the CIL compiler would take care of making whatever inside the obliv_if oblivious (by automatically writing a dummy else case for padding).

This obliv if, however, is not available in emp-toolkit, yet it would be a super useful grammar sugar if there is one. It also seems hard to add under the C++ environment. Obliv-C has to leverage the CIL, which is a heavy primitive that starts to fail to catch up with the new C standard and might not be a solution in the long run.

Any thoughts to add something similar?

One potential idea:

The following focuses on the plaintext protocol, which people use to generate circuits from emp programs.
We can add two macros/functions obliv_if_start(cond) and obliv_if_end, which instructs the underlying execution engine that the values in the middle would be conditioned by a specific oblivious bit cond.
The underlying execution engine keeps a list of all the modified values and conditions them (by an oblivious selection) during obliv_if_end.

This would require some changes to the plaintext protocol:

Currently, the plaintext protocol's labels are directly the "wire numbers". This would make it difficult to do conditioning during obliv_if_end, which would add a number of AND/XOR gates and thus wires.
To handle this, we could formulate two kinds of labels: symbolic labels and actual labels, for each oblivious bit, where the actual labels are wire numbers, but symbolic labels not necessarily are.
The oblivious data structures (e.g., Float) store symbolic labels, which would be transited to the actual labels by the plaintext engine during the writeup of the circuit files.
This would allow the engine to write additional gates silently while being transparent to the emp program writing system.

In addition, a related discussion:

The current circuit format is somehow inflexible. It requires all the output wires to be at the end. Many programs have been paying additional XOR gates to copy the values, which is inexpensive but unnecessary.

As a side note, the community may love a brand-new circuit format that provides great flexibility? Multiparty input & output? Parallel execution? Reactive computation? Nontrivially circuit file compression (like, for the loop, write something repeat xxx-xxx gates with an offset xxx in the file instead of a number of mostly "repeated" logic)?

For obliv if, I have thought about it. One thing we can do is to simulate a stack containing conditional variables, and all assignment will then be automatically passed by multiplexers of the top condition. This will support nest loops, etc.

For circuit file. Yes, that's what I'm also hoping for. For example, the circuit should be decoupled from which input belongs to which party, etc.

Xiao

On Wed, Sep 16, 2020 at 1:54 PM Weikeng Chen notifications@github.com wrote:

I recently want to run Circuit ORAM on EMP-AGMPC (ah, both come mostly from you), so the main challenge is to write prepare_deepest and so on.

In Obliv-C, writing prepare_deepest would be simpler due to obliv if, in which the CIL compiler would take care of making whatever inside the obliv_if oblivious (by automatically writing a dummy else case for padding).

This obliv if, however, is not available in emp-toolkit, yet it would be a super useful grammar sugar if there is one. It also seems hard to add under the C++ environment. Obliv-C has to leverage the CIL, which is a heavy primitive that starts to fail to catch up with the new C standard and might not be a solution in the long run.

Any thoughts to add something similar?

One potential idea:

-

The following focuses on the plaintext protocol, which people use to generate circuits from emp programs.

We can add two macros/functions obliv_if_start(cond) and obliv_if_end, which instructs the underlying execution engine that the values in the middle would be conditioned by a specific oblivious bit cond.

The underlying execution engine keeps a list of all the modified values and conditions them (by an oblivious selection) during obliv_if_end.

This would require some changes to the plaintext protocol:

-

Currently, the plaintext protocol's labels are directly the "wire numbers". This would make it difficult to do conditioning during obliv_if_end, which would add a number of AND/XOR gates and thus wires.

To handle this, we could formulate two kinds of labels: symbolic labels and actual labels, for each oblivious bit, where the actual labels are wire numbers, but symbolic labels not necessarily are.

The oblivious data structures (e.g., Float) store symbolic labels, which would be transited to the actual labels by the plaintext engine during the writeup of the circuit files.

In addition, a related discussion:

The current circuit format is somehow inflexible. It requires all the output wires to be at the end. Many programs have been paying additional XOR gates to copy the values, which is inexpensive but unnecessary.

As a side note, the community may love a brand-new circuit format that provides great flexibility? Multiparty input & output? Parallel execution? Reactive computation? Nontrivially circuit file compression (like, for the loop, write something repeat xxx-xxx gates with an offset xxx in the file instead of a number of mostly "repeated" logic)?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/emp-toolkit/emp-tool/issues/93, or unsubscribe https://github.com/notifications/unsubscribe-auth/AARKGCXU5CQSCJHQFFIO2DTSGECXJANCNFSM4RPIOBRQ .

Putting it on the schedule...

emp-toolkit / emp-tool

Golden apple ``obliv if``? #93

Any thoughts to add something similar?

The following focuses on the plaintext protocol, which people use to generate circuits from emp programs.

We can add two macros/functions obliv_if_start(cond) and obliv_if_end, which instructs the underlying execution engine that the values in the middle would be conditioned by a specific oblivious bit cond.

Currently, the plaintext protocol's labels are directly the "wire numbers". This would make it difficult to do conditioning during obliv_if_end, which would add a number of AND/XOR gates and thus wires.

To handle this, we could formulate two kinds of labels: symbolic labels and actual labels, for each oblivious bit, where the actual labels are wire numbers, but symbolic labels not necessarily are.