Skip to main content

Questions tagged [private-set-intersection]

In a private set intersection (PSI) protocol two parties jointly compute the intersection of their private input sets.

Filter by
Sorted by
Tagged with
1 vote
0 answers
35 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 ...
Rui T.'s user avatar
  • 31
0 votes
0 answers
24 views

How to implement a SKE scheme supporting single-message multi-ciphertext using LowMC and GMW?

I currently have a LowMC scheme and a GMW scheme. How can I implement a symmetric encryption scheme that supports single-message multi-ciphertext? In simple terms, I want to implement a protocol like ...
song's user avatar
  • 11
1 vote
2 answers
82 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 ...
shs's user avatar
  • 13
1 vote
1 answer
48 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 ...
Rui T.'s user avatar
  • 31
1 vote
2 answers
53 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 ...
Rui T.'s user avatar
  • 31
0 votes
1 answer
71 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 ...
wzh's user avatar
  • 1
0 votes
1 answer
122 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,...
CipherNewbie's user avatar
3 votes
1 answer
79 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 ...
alexander's user avatar
  • 149
3 votes
2 answers
566 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 ...
JoeKir's user avatar
  • 143
2 votes
0 answers
69 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 ...
freely's user avatar
  • 21
1 vote
1 answer
450 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 $\...
vince.h's user avatar
  • 147
0 votes
1 answer
68 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 (...
John Smith's user avatar
1 vote
0 answers
31 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 ...
DaWNFoRCe's user avatar
  • 872
2 votes
1 answer
366 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 ...
tarun14110's user avatar
0 votes
1 answer
224 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,...
Naveen S's user avatar
2 votes
1 answer
343 views

Questions on PRF

Define three hash functions: $H_1: \{0, 1\}^* \rightarrow \mathbb{G}$ mapping $x$ to the group $\mathbb{G}$ of prime order $q$ $H_2: \mathbb{G} \rightarrow \{0, 1\}^\tau$ $H_3: \{0, 1\}^* \times \...
D.V.'s user avatar
  • 151
3 votes
1 answer
73 views

How to find common answers without revealing differences?

Say Bob and Alice are trying to figure out the fruits they like, but don't want to reveal the fruits they dislike. How could they compare their list of liked fruits and reveal only the common set to ...
saucewaffle's user avatar
0 votes
0 answers
54 views

Is blinded mixing possible?

Alice creates ordered set of $N$ public messages $(m_1,...,m_N)$ and sequentially sends them to Bob. Bob evaluates $N$ functions $E_i(m_1,...,m_N)$ (possibly using a secret random value $r$ and/or his ...
DeLorean88's user avatar
3 votes
1 answer
102 views

Correctness of signle-point Oblivious PRF

In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a ...
vxek's user avatar
  • 467
1 vote
1 answer
294 views

Hash into elliptic curves for private set intersection

Would it be insecure to hash a message $m$ to an elliptic curve point by multiplying it to some generator $G$ for the purpose of a private set intersection ? $$ M = hash(m) * G $$ I keep seeing ...
braincoke's user avatar
  • 113
2 votes
1 answer
385 views

Negative numbers with additive ElGamal

I'm trying to implement Private Set Intersection using the additive ElGamal public key encryption system. The code I've written can encrypt and decrypt numbers using the ElGamal system, so far so good....
progician's user avatar
  • 135
4 votes
1 answer
98 views

Multiparty dataset intersection count

Typically, Private Set Intersection (PSI) protocols let you learn the subset of items on each party's dataset that are in the intersection. The problem in this case is a relaxation of these kind of ...
DaWNFoRCe's user avatar
  • 872
1 vote
2 answers
206 views

AES ECB deterministic encryption to perform Private set intersection

There are two parties, and each has a list of plain-texts. My end goal is to assign indices to unique plain-texts across both parties. My present approach is the following. Both parties perform a ...
Sachin Kumar's user avatar
1 vote
0 answers
63 views

Can two anonymous parties determine whether they interacted before, without being able to link encounters?

Assume an anonymous communication system in which anonymous parties randomly meet in pairs to exchange information. How could two anonymous parties determine whether they have interacted before, ...
oc512's user avatar
  • 21
1 vote
2 answers
162 views

How can a client privately query a subset of a database?

I am trying to build a solution for the following problem and I think it is relevant to crypto: Party A has a set of indexes M, such as a group of people's ID; Party B has information of a larger ...
S. Luo's user avatar
  • 11
2 votes
1 answer
149 views

Is there any Private Set Intersection scheme that only leak whether intersect or not without the real intersection value?

If there are two people Alice and Bob, and each has one set. They want to know whether their sets have intersect or not. Is there any Private Set Intersection scheme that only leak whether intersect ...
Felix LL's user avatar
  • 321
0 votes
1 answer
68 views

Is it possible to construct dataset for only another party to consult?

Is it possible to construct a dataset made of some kind of probabilistic encrypted indexes such that anyone can update the information contained in the set but only the one with a secret key could be ...
Afonso Delgado's user avatar
1 vote
1 answer
412 views

is there a problem with the following private set intersection protocol

Say Alice has the following set: $\{A_1,A_2,\ldots,An\}$ and Bob has the following set: $\{B_1,B_2,\ldots,B_m\}$ Alice creates a key $a$ and bob creates a key $b$ these keys should be commutative (...
user11466558's user avatar
2 votes
1 answer
220 views

how do we calculate set intersection using homomorphic encryption?

I am new to this field. I want to learn how homomorphic encryption can be used for PSI. I am aware of other SMC protocols but I never understood how to use schemes like Paillier for PSI calculation. ...
crypto disciple's user avatar
3 votes
1 answer
248 views

Design a OT-based Private Set Intersection protocol to obtain $A \cap B \cap C$?

This is a tutorial question for a Foundations of Privacy computer science course, I'm unsure on how to tackle it because we haven't talked much about these particular topics in class. (a) Assume ...
Kiyi1994's user avatar
1 vote
0 answers
122 views

Private Set Intersection using a subset of the larger set

Alice has a set $S_A$ with a low cardinality (say ~30k). Bob on the other hand has a set $S_B$ with a much higher cardinality than of Alice's (say ~100M). We're trying to create a reduced ...
zetaprime's user avatar
  • 591
4 votes
1 answer
509 views

What are the advantages of mutual private set intersection methods over finding the intersection of hashed lists?

I can understand the usefulness of one-way private set intersection methods. Where Alice and Bob both have listed but only Alice learns the intersection of those lists while Bob learns nothing. I ...
Curious Curt's user avatar
1 vote
2 answers
335 views

Oblivious Decryption: Decrypting with a private key, without knowing the message

I’m trying to devise a protocol, complimentary to a private-set-intersection, involving three parties, namely Alice, Bob and Charlie. Alice has a public and a private key. And receives website logs ...
zetaprime's user avatar
  • 591
7 votes
1 answer
276 views

True/False if a user is a customer without revealing the actual customer

I have a user A and a third party company B. I want to check if A is a customer of B. B cannot reveal any information about their customer list to me. If A is a customer of B, I do not want B to ...
Toby's user avatar
  • 71
3 votes
3 answers
119 views

communication efficient private lookup

I have a scenario where a client has a private set and the server has a large public set, we would like an estimate of the intersection size or more specifically the percent of the private set covered ...
Meir Maor's user avatar
  • 11.8k
0 votes
1 answer
216 views

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
zetaprime's user avatar
  • 591
1 vote
2 answers
411 views

PSI protocol reveals only one element of the intersection of two sets

So let Alice has a set of integers, says, $A = \{a_1,\dots, a_n\}$, similarly, Bob has a set of integers $B=\{b_1,\dots, b_n\}$. is there any protocol that allows Alice and Bob to randomly learn ...
DiamondDuck's user avatar
4 votes
3 answers
670 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
zetaprime's user avatar
  • 591
2 votes
1 answer
187 views

How can Alice enable Bob to look-up values in a private map

I think this problem is similar to private set intersection, yet distinct in a way where: Alice has an extensive Mapping of say id to name id1 -> John Doe id2 -> Jane Doe id3 -> Edgar Poe ...
zetaprime's user avatar
  • 591
5 votes
2 answers
337 views

Socialist Millionaires variant, where only one party learns $x=y$?

In the Socialist Millionaires protocol, Alice selcts some $x$ and Bob selects some $y$, and both parties learn whether or not $x=y$ without learning the other party's selected value. However, on a ...
apsillers's user avatar
  • 350
1 vote
1 answer
56 views

Is there something similar to a Bloom filter that allows you to test arbitrary predicates on the set?

As I understand it, if you have a Bloom filter that was generated from the members of a specific set, you can test whether a given bit string is in the set (with some given false positive rate). The ...
Ian MathWiz's user avatar
4 votes
2 answers
231 views

Find out a set of values without sharing my own

I have the following problem which i am trying to find a reasonable protocol to solve it. This is a simplified version of the problem. Alice has a set of values $\{a_1,a_2,...,a_n\}$. Bob has a set ...
Black_b_r's user avatar
2 votes
2 answers
151 views

Proof of using a literal from known set, inside a computed formula

Suppose I have publicly revealed the value of $\phi(u) = A+Bu$, where A, B, u are private values from a large group, that I want to keep in secret. Furthermore, I want to add proof that the value $u$...
user1387682's user avatar
0 votes
1 answer
451 views

SHA2 Certificate generating (create Signed Certificate) [closed]

i was requested to write a programmer that can generate A SHA2 certificate. So i wrote a tester class to try and mimic Keytool process of generating One (referencing base of this: url https://www....
SmurtD's user avatar
  • 3
8 votes
1 answer
2k views

2-party private set intersection

Are there dedicated protocols to achieve a private set intersection where one of the set is of small constant size $c$ and the other one of size $n$? What are the resource complexities of this kind ...
Dingo13's user avatar
  • 2,867
5 votes
1 answer
451 views

Malicious Model and Arbitrary selecting inputs on MPC and PSI

Imagine the following setting: a party considers a secret sharing or multiparty protocol that is secure against semi-honest adversaries. The adversary selectively chooses the inputs such that it could ...
DaWNFoRCe's user avatar
  • 872
1 vote
1 answer
296 views

Oblivious Polynomial Evaluation and Encoding Payload

I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a ...
progician's user avatar
  • 135
0 votes
1 answer
294 views

Secure multi-party private set intersection: Protocols supporting MULTI-party VS supporting TWO-party

Let assume party $B$ wants to receive secure multi-party computation (MPC) output. The are many private set intersection (PSI) protocols that support only two parties but they cannot support multi-...
user153465's user avatar
  • 1,583
2 votes
2 answers
122 views

Simulator in Private Outsourced Computation over Outsourced Datasets

Please, consider two honest parties $A$ and $B$ outsourced their private data to a malicious server $S$. So the parties store their data in the server. Then at a later point in time they want to ask ...
user13676's user avatar
  • 835
1 vote
1 answer
345 views

On the privacy of perfect hash functions

I'm digging into the several algorithms for building (Minimal) Perfect Hash Functions. It seems that the recent works provide quite a few very efficient algorithms. However, I'm wondering how a (M)...
pAkY88's user avatar
  • 163