No Description

Ian Goldberg 12d1f91e51 Add MIT licence 1 month ago
docker 89999d96b6 Remove obsolete comment 2 months ago
LICENSE 12d1f91e51 Add MIT licence 1 month ago
Makefile 761610d33c Heap Sampler, including implementation, repro script, and log parser 4 months ago
README.md 114617031b Remove the repro directory from the main branch, and point to the popets-repro branch from the main branch's README 2 months ago
aes.hpp 3c86beb097 Change op_counter to aes_ops everywhere 1 year ago
avl.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
avl.hpp 3bf904d7d4 Have the AVL constructor default to optimized = true 5 months ago
bitutils.hpp ff2653d6ea Create wide RDPFs 1 year ago
bst.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
bst.hpp 9dfcf124ae Make MPCIO and MPCTIO objects non-copyable 5 months ago
cdpf.cpp f9fd97e396 Comparisons only need 114 AES operations, not 170 1 year ago
cdpf.hpp f9fd97e396 Comparisons only need 114 AES operations, not 170 1 year ago
cdpf.tcc 57a1dfd6cb Make CDPF::is_zero work for both RegAS and RegXS (as intended) 1 year ago
cell.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
cell.hpp d826b2e97f Putting the class back into hpp for cell 8 months ago
corotypes.hpp 62855f7b92 Online-only mode 1 year ago
coroutine.hpp e09f4e3f3b Keep separate track of the number of threads we can use for computation and for communication 1 year ago
dpf.hpp 64fa2cbc67 Move depth() from DPF to RDPF 1 year ago
duoram.cpp 650561d158 binary_search sometimes returned -1 instead of 1 when searching over a single item 4 months ago
duoram.hpp 62d835388b Merge branch 'avadapal/heaps' 5 months ago
duoram.tcc 54050bfc1e Have Shape::reconstruct reconstruct just the Shape and not the whole database 5 months ago
heap.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
heap.hpp 420d39d797 There were an incorrect number of "f"s in several instances of 0x7fffffffffffffff 4 months ago
heapsampler.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
heapsampler.hpp 761610d33c Heap Sampler, including implementation, repro script, and log parser 4 months ago
mpcio.cpp d469eee445 Try to make the players start within one latency of each other 4 months ago
mpcio.hpp 9dfcf124ae Make MPCIO and MPCTIO objects non-copyable 5 months ago
mpcio.tcc 89ecb9f81f Preprocessing and storage of incremental RDPFs 1 year ago
mpcops.cpp 8cd9db4713 Add mpc_reconstruct functions for RegXS, RegAS, RegBS 1 year ago
mpcops.hpp 8cd9db4713 Add mpc_reconstruct functions for RegXS, RegAS, RegBS 1 year ago
mpcops.tcc ff2653d6ea Create wide RDPFs 1 year ago
online.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
online.hpp 11c05623ec Add a timing test for DPF evalution 1 year ago
options.hpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
prac.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
preproc.cpp de44157928 Cleanly separate communication threads from CPU threads in the CLI 4 months ago
preproc.hpp 11c05623ec Add a timing test for DPF evalution 1 year ago
prg.hpp ff2653d6ea Create wide RDPFs 1 year ago
rdpf.cpp a9e39d265e Add a template parameter to RDPF, RDPFPair, RDPFTriple for the leaf width 1 year ago
rdpf.hpp 167fb6614a ORAM operations now reuse RDPFs when given the same OblivIndex object 1 year ago
rdpf.tcc c384b452a8 New RDPF2of3 struct 1 year ago
shapes.hpp 9bd6655f2e The Path Shape 1 year ago
shapes.tcc 9bd6655f2e The Path Shape 1 year ago
types.hpp 42eb384dcd Add operator<< for RegAS 4 months ago

README.md

PRAC: Private Random Access Computations

Ian Goldberg, iang@uwaterloo.ca
Sajin Sasy, ssasy@uwaterloo.ca
Adithya Vadapalli, avadapalli@cse.iitk.ac.in

PRAC implements three-party secure computation, with a particular focus on computations that require random access to memory. Parties 0 and 1 are the computational peers, while party 2 is the server. The server aids the computation, but generally does much less than the two computational peers.

This work appeared in:

Sajin Sasy, Adithya Vadapalli, Ian Goldberg. "PRAC: Round-Efficient 3-Party MPC for Dynamic Data Structures". Proceedings on Privacy Enhancing Technologies 2024(3). https://eprint.iacr.org/2023/1897.


Looking for the reproduction instructions?

The reproduction instructions for the PoPETs paper are in the README file in the repro directory of the popets-repro branch.


The multi-party computation (MPC) makes use of resources, most notably multiplication triples and distributed point functions (DPFs). These resources can be precomputed; they are independent of the values in the computation being performed, so you only need to know how many of each you'll need.

PRAC has three modes:

  • Precomputation mode

    • In this mode, the parties precompute all of the resources they will need in the online phase. The resources will be stored in files on disk.
  • Online mode

    • In this mode, the parties perform the actual computation, using the resources stored by an earlier precomputation mode.
    • Note: using resources during online mode does not currently delete them from disk; this is to facilitate timing tests that run the online mode many times, for example with differing numbers of threads or networking configurations. This is insecure when used in practice, however; be sure to never use a precomputed resource for more than one computation, or private information may be leaked!
  • Online-only mode

    • In this mode, there is no precomputation; all of the required resources are computed on the fly, as needed. At the end of the run, the number of each resource so computed will be output, so that you can feed that into a precomputation mode for next time.

PRAC supports two kinds of threading: communication threads and local processing threads.

  • Communication threads allow multiple independent subproblems to be performed at the same time, where each subproblem requires multi-party interaction.
  • Local processing threads allow individual parties to perform large local computations (for example, computing large local dot products) in a multithreaded manner, without interacting with other parties.

Currently, all of the interesting multithreading (except for some unit tests) are local processing threads.

Non-docker instructions:

Build with make. The build has been tested on Ubuntu 20.04 and Ubuntu 22.04. You'll need libbsd-dev and libboost-all-dev.

You'll need three terminals with the built binary, either on the same machine, or different machines. If it's on the same machine, it's OK for them all to be in the very same directory; the saved resources for the different parties won't clobber each other.

In each terminal, run ./prac opts player_num player_addresses args

  • player_num is 0, 1, or 2
  • player_addresses is:
    • for player 0: nothing (just leave it out)
    • for player 1: player 0's hostname
    • for player 2: player 0's hostname followed by player 1's hostname
    • (you can use IP addresses instead of hostnames if you want)

For preprocessing mode:

  • opts should be -p to indicate preprocessing mode
  • You can also add -a to indicate that the resources being computed should be appended to existing resource files, rather than replacing them. This is useful if you want to create for example a large number of large DPFs. Each DPF creation consumes a lot of memory, and all the DPFs are computed simultaneously in order to save network round trips. To compute them in smaller batches if your memory is limited, run ./prac several times, each with the -a option.
  • The -e option means to store precomputed DPFs in expanded form. This can take a lot of disk space for large DPFs, and depending on your disk speed and CPU capabilities and number of local processing threads, it can actually be faster to recompute the expansion than to read it from disk.
  • Use the -C num option to enable num communication threads. As above, this is probably not what you want.
  • Use the -t num option to enable num local processing threads.

Then the args specify what resources to compute. You actually only need to provide the args to player 2 (the server) in preprocessing mode; it will inform the other players what is being computed. The other players will ignore their arguments in preprocessing mode.

The args in preprocessing mode are each of the form type:num to indicate to create num resources of the given type. The available types include:

  • m: a multiplication triple
  • h: a multiplication half-triple
  • a: an AND triple
  • s: a select triple
  • rd: A DPF of depth d for random accesses to memory (RDPF). A DPF of depth d can be used to process 2d memory locations. Can optionally take a suffix .w (for example, r26.3) where w is an integer between 1 and 5 to indicate the width of the RDPF (the default is 1).
  • id: An Incremental DPF of depth d for random accesses to memory (IDPF). Can take an optional width suffix as above.
  • c: a DPF for comparisons (CDPF)

If you do have multiple communication threads, you can optionally specify different sets of resources to create in each one by prefixing communication thread i's list with Ti (i starts at 0). If the args do not start with such an indication, each communication thread will use a copy of the provided list.

Example: In three terminals on the same host, run:

  • ./prac -t 8 -p 0
  • ./prac -t 8 -p 1 localhost
  • ./prac -t 8 -p 2 localhost localhost m:100 r6:10 r20:5 c:50

to create 100 multiplication triples, 10 RDPFs of depth 6, 5 RDPFs of depth 20, and 50 CDPFs, using 8 local processing threads.

For online mode:

The useful options in online mode are:

  • -C num specifies the number of communication threads to use.
  • -t num specifies the number of processing threads to use.
  • -x indicates that you wish to use an XOR-shared memory instead of the default additive-shared memory. Some computations can work with either type (and respect this option) while others cannot (and ignore this option).

The args in online mode specify what computation to do. These are mostly unit tests and benchmarks. The interesting ones for now:

  • duoram depth items: in a memory of size 2depth, do items dependent updates, items dependent reads, items independent reads, items independent updates, items dependent writes, and items dependent interleaved reads and writes. Each batch is timed and measured independently.
  • read depth items: similar, but only time dependent reads.
  • bbsearch [-r] depth iters: iters iterations of basic binary search on an array of size 2depth-1. The -r flag means to generate (and sort, so it's more expensive) a random array rather than using a pre-sorted array.
  • bsearch [-r] depth iters: as above, but for our optimized binary search rather than the basic one.
  • heap -m maxsize -d datasize -i numinserts -e numextracts -opt optflag -s sanityflag: the heap benchmark. Allocate a heap of maximum size 2maxsize-1 elements, and initialize the first 2datasize elements of it. Perform numinserts insertions and numextracts extractions. Set optflag to 1 to use the optimized heap algorithms, or 0 otherwise. Set sanityflag to 1 to check the results after each operation, or 0 otherwise.
  • avl -m size -i numinserts -e numextracts -opt optflag -s sanityflag: the AVL benchmark. Initialize an AVL tree with 2size elements. Insert numinseerts more elements, and delete numextracts elements. Set optflag to 1 to use the optimized AVL algorithms, or 0 otherwise. Set sanityflag to 1 to check the results after each operation, or 0 otherwise.
  • avl_tests: unit tests for the AVL algorithms
  • heapsampler n k: the heap-based oblivious stream sampler benchmark. Obliviously select a random subset of k elements from a stream arriving one element at a time, using O(k) memory. Stop after n elements.

It is vital that all three players are told the same computation to run!

The output of online mode (for each player) includes timings (real and CPU time), the number of messages sent, the number of message bytes sent in total, the Lamport clock (the number of network latencies experienced), and the number of local AES operations performed (each AES operation is an encryption of a single block), as well as the list of the number of precomputed resources used in each communication thread.

Example: In three terminals on the same host, run:

  • ./prac -t 8 -p 0
  • ./prac -t 8 -p 1 localhost
  • ./prac -t 8 -p 2 localhost localhost r20:90

to complete the preprocessing required for the following computation, using 8 threads, and then:

  • ./prac -t 8 0 duoram 20 10
  • ./prac -t 8 1 localhost duoram 20 10
  • ./prac -t 8 2 localhost localhost duoram 20 10

to do the online portion of the computation, also using 8 local processing threads.

For online-only mode:

The options and arguments are the same as for online mode, only you also add the -o option, and you don't have to have run preprocessing mode first. At the end of the run, PRAC will output the number of resources of each type created, in a format suitable for passing as the arguments to preprocessing mode.

Example: In three terminals on the same host, run:

  • ./prac -o -t 8 0 duoram 20 10
  • ./prac -o -t 8 1 localhost duoram 20 10
  • ./prac -o -t 8 2 localhost localhost duoram 20 10

No separate preprocessing step is needed.

Docker instructions:

  • cd docker
  • ./build-docker
  • ./start-docker
    • This will start three dockers, each running one of the parties

Then to simulate network latency and capacity (optional):

  • ./set-networking 30ms 100mbit

To turn that off again:

  • ./unset-networking

If you have a NUMA machine, you might want to pin each player to one NUMA node. To do that, set these environment variables before running ./run-experiment below:

  • export PRAC_NUMA_P0="numactl -N 1 -m 1"
  • export PRAC_NUMA_P1="numactl -N 2 -m 2"
  • export PRAC_NUMA_P2="numactl -N 3 -m 3"

Adjust the numactl arguments to taste, of course, depending on your machine's configuration. Alternately, you can use things like -C 0-7 instead of -N 1 to pin to specific cores, even on a non-NUMA machine.

Run experiments:

  • ./run-experiment opts args
    • opts and args are those of ./prac above, not including the player number and other players' addresses, which are filled in automatically. The number of processing threads for each player is also automatically set to the number of cores available in the given PRAC_NUMA_P{0,1,2} configuration.

When you're all done:

  • ./stop-docker
    • Remember this will lose anything you've saved on the docker filesystem, most notably any precomputed resources.