Ensuring Credible Private Set Membership with Efficient Communication
Explore the concept of credible private set membership ensuring server privacy, client privacy, and data credibility through innovative protocols and approaches. The focus is on maintaining high-entropy passwords securely while optimizing rounds and leveraging underlying crypto primitives efficiently.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Credibility in Private Set Membership Sina Shiehian Sanjam Garg Mohammad Hajiabadi Zhengzhong Jin Omkant Pandey Abhishek Jain Snap Inc. Stony Brook University UC Berkeley Waterloo University Johns Hopkins University MIT
P Private S Set M Membership (PSM) Server Client ? ... DB: ? ?DB ... DB learns nothing about ? Client only learns ? ?DB
Application: Exposed Password Checker ... qwerty123 Leaked password DB ... Other Applications: Private contact discovery [Mar14]
Issue: Credibility ... qwerty123 DB ... Update password Credibility: Any malicious server shouldn t convince the client that (a high-entropy) password is in DB.
Our Def: Credible Private Set Membership Client ... ? DB: Our Goal: Round Optimal Protocol (2 rounds) Accept / Reject (? = equality : Password checker) ... Client Privacy: ?
Our Def: Credible Private Set Membership Client ... ? DB: Accept / Reject ... Server Privacy: Sim: Server ? ??? Sim(?????? ? ??? ,?????? {0,1})
Our Def: Credible Private Set Membership ... ? DB: Reject! ... Credibility If ?~?has high entropy , i.e. ?: Pr ?~?? ?,? = 1 negl Client rejects for a random ?~?.
Prior Approaches Client ... qwerty123 0x24152ab DB: Communication |DB| 123ABC! 0x12a315c Oblivious PRF Password 0x24152ab Match! PRF ... Client Non-back-box Use of Crypto Primitive DB: , zk-SNARK Hash
Question Can we build credible private set membership with both 1. sublinear communication, and 2. black-box use of underlying crypto primitives?
Our Result For Equality Relation (Password Checker) Black-box credible private set membership protocol in plain model from Learning with Errors (LWE)/Decisional Diffie-Hellman (DDH). For Efficiently Searchable Relation Black-box credible private set membership protocol with trusted transparent setup from LWE/DDH. For Bounded-depth Searchable Relation A relation ?( , ) is efficiently searchable, if a branching program ???(?) of length ?(log ?? ) that outputs the index ? s.t. ? ?,?? ? Credible private set membership protocol with trusted transparent setup from LWE. (almost black-box, except bootstrapping in FHE) = 1.
Starting Point: Commit-and-Prove HE: Malicious secure homomorphic encryption [IP07] Server Client HE ... ? Com(?) ... Zero-Knowledge Proof ? & its local opening for ? ?,? = 1 , HE Intuition: is outside of FHE Independent of ?
Background: Somewhere Statistical Binding Hash (SSB) [Hubacek-Wichs 15, Okamoto-Pietrzak-Waters-Wichs 15] Trapdoor Mode Normal Mode ? ? (?) ? ? ?(?,?1,??, ,??) ? ?(? ,?1,??, ,??) Extraction:?? Ext(td,?) Can be constructed from LWE [Hubacek-Wichs 15] / DDH [Okamoto et. al] in a Merkle-tree style.
Proving Credibility Server Client (SSB Hash) HE ... ? Com(?) ... Zero-Knowledge Proof ? & its local opening for ? ?,? = 1 , HE Extract a random location: ? Avoid non-black-box use of hash? With Pr. 1/????, ? = ? ? ?,? = 1, which is unlikely for high entropy ?
Background: Zero-Knowledge via MPC-in-the-Head [IKOS 17] Secrete share ? = ?1 ?2 ?? Com(????1),Com(????2), ?1 ? ? , ? < ?/3 ?2 ?4 Open ????? ? ? ?3 Jointly Compute ?(?,?1 ?2 ?3 ?4)
4-Round Protocol ? HE ... = , Com(????1),Com(????2), HE DB1 DB? DB DB2 ? [?] Open ????? ? ?, local opening for in ? HE Compress to 2 rounds?
Recall: 2-round O Oblivious T Transfer (OT) Sender Receiver OT1 ? {0,1} ?0,?1 OT2 Get ?? Sender Security: hide ?1 ? Receiver Security: hide ?
Compress 4-round to 2-round ? OT1(?) HE ... = , Com(????1),Com(????2), HE DB2 DB1 DB? DB ? [?] Open ????? ? ?, local opening for ? OT2( View? ?,local openings) HE
Thank you! Q & A
