Better ORAM results with -R 128 than -R 64

[roostab]

Hi Marcel,

Sorry for asking yet another question, but I was wondering whether you could help me understand the this behavior.

I wrote some code that initializes OptimalORAM with n elements and writes to 1% of the ORAM's locations, chosen at random. I ran it with compile-run.py passing -v -E ring -R 64 -Z 3. Then, I also ran it with -R 128 and -R 256. I noticed that the performance with 64 bits is significantly worse than with 128 bits, despite the higher number of MBs sent in general (except in the run with 100k elements, where fewer MBs are sent with 128 bits). I also ran it with 256 bits, getting results similar to 128 bits.

size (n)	init time (s)	write time (s)	global data sent (MBs)	n bits
10000	3.63124	4.04475	116.527	64
100000	303.425	193.896	5078.39	64
1000000	2593.05	1185.5	101946.0	64
10000	0.901051	3.331	178.2	128
100000	78.8233	117.311	4950.15	128
1000000	755.057	881.251	116365.0	128

So I think that these results depend on specific implementation choices in the VMs, but I haven't found the point in the code that confirm this. Could you please let me know what in particular is causing this behaviour?

On a different note, I see that I can initialize the ORAMs as, e.g., OptimalORAM(n), but it looks like I can't also pass to the same function the n elements that I want to store into the ORAM. To do so, I wrote a subsequent for-loop that writes n elements from an array to the ORAM. Is there a reason why I can't do this at initialization? (Unless I just didn't see the API that does it).

Thank you!

[mkskeller]

This is probably due to the recursive structure of the ORAM (see https://eprint.iacr.org/2011/407). In short, larger ring elements allow to store more information, which allows for a leaner recursion. This comes out in the output during compilation. For example,

from oram import OptimalORAM
OptimalORAM(10000)

outputs the following when compiled with -R 64:

packed size: 313
(...)
used bits: 40

but the following with -R 128:

packed size: 157
(...)
used bits: 80

This indicates that the larger elements allow denser storage of the paths when recursing and thus smaller ORAMs.

You should be able to use batch_init for more efficient initialization of some ORAM types.

[roostab]

Hi Marcel, sorry for the late reply. Just wanted to thank you for the explanation, that was it. I also tried using batch_init, thanks for the suggestion. I see the function allows to store sint elements, but technically it should also be possible to store Array of sint in the ORAM, right?

[mkskeller]

Yes, OMatrix in Compiler/gs.py does that in some sense.

[roostab]

Thanks! If I got that code correctly, OMatrix creates a series of OMatrixRow, which allow to allocate elements in the ORAM at base + offset indexes (e.g., self.oram[self.get_index(offset)] = item). However, every item is a sint, right? In this case: say that I have to store an Array of n secret values. With this solution, every sint element is at a different ORAM leaf, thus setting / getting them all is slower than setting / getting the whole Array at an ORAM leaf?

[mkskeller]

PackedORAMWithEmpty roughly implements what you're after but it hasn't been tested as much. You can use it using PackedORAMWithEmpty(n_rows, [n_bits_per_entry] * n_columns).

[roostab]

Thank you, will try this out!