Questions tagged [private-set-intersection]
In a private set intersection (PSI) protocol two parties jointly compute the intersection of their private input sets.
58 questions
1 vote
2 answers
539 views
Why is naive hash based Private Set Intersection insecure?
I know that when the domain of the set is very small, we can enumerate the elements in the set, and in that case, a simple hash-based method is not secure. However, when the domain is very large, such ...
- 119
1 vote
0 answers
56 views
Is there any possible way to make each party obtain the output in a MPC protocol?
I konw a fact that it is impossible to achieve complete fairness in 2-party protocol from Cleve's paper.But i wonder if it is possible to achieve fairness in multi-party setting when the number of ...
- 119
1 vote
2 answers
138 views
Private set intersection using homomorphic encryption
I have a question regarding the scheme below. PSI using homomorphic encryption appears to subtract the plaintext into the ciphertext. I understand that homomorphism is maintained in operations between ...
- 13
1 vote
1 answer
110 views
Design a multi party Private Set Intersection protocol with unconditional zero-sharing
Unconditional zero-sharing was presented in the following paper Practical Multi-party Private Set Intersection from Symmetric-Key Techniques, by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike ...
- 119
1 vote
2 answers
97 views
How to avoid sender modify the final output in private set intersection under malicious setting?
I'm relatively new to this topic, and I have a question that might seem basic. I appreciate your patience. In most PSI schemes(2 party or multi party),the intersection result is always output by only ...
- 119
0 votes
1 answer
97 views
Fast Private Set Intersection from Homomorphic Encryption
I encountered a question while reading an article. My understanding is that fully homomorphic encryption supports ciphertext addition and multiplication. Why does the basic protocol given in this ...
- 1
0 votes
1 answer
144 views
Shamir secret sharing, recovery of keys which have 0 bytes in front of them?
From what I know SSS creates a polynomial with a0 = secret key and interpolates it on recovery using k coeffs. if a0 is a number,...
- 33
3 votes
1 answer
98 views
Private Matching Problem
I am here to ask a question on the current progress of private matching problem. Say, a user has a keyword (e.g. "apple") and a server holds a database of fruit records. Suppose the DB has ...
- 159
3 votes
2 answers
836 views
Practical implementations of Private Set Membership
Problem Statement Imagine you have a set (no duplicate elements) e.g. S1 = {'a', 'b', 'c'}. You wish to share a private (and ideally both small in size and ...
- 153
2 votes
0 answers
83 views
For unequal set sizes in PSI: why should the party with fewer elements use cuckoo hash rather than simple hash?
Most PSI papers usually use hash-to-bin to improve the number of comparsons. For unequal set sizes in 2PSI, I have read CCS17, which designs a PSI protocol for unequal size. The party with fewer ...
- 21
1 vote
1 answer
571 views
The Diffie-Hellman-based Private set intersection protocol cannot pass simulation proof?
Given the popular Private Set Intersection (PSI) protocol first described in [1]: Alice choose a random $a$, and sends $\{H(x_i)^{a}\bmod p\}| (i=1,...m)$ to Bob. Bob choose a random $b$, and sends $\...
- 304
0 votes
1 answer
84 views
How to extend operations from numbers to larger "objects" in cryptographic implementations?
I know I'm not supposed to roll my own crypto, but everyone starts somewhere! I'm implementing the PSI-CA protocol defined in Fast and Private Computation of Cardinality of Set Intersection and Union (...
1 vote
0 answers
40 views
Is it possible to Publicly Query Privately Held Data with proof of Correctness?
We can secretly query inputs from a public DBs using what we call in the literature PIR. We can secretly query inputs from a privately held DB by means of Private Set Intersection (PSI). We can also ...
- 892
2 votes
1 answer
558 views
Efficient private set intersection protocol for small sets
I need to implement a PSI that will be used on mobile devices to find mutual contacts. Assuming the set cardinality from both parties A and B are less than 1000, what would be the most efficient PSI ...
- 277
0 votes
1 answer
261 views
In Microsoft Password Monitor implementation using HME how do they perform ComputeMatch Function?
https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/ In this they mention The server then evaluates a matching function on the encrypted credential,...
- 1