Question about the implementation of linear_scan_write/read

[DylanWangWQF]

Hi @samee , I'm wondering how to implement the multiplexer among two parties in the linear scan of an array. I didn't find the corresponding code in this repository. As described in Obliv-C: A Language for Extensible Data-Oblivious Computation

Each assignment inside the obliv if is a conditional assignment (i.e., a multiplexer between old and new values), which is controlled by a different condition for each value of i.

[DylanWangWQF]

What's the scenario in Obliv-c?

Is the array shared between two parties (sat Alice and Bob)? Or only Alice locally stores the array while the private index is shared between Alice and Bob?

[samee]

A simple way to write newValue to a secret index index is to do this:

for(int i=0;i<n;++i) obliv if(i == index)
    myarray[i] = newValue;

If index was known to both parties (i.e. an int rather than obliv int), you could directly have written myarray[index] = newValue, and not needed the loop. If you want to read rather than write, you can also swap the assignment operator like so: newValue = myarray[i];

All of this is slightly inefficient, though, since it will produce a comparison for every ==. If you want to eliminate that, you can use a decoder, similar to what's implemented here: https://github.com/samee/sqrtOram/blob/master/oram/decoder.oh

Is the array shared between two parties (sat Alice and Bob)? Or only Alice locally stores the array while the private index is shared between Alice and Bob?

The array is shared between the two parties. The values can come from anywhere (i.e. directly from Alice or Bob, or it can be some intermediate result from some other computation).

Hope this helps.

[DylanWangWQF]

Hi @samee , many thanks for your reply!

Got it!

The array is shared between the two parties. The values can come from anywhere (i.e. directly from Alice or Bob, or it can be some intermediate result from some other computation).

Next, what I want to know is the details of implementing the multiplexer among Alice and Bob (say a boolean version of oblivious selection).

I'm new to secure multi-party computation and Obliv-c. I don't know if what I understand is correct: the traditional multiplexer circuit is like a 1-out-of-n OT. If given a secret-shared array [v], it's a "shared" variant of 1-out-of-n OT. I want to know the details of writing/reading in such a "shared" variant of 1-out-of-n OT (i.e., it's what Obliv-c did, right?).

If index was known to both parties (i.e. an int rather than obliv int), you could directly have written myarray[index] = newValue, and not needed the loop. If you want to read rather than write, you can also swap the assignment operator like so: newValue = myarray[i];

[samee]

I'm slightly unsure of what you are asking. Are you asking how multiplexers are generally made from simpler logic gates, or are you asking how that gets converted into a secure protocol?

For the former, just search online for "multiplexers with logic gates", and you should find lots of tutorials. Any good introductory book on digital logic design should work too. If, however, you want to know how to take an arbitrary circuit and garble it into a secure protocol, this talk has a good intro: https://simons.berkeley.edu/talks/mike-rosulek-2015-06-09

[DylanWangWQF]

I'm asking how to apply the multiplexers into the secure protocol in Obliv-C since I didn't find the details. Additionally, I want to replace the underlying Garbled Circuits with other protocols. What I can get is the high-level implementation of oblivious conditional assignment, like:

for(int i=0;i<n;++i) obliv if(i == index)
    myarray[i] = newValue;

I will check the sources you provided. Many thanks!