7

Here are some recent papers that explicitly study optimizing PSI for the case of unequal set sizes. Private Set Intersection for Unequal Set Sizes with Mobile Applications; Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas Fast Private Set Intersection from Homomorphic Encryption; Hao Chen, Kim Laine, Peter Rindal Unbalanced Approximate ...


6

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash function on the set of n bit strings. Obviously this function does not hide the input at all. So the answer to your questions is that it depends on the hash ...


5

In general, such attacks are "allowed" in the malicious model. This is due to the fact that secure computation guarantees that the process of computation reveals nothing. A secure protocol should behave like an ideal model where a trusted party computes the result. Now, in some cases, this is a problem. However, in practice, in many cases it is OK. Consider ...


4

Your simple approach is not bad, but you might consider these modifications: First, you don't need a PRF, any form of hashed key or a simple hash over the concatenation of a key and the element should be enough. Basically any one-way function over elements and some sort of key should do the trick, and you can optimize for speed. The key is not chosen by ...


4

You are looking for a private set intersection protocol. For the semi-honest (passive adversary that follows the protocol) setting, go to Benny Pinkas's homepage and read the papers there, e.g. Scalable Private Set Intersection Based on OT Extension Efficient Circuit-based PSI via Cuckoo Hashing For the malicious (active adversary that behaves ...


4

Now I noticed that no matter which generator I use, when I use power-mod such that g^(q-1) mod q the result always 1 Congratulations, you just rediscovered Fermat's Little Theorem which says that for all primes $p$ and all non-zero integers $a$ which are not multiples of $p$, it holds that $a^{p-1}\bmod p=1$. So if I have the group order set to 8009 minus ...


3

A 1-out-of-n Oblivious Transfer protocol would fit as a solution to your problem. Oblivious Transfer can be viewed as an improved Private information retrieval protocol, because it allows that only exactly 1 item is retrieved from the database, without sharing any additional info about the database. In addition the "sharer" of the database ($B$) doesn't ...


3

Here are some recent papers that study optimizing PSI for the case of significantly unequal set sizes. In all of these papers the primary goal is to reduce communication. These two papers save on communication by having an offline phase with high communication. When it comes time to actually compute the intersection, the online communication is low: ...


3

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper Practical Multi-party Private Set Intersection from Symmetric-Key Techniques, by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu If I remember correctly, we may ...


3

In fact, one possibility is to use the generic garbled circuit protocol that implements a PSI circuit + a filter circuit such that the result (intersection) from the PSI is filtered and only one randomly chosen element in the intersection is output at the end of the protocol. However, I cannot say much except this is feasible. Below is a custom protocol for ...


3

Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called "PSI with associated data" or "PSI with data transfer". For example, you can see this variant of PSI described explicitly in: Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear ...


3

A protocol consists of parties taking turns sending messages. Therefore one party will naturally learn the output before the other (only very few exceptions exist to this rule). This means that in almost every protocol you find (especially in the semi-honest setting) you will see that either (1) the last protocol message literally is nothing more than the ...


3

I use the notation introduced in the paper: The parameters of ElGamal are $(G, q, g)$ where $q$ is prime, $G$ is a cyclic group of order $q$ and $g$ is a generator. In the paper, the authors use "exponential ElGamal" such that they have an additive homomorphism, i.e., the message is represented as "exponent" of $g$, i.e., as $g^m$. With $h=g^x$ being the ...


3

This problem was studied under the name of private set-intersection cardinality (PSI-CA) by De Cristofaro et al. They give protocols for the two-party case both in the honest-but-curious and malicious setting, and the complexity grows only linearly in the size of the sets. A result for the multi-party case was given by Egert et al. using Bloom Filters. In ...


2

It is of base $2$ since it is the number of bits needed to represent in binary form $n$.


2

In general, you might find it more useful to look at the full description of the protocol on page 137 of the paper you cite, rather than the general overview on the preceding pages. To answer your specific questions: From page 137, step 8 (which corresponds to step 7 in the general overview): "For each $y_j \in Y$, $S$ chooses a random polynomial $P_{0,...


2

The coefficients in the polynomial are elements of the field; when you expand the polynomial: $$(x-1)(x-2)$$ where $1$ and $2$ are field elements, the normal algebraic rules apply (because those rules are based on the field properties), you get: $$x^2 + -(1+2)x + (1\times2)$$ where the middle coefficient is the additive inverse of the sum of 1 and 2 (...


2

The bar is just concatenation of strings. As long as you are comfortable treating things both as bit strings and as group elements, there is nothing special about the encryption scheme being used here. Without these payloads, the idea of the protocol is the following. Bob sends a set $Z$ of ciphertexts. Alice computers her output as $\{ \mathsf{Dec}(z) \mid ...


2

The objective of the simulator is to make the simulated world (often called the ideal world) indistinguishable from the real world (running the actual protocol). See my write-up on the UC framework here for more detail. In the proof setup, the entity attempting to distinguish between the two worlds is often assumed to provide the inputs to the parties. That ...


2

What you describe sounds a lot like the encoding mechanism in this paper: Benny Pinkas, Thomas Schneider, Michael Zohner: Faster Private Set Intersection based on OT Extension, Usenix 2014. See section 5.1 of that paper. Basically there is an OT of random strings for each bit of Bob's input. Bob takes the XOR of his OT outputs. Alice can compute the ...


2

Naive hashing protocol Suppose Alice has items $x_1, \ldots, x_n$ and Bob has items $y_1, \ldots, y_n$. In the naive hashing protocol, they agree on a common hash function $H$, and Alice sends $H(x_1), \ldots, H(x_n)$ to Bob. Bob can compute $H(y_1), \ldots, H(y_n)$ and then calculate the plaintext intersection between these two lists. Insecurity of naive ...


2

This can be done by exploiting the homomorphic property of RSA. Let's say Alice's key is $(e,N,d)$ where $e$ is the public exponent, $N$ the modulus, and $d$ the private exponent. To decrypt $x$, Bob samples $r$ randomly from $\{1,\cdots,N\}$ and computes $xr^e\mod N$ and sends it to Alice. Alice computes $(xr^e)^d=x^dr\mod N$ and sends it back to Bob. ...


2

This is very similar to a well-known protocol that dates back to the following work. Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986 Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in ...


2

I'm not sure where Bloom filters necessarily come in. The "standard" way to use additively homomorphic encryption (that's what Paillier is) for set intersection is the oblivious polynomial evaluation (OPE) technique. It works like this: Alice generates a polynomial whose roots are the items in her set: $p(x) = \prod_{a \in A} (x-a)$. She encrypts the ...


2

I believe this protocol should be satisfying the requirements of an Oblivious PRF. This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis: Parameters: A multiplicatively-written Group $\mathbb ...


2

Yes, there is a more secure way to achieve your goal. For uniqueness you can use SIV mode with a static nonce. SIV mode first calculates a MAC over the plaintext and then uses that as IV to the mode of operation. This means that identical plaintext will result in identical ciphertext, but that plaintext that only differ by a single bit will result unrelated ...


2

There is no need to decrypt here, so an encryption scheme is not the right fit. The parties simply need to compute a deterministic function whose outputs are random to your central machine --- i.e., a pseudorandom function. You should use a PRF like HMAC or GMAC etc. If you use a PRF, then what you have is essentially what is described in the following work ...


2

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known : That is correct; it is not known; however that is not sufficient; the relationship between $h(m_1) * s$ and $h(m_2) * s$ would be known (if you know $m_1, m_2$), and that breaks security (at least, within ...


2

I'm not well versed in cryptography, but it seems like private set intersection may be what I'm looking for? Yes. In private set intersection (PSI) if we have elements from a universe $U$ (e.g. the set of 128 bit integers) and Alice has $N_A$ elements and Bob has $N_B$ elements, most good PSI protocols will try to give you $O(N_A+N_B)$ communication and ...


Only top voted, non community-wiki answers of a minimum length are eligible