Garbling Schemes without Privacy: Exploring Secure Function Evaluation
Delve into the concepts of garbling schemes without privacy, secure function evaluation, and passively secure 2PC by Carsten Baum from Aarhus University. Explore the properties, challenges, and strategies for achieving security in cryptographic protocols.
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
On Garbling Schemes with and without Privacy Carsten Baum, Aarhus University
Secure Function Evaluation Carsten Baum, Aarhus University Submit to SCN? No! Si! 2 no no
Garbling Schemes [BHR12] Given function ?, input ?, algorithms (Gb, En, Ev, ev, De) Carsten Baum, Aarhus University Properties: Privacy (simulate ?,?,? that evaluate to ?) Obliviousness (?,? leak nothing about ?,? ) Authenticity (?,? do not allow to obtain another valid ? ??(?,?) 3
Passively secure 2PC Carsten Baum, Aarhus University Input a Input b ?,?1 ? 1. ?,?,? ??(?), ? = ?0 ? [2?] ?+?} via OT 2. Obtain {?? ? ? 3. Send ?,{?? ? } 4. ? = ?(?) 4 5. Decode ? = ??(?)
Going to active security Alice can garble wrong function (Obliviousness), not actively secure! Cut and Choose: Alice makes lots of circuits. Bob checks half, evaluates rest. Carsten Baum, Aarhus University Currently best lots of : ? circuits for security 2 ? [Lin13,HKE13,Bra13]. 5
Large overhead Do we have to garble ? circuits to achieve security 2 ?? Can do better for certain functions: Construct garbling scheme for function [KW13]. Carsten Baum, Aarhus University This work: Combine multiple garbling schemes to reduce overhead. Concurrent work by [KMW16]. 6
Decomposable functions Some part of the circuit depends on input from Alice or Bob only. Carsten Baum, Aarhus University Maybe we can save on ??,??? Think about input validation, signature verification etc 7
Attempt 1: Dont garble it What happens if we do not garble ??,??? Carsten Baum, Aarhus University Input into ? may not be in ?????(? ). Example: If ?? validates ? and ??? = then Alice could input x, instead of ?, . 8
Verifying inputs Alice, Bob must give proof that their input is in ?????(? ). Type equation here. Carsten Baum, Aarhus University Bob could give ZK proof using a commitment to input, but may be inefficient over ?2(non-algebraic statement). Even more difficult for Alice no commitment! Alternative idea: ? must verify this proof! 9
Attempt 2: Garble it again?? Example: Proof by Alice. (similar to [JKO13]) 1. Bob garbles ??as ??and sends it to Alice. 2. Alice has output keys of ?? -> proof that she computed ??. 3. Bob opens ?? and shows that it is a garbling of ??. Carsten Baum, Aarhus University How can Alice check that ??is correct garbling?? 10
Privacy-free garbling [FNO15] Given function f, input x, algorithms (Gb, En, Ev, ev, De, Ve) ?,? Carsten Baum, Aarhus University Properties: Authenticity: ?,? do not allow to obtain another valid ? ??(?,?) Verifiability: If x ?,? ? = ? ? ,?? ?,? = 1 then ?? ?,?? ?,? = ??(?,?? ?,? ) 11
Attempt 2: Garbling Using privacy-free garbling: Authenticity: If Alice presents keys of ?? to Bob, then she computed ga(?). Verifiability: These keys leak no information about ? when shown to Bob. Carsten Baum, Aarhus University Are we done?? Cannot make keys public: ?? is not one-way! 12
Attempt 3: One-time pad 1. Alice chooses ?,? 2. Bob garbles ?? 3. Alice evaluates garbling. Opens result to Bob. (?,?) = ?? ? ? Carsten Baum, Aarhus University 4. Alice computes r = ?? ? . 5. Alice inputs ?,? into ? (?? (?,?) is public input) 6. ? checks that r ? = ?? (?,?) (with active security) Problem in ?: Alice can input ? ? 13
Attempt 4: Hashing 1. Bob chooses some hash function ?, garbles ?? 2. Alice garbles ? with additional check for , sends her input keys. 3. Bob reveals ?, Alice evaluates ?? 4. ?,?,? = ???? ? Carsten Baum, Aarhus University . Caveat: 1. What if ?is complex function? 14
Universal hashing Universal hashing: 1. Choose ? 0,1?+? 1 ?1 ?2 ?? ?2 ?3 ?? ??+1 ??+? 1 0,1? ? 2. Compute ? = Carsten Baum, Aarhus University ??+1 ? = ? ? 3. 2 ? Property: ?,?:Pr ? = ? 15 Bob chooses ? after Alice commits to inputs.
Construction in detail Carsten Baum, Aarhus University 16
Evaluating In order to save computation of ?? we compute . Does that make sense? Observation: Carsten Baum, Aarhus University For certain protocols, we obtain ???? ? for free! Based on consistency check in [Ss13,FN13]. 17
Observation in [Ss13,FN13] Alice garbles ? instances of ?. Alice afterwards sends her input keys for each instance. Input keys may be inconsistent! Carsten Baum, Aarhus University Solution: Compute cheap hash, output to Bob. Bob chooses ?, output must be secret to not reveal ?. In the paper: How to embed our approach into [FJN14] protocol. 18
Conclusion Consider decomposable circuits: Carsten Baum, Aarhus University Then you do not need active security everywhere. Reduce overhead for certain interactive computations. 19
Why does Bob not hash? For all ? instances Bob obtains input keys for GC using OT Carsten Baum, Aarhus University Send keys for ? for actively secure computation together with privacy-free computation No hash needed! Less overhead 21
