3PC honest-majority PRAM computation with perfect security and low overhead

In this thesis, we present new techniques for three-party secure computation in the parallel random access machine (PRAM) model. Our protocol is perfectly secure and concretely efficient. Considering a PRAM machine storing n w-bit words and having a large number (p = O(n)) of processors, and assuming at most one passively corrupt party, our construction exhibits the following properties: • Minimal cryptographic assumptions: By carrying out all computations using secret shares, our protocol achieves perfect security without any cryptographic assumptions. • Low communication complexity: To serve p queries to our PRAM in parallel, our construction requires only O(log^2(p) log(n)) + log(n/p) O(wlog(n) + log^2(n)) bits of transmission per query, amortized over the total number of queries. In our setting of p = O(n), this becomes O(w + log^3(n)), matching the known lower bounds on Oblivious RAM if w = Ω(log2(n)). The low constant factors in our construction also ensure that our protocol is concretely efficient. Specifically, with n = 225,w = 625, p = 216, n queries to our PRAM requires a transmission of 123130 bits per query. • Low round complexity: By carefully leveraging the inherent parallelism available in the PRAM model, we were able to reduce the round complexity of each query. To serve p queries to our PRAM in parallel, our construction requires only O(log^2(p) log log(n)) + log(n/p) O(log(p) + (log log(n))^2) ronuds of communications. When setting p = O(n), this becomes O(log^2(n) log log(n)), which states that our rounds scales only logarithmically in n. The low constant factors we have contribute to our protocol’s concrete efficiency, allowing it to serve each set of parallel queries in 4352 rounds in the same setting as above. Our protocol’s concrete efficiency, coupled with its ability to serve p queries in parallel, makes it appealing for real-world applications such as allowing p end users to simultaneously access a shared database and receive their results back in real time.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Chen, Zexiang

Contributors dc:contributor

• Heath, David

• Multiparty Secure Computation
• Secure Ram Computation

Statement dc:rights

• Copyright 2023 Zexiang Chen

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120111

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120111