Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
2answers
79 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 ...
5
votes
0answers
65 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 ...
3
votes
3answers
67 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 ...
0
votes
1answer
83 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) =...
1
vote
1answer
38 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 ...
3
votes
1answer
86 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 ...
2
votes
1answer
75 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 ...
5
votes
2answers
98 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 ...
1
vote
1answer
25 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 ...
4
votes
2answers
98 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 ...
0
votes
0answers
33 views

What Set and MultiSet Hash allows Secure, Homomorphic, commutative comparison of key-value databases? (Orderless, Online alternative to Merkle trees)

I am interested in Merkle tree like hashes that do not require the data to be ordered, but will hash the data, not the byte by byte, page by page storage but rather hash UNORDERED data (presumably ...
2
votes
1answer
69 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$...
0
votes
0answers
70 views

Diffie Hellman Private Set Intersection with Radix Merkle Tree instead of Bloom Filter

I was reviewing Diffie Hellman 2-party private set intersection here : https://eprint.iacr.org/2017/670.pdf [Figure 2]. We encrypt the data using DH and generate a BF on the client. We then map ...
0
votes
1answer
146 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....
4
votes
1answer
437 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 ...
6
votes
1answer
191 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 ...
1
vote
1answer
143 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 ...
2
votes
2answers
99 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 ...
1
vote
1answer
178 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)...
1
vote
1answer
162 views

Privacy-Preserving relational databases: checking the existence of a record (or multiple records)

I would like to know if there exists a protocol which performs the following operation in a privacy-preserving fashion: User $U$ wants to know whether a record is stored in the database. The primary ...
6
votes
1answer
323 views

Private set intersection, using a semi-trusted server

Alice has a set $S$ of words. Bob has a set $T$ of words. They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent. Trent runs a central ...
0
votes
0answers
55 views

Private Set Intersection Polynomial Computation [duplicate]

I am trying to implement the protocol mentioned in Section 3.4 of “Efficient Robust Private Set Intersection” in Java. In the Second Step, the Client computes a polynomial of degree $n$ over the ...
1
vote
1answer
58 views

Logarithm in Private Set Intersection

Is the logarithm in the private set intersection protocol mentioned in Section 3.4, Step 5 of http://www.ece.umd.edu/~danadach/MyPapers/set-int.pdf, a base 10 or 2? How do we find this out?
1
vote
1answer
156 views

Efficient Robust Private Set Intersection Questions

I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal. I am trying to run the full protocol mentioned in Section 3.4 on the following inputs: $p = 17$ (prime) $g =...
2
votes
0answers
64 views

Efficient Robust Private Set Intersection Additive ElGamal [duplicate]

I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal. I am trying to run the full protocol mentioned in Section 3.4 on the following inputs: $p = 17$ (prime) $g =...
3
votes
2answers
281 views

ElGamal in private set intersection: how to handle negative numbers?

I am trying to implement the Efficient Robust Private Set Intersection using Additive ElGamal. For this, from the client side, my inputs are $C = \{1, 2\}$. So, the polynomial is $(x-1)(x-2)$ which ...
2
votes
1answer
192 views

2PC Private Set Intersection Optimized for asymmetrically sized sets

I am researching some concepts of practical 2 party computation and was curious if anyone could point me to a research paper that is focused on private set intersection where one party has a very ...