{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120111"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120111","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"3PC honest-majority PRAM computation with perfect security and low overhead","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Chen, Zexiang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Heath, David"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:56Z","subjects":["Multiparty Secure Computation","Secure Ram Computation"],"languages":["en","eng"],"rights":["Copyright 2023 Zexiang Chen"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120111","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Heath, David"]},{"key":"dc:creator","label":"Author","values":["Chen, Zexiang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-04-27"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Multiparty Secure Computation","Secure Ram Computation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Zexiang Chen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120111"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["3PC honest-majority PRAM computation with perfect security and low overhead"]}]}],"canonical_facts":{"dc:contributor":["Heath, David"],"dc:creator":["Chen, Zexiang"],"dc:date":["2023-05","2023-04-27"],"dc:description":["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","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120111"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Zexiang Chen"],"dc:subject":["Multiparty Secure Computation","Secure Ram Computation"],"dc:title":["3PC honest-majority PRAM computation with perfect security and low overhead"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:56Z"}