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

Chen, Zexiang

Permalink

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

Description

Title

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

Author(s)

Chen, Zexiang

Issue Date

2023-04-27

Director of Research (if dissertation) or Advisor (if thesis)

Heath, David

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

Multiparty secure computation, secure RAM computation

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Zexiang Chen

Owning Collections