Oblivious parallel random access machine system and methods

A secure computer method enabling two or more processors to simultaneously access a shared external memory, the method comprising the steps of:

• selecting a processor from two or more processors to obtain a selected processor and one or more unselected processors, said selecting step occurring when each of the two or more processors require simultaneous access to a data item;
• aggregating by the selected processor instructions of each of the two or more processors to obtain aggregated instructions;
• accessing a memory by the selected processor to obtain a read value of the data item, wherein the data item is stored in a node of a binary tree structure, the node comprising a collection of data items;
• recording by the selected processor the read value of the data item;
• removing by the selected processor the data item from both the collection of the note and all other collections of other nodes along a path of the node;
• communicating by the selected processor to the one or more unselected processors the read value of the data item;
• routing the data item between the two or more processors until an ith processor holds the data item to be inserted to an ith node such that the data item is assigned a new position in the binary tree structure to obtain a new node comprising a corresponding path;
• and
• inserting by the selected processor the data item at the new node or along the corresponding path without revealing any information about the new node and the corresponding path to obtain a write value of the data item.