search

data61 / MP-SPDZ

Versatile framework for multi-party computation
Other
868 stars 272 forks source link

Using Dictionaries as a data structure #29

Open shreyansh26 opened 4 years ago

shreyansh26 commented 4 years ago

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

mkskeller commented 4 years ago

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

shreyansh26 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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

chrisZgh commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

Ok thanks.

Mikerah commented 1 year ago

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 commented 1 year ago

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.