Ensuring Credible Private Set Membership with Efficient Communication
Credibility in Private Set Membership
Sina Shiehian
Sanjam Garg
Mohammad Hajiabadi
Abhishek Jain
Zhengzhong Jin
Omkant Pandey
UC Berkeley
Waterloo University
Johns Hopkins University
MIT
Stony Brook University
Snap Inc.
P
r
i
v
a
t
e
S
e
t
M
e
m
b
e
r
s
h
i
p
(
P
S
M
)
Application:
Exposed Password Checker
Other Applications:
Private contact discovery [Mar14]
Issue:
Credibility
...
...
DB
Credibility
:
Any malicious server
shouldn’t
convince the
client that (a high-entropy) password is in DB.
Our Goal:
Round Optimal Protocol (2 rounds)
Our Def:
Credible
Private
Set Membership
DB
:
Client
...
...
Accept
/
Reject
Our Def:
Credible
Private
Set Membership
DB
:
Client
...
...
Accept
/
Reject
Server Privacy:
Our Def: Credible
Private Set Membership
Reject!
DB
:
...
...
Prior Approaches
Password
0x24152ab
Match!
Non-back-box Use of Crypto Primitive
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
Credible private set membership protocol with
trusted transparent setup
from LWE. (almost black-box, except bootstrapping in FHE)
Starting Point:
Commit
-and-Prove
Server
Client
HE: Malicious secure
homomorphic encryption [IP07]
Background
:
S
omewhere
S
tatistical
B
inding Hash (SSB)
[Hubacek-Wichs’15, Okamoto-Pietrzak-Waters-Wichs’15]
Normal Mode
Trapdoor Mode
Can be constructed from LWE
[Hubacek-Wichs’15]
/ DDH
[Okamoto et. al]
in a Merkle-tree style.
Proving
Credibility
Server
Client
(SSB Hash)
Avoid non-black-box use of hash?
Background
:
Zero-Knowledge via
MPC-in-the-Head
[IKOS’17]
4-Round
Protocol
Compress to 2 rounds?
R
e
c
a
l
l
:
2
-
r
o
u
n
d
O
b
l
i
v
i
o
u
s
T
r
a
n
s
f
e
r
(
O
T
)
Sender
Receiver
Compress
4-round
to
2-round
HE
HE
=
...
Thank you!
Q & A
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
