Secure Computation with Parallel Calls to 2-ary Functions
Explore the concept of secure computation with parallel calls to 2-ary functions as discussed by Varun Narayanan, Shubham Vivek Pawar, and Akshayaram Srinivasan from UCLA, Royal Holloway, and the University of Toronto, respectively. Learn about the correctness, security, and simplicity measures involved in secure computation, including insights from previous works and the notion of simplicity in computing functions with constant input and output locality.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Secure Computation with Parallel Calls to 2-ary Functions Varun Narayanan, UCLA Shubham Vivek Pawar, Royal Holloway Akshayaram Srinivasan, University of Toronto
Secure Computation [Yao 86, GMW 87] ?1 ?:?? ? Correctness ?? ?2 . . . Learn ?(?1, ,??) ?5 ?3 ?4
Secure Computation [Yao 86, GMW 87] ?1 ?:?? ? Correctness Security ?? ?2 . . . Not learn anything about other inputs except ?(?1, ,??) ?5 ?3 ?4
Randomized Encodings [Yao 86, Ishai-Kushilevitz 00, Applebaum-Ishai-Kushilevitz 04] ?1 ?:?? ? ?? ?2 Securely compute ?(?1, ,??) . . . ?5 ?3 ?4
Randomized Encodings [Yao 86, Ishai-Kushilevitz 00, Applebaum-Ishai-Kushilevitz 04] ? 1 ?:? ? ? ?is simpler than ? ? ? ? 2 Securely compute ?(? 1, ,? ?) . . . ? 5 ? 3 ? 4
What is the measure of simplicity? Previous works equated simplicity with constant degree ? 1 ?:? ? ? ? ? ? 2 Securely compute ?(? 1, ,? ?) . . . ? 5 ? 3 ? 4
What is the measure of simplicity? ? can be a degree-2 function [BL18, GS 18] ? 1 ?:? ? ? ? ? ? 2 Securely compute ?(? 1, ,? ?) . . . Abstracted as MPRE [ABT 18] ? 5 ? 3 ? 4
Our Notion of Simplicity ? is a function with constant input and output locality. ? 1 ?:? ? ? ? ? ? 2 Securely compute ?(? 1, ,? ?) . . . ? 5 ? 3 ? 4
Our Model : Parallel Calls to 2-ary Functions We can convert any protocol in this model to one making calls to a function with constant input and output locality. [BL18,GS18] In the semi-honest setting, we can compute any degree-2 function with parallel calls to 2-ary functions. ??? ?,??;?? (??,1, ,??,?) ??,???,?,??,? ??,? ??? ??,??,? ? ?(?1, ,??) Is it complete against malicious adversaries?
Our Main Results Theorem: There exists a degree-2 function that cannot be securely computed against malicious adversaries with parallel calls to 2-ary functions. Theorem: Every degree-2 function can be securely computed against malicious adversaries with PwKO by making parallel calls to 2-ary functions. Theorem: Assume oblivious transfer. Then, every function can be securely computed against malicious adversaries by making parallel calls to 2-ary functions.
Negative Result Negative Result
Functionality ?1 ?4 This can be expressed as a degree-2 polynomial over binary Checks if ?1+ ?2+ ?3= 0 ?2 ?4 ?3 ?4
Impossibility Result ?1 ?4 ?1,3 ?1,2 ?2,3 ?2 ?4 ?3 ?4
Impossibility Result ?1 ?4 For any ? ????? ?1,2, the output of ??? is ?(?1,?2,?3) or . ?1,3 ?1,2 ?2,3 ?2 ?4 ?3 ?4
Impossibility Result ?1 ?4 For any ? ????? ?1,3, the output of ??? is ?(?1,?2,?3) or . ?1,3 ?1,2 ?2,3 ?2 ?4 ?3 ?4
Impossibility Result ?1 ?4 Encoding of ?1+ 1 Encoding of ?1 Find ? ????? ?1,2 such that the o/p is not . It is guaranteed to be ?(?1+ 1,?2,?3) Find ? ????? ?1,3 such that the o/p is not . It is guaranteed to be ?(?1,?2,?3) ?1,3 ?1,2 ?2,3 ?2 ?4 ?3 ?4
Positive Result Positive Result How to ensure that a corrupt party does not send inconsistent inputs?
A special CDS protocol See the paper for the details! ?1 ?4 We want the o/p of ?2,3 to be erased if ?1 is using inconsistent inputs ?1,3 ?1,2 ?2,3
Other Results Assuming one-way functions, we can compute any function with standard security against malicious adversaries with parallel calls to 3-ary functions. Assuming one-way functions, in the honest majority setting, we can compute any function with standard security against malicious adversaries with parallel calls to 2-ary functions.
Thank you! Thank you! https://eprint.iacr.org/2024/1701
