data61
MP-SPDZ VM memory model
As I understand it, when executing one of the many protocols available in MP-SPDZ, memory is allocated at compile time before this step. As such, when executing a protocol, it already knows how to touch the memory needed. However, as I understand, the memory model of the VM for that specific protocol doesn't rely on neither generic ORAM constructions nor oblivious algorithms for hiding array access patterns. Instead, ORAM is available as a kind of type in the high-level language and then it is somehow allocated at compile time.
Can you expand on how this works in MP-SPDZ? The paper doesn't go into as much details in order to better understand the rationale for this memory model design.
As I understand it, when executing one of the many protocols available in MP-SPDZ, memory is allocated at compile time before this step. As such, when executing a protocol, it already knows how to touch the memory needed. However, as I understand, the memory model of the VM for that specific protocol doesn't rely on neither generic ORAM constructions nor oblivious algorithms for hiding array access patterns. Instead, ORAM is available as a kind of type in the high-level language and then it is somehow allocated at compile time.
Indeed. The reasoning here is that ORAM is too complex to be done inside the virtual machine.
Can you expand on how this works in MP-SPDZ? The paper doesn't go into as much details in order to better understand the rationale for this memory model design.
Which paper do you mean? The main ORAM algorithms are documented in this paper while later additions include Circuit ORAM and Square-Root ORAM.
If you're looking for a more general introduction as opposed to the specifics in MP-SPDZ see Chapter 5 of the book here: http://securecomputation.org/
Which paper do you mean? The main ORAM algorithms are documented in this paper while later additions include Circuit ORAM and Square-Root ORAM.
I meant the MP-SPDZ paper. I don't recall any details about how ORAM is actually handled within the VM itself. I'm trying to wrap my head around how array accesses are still kept hidden if the VM itself doesn't do any oblivious operations.
This isn't treated in the MP-SPDZ paper because the ORAM implementation sits on top of the VM or even the compiler, and it's not related to a particular protocol. I would recommend the book chapter mentioned above for an introduction to the matter.
Is it accurate to say then that memory in MP-SPDZ isn't oblivious in anyway? If so, what is the design rationale for that besides simply that ORAM is too heavy to have within the VM? As far as I understand, then MP-SPDZ 's memory model leaks when accessing arrays regardless of whether you have a high level type for ORAM. Is that accurate?
Yes, memory accesses in the VM are always by public index and hence not oblivious. The rationale is that it's much easier to implement in the high-level interface, that the ORAM algorithms are largely independent of the protocol, and that there several options to achieve it, so a VM integration would get considerable more bloated while not providing any speed-ups.
That makes sense. Despite not getting any speed-ups if you were to have ORAM within the VM itself, it might make sense from an application perspective to still do it at the VM level. My reasoning is that there might be use cases where leaking this information is not within the applications leakage model. For MP-SPDZ, since the goal is benchmarking, this is not a problem at all.
In any case, thank you for answer my questions