Using Dictionaries as a data structure

[shreyansh26]

I wanted to know if there exists a way to use dictionaries in the .mpc format files like the Matrix and Array ones.

[mkskeller]

Unfortunately not. The virtual machine currently supports neither the dynamic memory allocation needed for a tree-based or a hash-based map.

[shreyansh26]

Right, however, I see that when I use normal dictionaries like in Python, the code still does compile and run. So, how does that work then?

[mkskeller]

The Python code is executed at compile time. So you can always use Python dictionaries, but if you use e.g. regint objects as dictionary index, you might not get the result you expect.

[shreyansh26]

Okay, thank you. I guess I'll have to play around with it a bit more.

[chrisZgh]

Is the 'limitation' of the virtual machine to non-dynamic memory allocation based on some basic theoretical limitations or could it in principle be extended?
Is there any documentation regarding the virtual machine implementation (other than reading the code)?

[mkskeller]

The only theoretical limitation is that memory accesses by secret addresses are rather expensive because that requires oblivious RAM. For the rest, there is no theoretical limitation, it is simply not a priority at this stage.

Regarding documentation of the VM, all instructions for arithmetic computation are defined in Compiler/instruction.py, and most of them come with a brief doc-string, but that's about it at the moment.

[chrisZgh]

Ok, thank you for the information. I had a closer look at several source code parts.
Is there an open source implementation including oblivious RAM? I also had a look into SCALE-MAMBA which also does not have it as far as I understood.

[mkskeller]

The oblivious RAM is implemented in Compiler/oram.py and Compiler/path_oram.py with applications in Compiler/dijkstra.py and Compiler/gs.py. This code is also available in SCALE-MAMBA because it stems from the predecessor project.

[chrisZgh]

Ok thanks.

[Mikerah]

What's the status of this? It appears to me that MP-SPDZ in its current state can be used to implement an oblivious dictionary as described in https://eprint.iacr.org/2014/137.pdf.

[mkskeller]

Only partially because the keys have to fixed-length for the solution in said paper. I think the original question was also more geared towards public keys by referring to Array and Matrix, which only work with public indices.