2026-09-22T02:57:05Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/120111 2023-09-04 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Heath, David 2023-05 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms The student, Zexiang Chen, accepted the attached license on 2023-04-25 at 20:59. The student, Zexiang Chen, submitted this Thesis for approval on 2023-04-25 at 21:17. This Thesis was approved for publication on 2023-04-27 at 13:07. DSpace SAF Submission Ingestion Package generated from Vireo submission #19180 on 2023-09-01 at 16:55:35 3PC honest-majority PRAM computation with perfect security and low overhead Chen, Zexiang 2023-04-27 Multiparty Secure Computation Secure Ram Computation 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. Thesis eng https://hdl.handle.net/2142/120111 Copyright 2023 Zexiang Chen M.S. Thesis Computer Science University of Illinois at Urbana-Champaign Computer Science