need a piece of suggestion on `feed`

[weikengchen]

UPDATE: feel much confident now. the post is changed

It seems online/offline has some interesting things (but should be resolvable) with feed/reveal. (anybody did reactive online/offline semi-honest GC?) So I am wondering if you have any suggestion before I move forward.

ProtocolExecution has reveal and feed. These two are crucial for reactive programs.

feed uses a special trick to avoid sending for Alice -- Bob always receives the corresponding labels for 0 and 1 from shared PRG. Alice reverses the labels according to the data she wants to use.

That is to say, Alice is changing the circuit to input instead of changing the label to input. Therefore, Alice has nothing to send -- she writes it in the circuit.

This is a runtime optimization. It works for the input Alice always knows (e.g. share of a long-term key). But not the input Alice does not anticipate (e.g., current time when we evaluate).

(1) I guess we need a modification of feed -> Alice can specify whether an input is okay to specify in offline mode or wait! I will specify it in online mode. An offline test run should use this opportunity.

(2) To generate the circuit for offline, we actually run the program. If the program does not change the outside (stateless), then it is safe to run $f$ to generate the circuit. But now in such a reactive case, if the outside application needs to get the filename from the circuit, and feeds the data back to the circuit. Then such an application will find reveal returns something strange -- $f$ may not be designed for the offline test run.

(3) An optimization: the offline package can also contain the information to reveal. Therefore, if the reveal is to PUBLIC and cached in the offline package, Bob can immediately get the answer without asking Alice. Additionally, I think to reveal, Bob doesn't need Alice to send the whole block (semihonest_gen.h Ln 56), but LSB of 0-label is enough? So does Bob sends data back to Alice.

I think I still need one day to think about these details :) especially, I hope to get the plaintext circuit file of a real run and later all the offline phases is just garbling a circuit.

[weikengchen]

And Thank Xiao Wang :)

and also happy CCS'17.

[wangxiao1254]

In the offline phase, you do not really need to do any preprocessing for feed w.r.t. any party. It does not really matter whose input it is. All you need to know is what wires are input wires. You only need to garble and send GC. I think a good way to think of it is treating the protocol as a semi-honest 2pc, with black-box use of GC. The offline/online setting essentially puts GC offline and nothing else is changed.

Now in the online phase, parties will determine for each wire who will provide input. You can run feed here. Reveal should also be done at online phase. If the next computation depends on the first computation in a non-oblivious way, then I suppose the next circuit should incorporate all cases like a universal circuit. I'm not sure about exact details in my mind at this moment.

Now to your questions: 1) Your offline/online protocol should know that currently it is in the offline phase. If so, it is safe to ignore the ownership of this bit directly. The optimization I have will not work in this setting.

2) Say your program have two stage: first stage run f1, second stage runs g1 or g2, depending on the (public) output of the first stage. In this case I think you will need to do preprocessing for f1, g1, and g2 anyway, right? A side note: for ORAM, the choice of circuit is independent of input/output.

3) You are right :)

and Thanks!

[weikengchen]

Yes. I can set a global variable NOW_IN_OFFLINE_MODE=1 when offline generating the circuit.

The function $f$ should just pretend to read or write. Not doing any actual operation.

In 2., I am worrying the case where "if the second party's input does not satisfy a condition, the upper application after knowing this fact from reveal, it will call a side program to do unrecoverable change". But it is actually in the offline mode where all the middle values are meaningless.

a = reveal(xxxx);
if( a != 1){
     // Another party is cheating. Kill it.
     Realworld->UnrecoverableChange->UseWeapon->Kill(Bob);.
}else{
     // Normal. Let us feed data and continue.
     feed(xxxx);
}
continue the instructions...

This can be solved by adding NOW_IN_OFFLINE_MODE and let Alice relax (not kill Bob regardless of what is happening) and just feed zero (pretend that everything is okay).

[wangxiao1254]

You are right. Since we have no idea which execution path will be taken, you need to assume that all can happen. Therefore all computation, no matter whether it will be used or not, needs to be preprocessed.

However, depending on your use case, you can also just preprocess commonly used components. For those rarely encountered cases, you can just garbling online.

[weikengchen]

I think maybe in the future, we can support the case where the program may have different running paths like a DAG. All possible running blocks are garbled in the offline phase but some might not be run in the online phase.

p -> q1 or q2 or q3 -> r -> s1 or s2 -> t

However, in the real running, a specific path is selected -- if the secrecy of branching does not matter, why not leak it to reduce the online latency?

-- This is not something I should think about before finishing the current project. Let us ignore it for a moment.

Luckily, what I am trying to implement is something extensional to Circuit ORAM :) I see and as you mention, there is no such a problem.

Enjoy!