Efficient Cryptography: Commitments, Arguments, and RAM MPC
Explore the world of efficient cryptography with a focus on commitments, arguments, and RAM MPC. Learn how to execute crypto protocols over large data without paying linear time in input size. Discover ways to achieve small communication while addressing the issue of linear runtime inherent for security.
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
Doubly Efficient Cryptography: Commitments, Arguments and RAM MPC Daniel Wichs Northeastern & NTT Research Wei-Kai Lin Northeastern Ethan Mook Northeastern Soft Merged with: Reusable Online-Efficient Commitments Omer Paneth Nir Bitansky Dana Shamir
Crypto over large inputs Goal: Execute crypto protocols over large data without paying linear time in input size - e.g. MPC for RAM functionalities ?5
Crypto over large inputs Goal: Execute crypto protocols over large data without paying linear time in input size - e.g. MPC for RAM functionalities ?5 Many crypto protocols can achieve small communication, but what about runtime?
Crypto over large inputs Goal: Execute crypto protocols over large data without paying linear time in input size - e.g. MPC for RAM functionalities ?5 Many crypto protocols can achieve small communication, but what about runtime? Problem: Linear runtime is often inherent for security any location not touched must not have been used
Crypto over large inputs Goal: Execute crypto protocols over large data without paying linear time in input size - e.g. MPC for RAM functionalities ?5 ?5 Many crypto protocols can achieve small communication, but what about runtime? Problem: Linear runtime is often inherent for security Core Question: Can we push all linear time overheads into an offline preprocessing phase?
Doubly Efficient Primary Information Retrieval (DEPIR) Prep runtime: ?1+? ? [|?|] ? ?,? Query(?) ? ? ? Resp(?, ?) Online runtime: polylog( ? ) Dec ?,? = ?[?] Goal: Retrieve ?[?]without revealing ? Prior work: [LMW 23] construct DEPIR from RingLWE
Doubly Efficient CRHF An interactive commitment protocol ? Gen(1?) ? ? ? ?(?) Security: Standard CRHF binding Efficiency: ?(?) can be computed from ?in sublinear time
A Trivial Solution CRS = ? Gen(1?) ?(?) ? ?(?) CRS model trivializes the problem! But unsatisfying: You have to preprocess again for anyone who doesn t trust the CRSCan we do it in the plain model?
Doubly Efficient CRHF Adapting the construction of [IKO 05] ? [|?|] ? = ? (?,?) Query(?) ? ? ?? = Resp( ?,?) Any collision ? ? with ?? = ?(? ) must have ? ? = ? [?] But this violates DEPIR security! DEPIR preprocessing
Doubly Efficient CRHF Adapting the construction of [IKO 05] Prep runtime: ?1+? ? [|?|] ? = ? (?,?) Query(?) ? ? ?? = Resp( ?,?) Hash runtime: polylog( ? ) Result: DE-CRHF in the plain model with the same efficiency as DEPIR DEPIR preprocessing Local Opening?: Standard Merkle tree requires constructing the tree afterknowing the seed linear online run time
Doubly Efficient Commitments with local opening ?(|?|) stores private commitment digest ? Com Commit phase Open phase Open ? ? ?(?,?) ? {?[?], } Result: DE commitments with |?|1+? preprocessing and online runtime polylog( ? ) Up next: Fixed! Caveat: Only reusable if sender never learns if receiver accepts
Doubly Succinct Arguments Prover Verifier ? ? ? ? Checks that ? ?,? = 1 Preprocess once, then prove for to many verifiers
Doubly Succinct Arguments just do Kilian Com Commit to ? ? ? ? ? [|?|] ? Verifier sends PCP queries Open Generate & Preprocess a PCP Open to ?[?] Check openings and PCP verifier
RAM-MPC Prior work [GKK+ 12]: RAM-MPC in a joint preprocessing model Preprocessing not reusable in different groups ?4
RAM-MPC CRS Prior work [GKK+ 12]: RAM-MPC in a joint preprocessing model Preprocessing not reusable in different groups ?4 Would be interesting in the CRS model - e.g. RAM-MPC implies DEPIR
RAM-MPC Prior work [GKK+ 12]: RAM-MPC in a joint preprocessing model Preprocessing not reusable in different groups ?4 ?4 Would be interesting in the CRS model - e.g. RAM-MPC implies DEPIR Our work: Maliciously secure RAM-MPC with preprocessing in the plain model
Semi-Honest RAM MPC Goal: Compute ?(?1, ,?5) Start with trusted RAM processor ORAM ORAM ?5 ?5 ?5 ?5 ?5 ?5 ?? ? Implement trusted processor using standard MPC Use DEPIR to access each party s input Convert trusted processor to circuit by offloading local memory to ORAM
Fully secure RAM MPC Goal: Compute ?(?1, ,?5) ORAM ORAM ?5 ?5 ?5 ?5 ?5 ?5 ?? ? Result: Can upgrade to malicious security by committing to each input and proving each step is correct Technical Challenge: Need to enforce consistency between committed value and statement for proofs
