Cryptographically safe lookup of value in a set

I'm looking for an elegant solution to the might-seem-trivial problem of looking up for specific value in a known set of values without disclosing what value we look for. Let me describe it in a classical way:

Alice will soon celebrate her birthday and she wants to know if anyone in her class has the birthday on the same day as her. Unfortunately, the only person who knows the dates of birth of all the people in the class (except Alice's one) is Malory. How Alice could ask Malory if anyone has the birthday on the same day without disclosing her own date?

Assumption:

1. Malory is open to helping Alice and she will answer any questions legitimately. Yet, she can only answer yes or no.
2. Alice will ask Malory a single time. Malory cannot influence Alice to make her ask the same question once again. Though, in future Alice might on her own will ask about the different dates (e.g. Bob's birthday).
3. Alice doesn't need and doesn't want to know the dates of birth of everyone in a class. She would like to get an answer from Malory asking a single question.

A pretty straightforward way to approach this problem is to apply hash. Alice hashes her birthday and passes this information to Malory, the same time asking her to hash the birthdays of all the people she knows and tell her if any match. The problem is that Malory, who would like to know Alice's birthday, can enumerate all possible dates (as the entropy of input is low) and check one by one if any matches with what Alice asked about. I would like to eliminate that threat.

I have thought about applying the one-to-many mapping to the birthday. As one date could be represented by multiple values, the enumeration attack would become unfeasible. The first problem is I don't see an easy way to let Malory do an atomic mathematical comparison with her set of dates. The second problem is if such comparison can be done, it is still possible for Malory to make a new set and do the lookup operation once again (what effectively translates to enumeration attack). Thus, the one-to-many mapping Alice applies should be parametrized by the unique feature of a set Malory will be searching in.

I do hope I haven't brought too much confusion and I'll appreciate any help, references, mentions of algorithms, or similar problems! I'll also appreciate your opinion if you think this problem is not solvable with given assumptions! If some of them are unclear, let me know and I'll do my best to clarify my intent.

You are describing the problem of 1 out of $n$ Oblivious transfer with $n=366$ if it is required that Alice receives no extraneous information. The methods of Kolesnikov et al in their paper “Efficient batched oblivious PRF with application to private set intersection” gives a sense of what is possible.

If it is acceptable for Alice to obtain additional information, then the problem is one of private information retrieval. Ostrovsky and Skeith’s survey paper “A survey of single-database private information retrieval: techniques and applications “ provides a good overview.

Second, simpler approach, thanks to a comment by @Mikero:

Alice picks a uniformly random private key $b$. Alice's birthday is on the $k$th day of the year. Alice sends $A = bH_p(k)$ to Malory, where the function $H_p()$ means to hash the input and interpret the result as an EC point.

Malory picks a uniformly random private key $e$. Malory has a function $F_e(i)$ which outputs $eH_p(i)$ if at least one person is born on that day of the year, and otherwise outputs a randomly chosen EC point.

For each value of $i$ such that $0\leq i \leq 365$, Malory sends $F_e(i)$ to Alice. In addition, Malory sends $Q = eA$ to Alice.

Alice calculates $Z = b^{-1}Q == b^{-1}eA == b^{-1}ebH_p(k) == eH_p(k)$.

Alice then checks if $Z$ matches any of the 366 outputs of $F_e(i)$ that Malory sent to Alice. If there is a match, then Alice shares a birthday with someone else.

Explanation: We've created a "1-OPRF", which means an oblivious pseudo-random function which Alice is able to query once with the blind assistance of Malory, but which Malory can query many times.

The PRF is simply Malory blinding an EC point $H_p(i)$ (where $H_p(i)$ represents a particular day $i$ of the year as an EC point), with his private key $e$, by calculating $eH_p(i)$. Because of the elliptic curve discrete log problem, no observer (including Alice) can predict the output of $eH_p(i)$ for any $i$ without knowledge of the secret $e$. This means that when no one is born on a particular day, Alice cannot tell that Malory has sent a random EC point instead of the real output of the PRF, because the output of the PRF is unpredictable to Alice.

Alice blinds her input to the PRF by picking a blinding factor $b$ and sending $bH_p(k)$ to Malory instead of sending (and thus revealing) $k$. Alice un-blinds the response by reversing the multiplication with $b$, and is thus able to query the PRF without Malory having knowledge of the input Alice is using.

The consequence is that Malory has sent a list of EC points to Alice that only include the true output of the PRF for those days of the year that at least one other person is born on. In addition, Alice has been able to blindly query the PRF for the output of her particular birthday, and is able to see if that result appears in the list of possible PRF outputs sent to her by Malory.

Malory has not learned $k$, and Alice is unable to learn anything other than whether she shares her birthday with at least one other person.

One approach is to do 1-out-of-n oblivious transfer. Malory will send Alice a list of 366 encrypted booleans (to allow for birthdays on Feb 29), where each boolean will signify whether anyone has a birthday on that day of the year. Alice will only be able to decrypt one of the 366 booleans, and will thus only be able to know if anyone else has a birthday on that day of the year.

The wikipedia article I linked to in the paragraph above references several implementation approaches to achieve 1-out-of-n oblivious transfer. Here is one approach that I thought up just now (with credit to @IlmariKaronen for a very elegant improvement):

Alice is born on day $k$ of the year, where $0\leq k\leq 365$. Alice sends the public key $P = xG-kH$ to Malory, where $x$ is a uniformly random scalar private key. $H$ is calculated as $H = H_p(G)$, where the function $H_p()$ means to hash the value and interpret the result as an EC point. Choosing $H$ in this manner means the discrete log of $H$ w.r.t. $G$ is unknowable, i.e. $h$ cannot be known such that $H==hG$.

Malory calculates 366 public keys $\{Q\}$ of the form $Q_i=P+iH$ for all values of $i$ where $0\leq i\leq 365$.

The private key corresponding to each public key $Q_i$ will be $q_i == x - kh + ih == x+(i-k)h$.

Since we've already demonstrated that $h$ is unknowable, this means that $q_i$ will only be knowable by Alice when $i==k$, in which case $q_k$ will be equal to $x$.

Thus, Malory will have computed 366 public keys for which Malory can be sure that Alice can only know the private key corresponding to one of them.

For each day of the year $i$, Malory uses the El Gamal scheme as follows: Malory picks a uniformly random scalar $e_i$, and provides Alice with the pair $(E_i, F_i)$ where $E_i = e_iG$, $F_i = e_iQ_i + H_p(v_i)$ and where $v_i$ will be specified as $0$ if no one has a birthday on that day of the year, or as $1$ if at least one person has a birthday on that day of the year.

To decrypt $v_k$, Alice computes $V_k = F_k - xE_k$. Alice then checks whether $V_k\overset{?}{=}H_p(0)$ or $V_k\overset{?}{=}H_p(1)$, and thus knows if $v_k$ is $0$ or $1$. This works because $q_k==x$ and $Q_k==xG$, and so $xE_k==x\cdot e_kG==e_k\cdot xG==e_kQ_k$.

Alice will have been able to determine only if someone else was born on day $k$ of the year, and Malory will not be able to determine $k$.

There is a novel Private Information Retrieval with Fully Homomorphic Systems,

• 2014 Bandwidth Efficient PIR from NTRU Yarkin Doröz, B. Sunar, Ghaith Hammouri

This is a Private Encryption Scheme that can the value at index $i$ from the array on the semi-honest server. The server learns nothing and only returns the value at index $i$. We can modify this as;

1. Mallory encrypts all existing birthdays $b_i$, $0 \leq i \leq 366 $ with the FHE public key of Alice. (Encryption of $366\cdot 8$ bits, not necessarily all days, the existent birthdays are enough and this saves space in large sets.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, b_i)$$

   If we use bit-based (HLibe, TFHE) then each $c_i$ is an array size 8.

2. Alice sends her birthday $A$ encrypted with her public key to Mallory (Encryption of 8-bit).

   $$a = \operatorname{FHE-Enc}(A_{pub}, A)$$

3. Mallory executes the FHE Equality circuit on each encrypted birthdays

   $$t_i = \operatorname{FHE-Compare}(A_{pub}, c_i,a)$$

4. Mallory OR the results with FHE using binary tree approach to reduce the depth of circuit (it is possible with the summation instead of OR) and return the result back to Alice.

   $$o = \operatorname{FHE-OrAll}(A_{pub}, [t_0,\ldots,t_n])$$

5. Alice decrypts the resulting bit with their private key;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • if $b=1$ then there is at least one student with date $A$
   • if $b=0$ then there is no student with date $A$.

What is guaranteed;

1. Mallory can not learn what is the queried data $A$ since it is encrypted with FHE - semantical security exists.
2. Mallory can not induce the queried data from the result for the same reason as above; from $(A,o)$.
3. The circuit doesn't reveal anything about the internals of the data other than what function is computed - the circuit calculates the existence of data without revealing the result.
4. Alice only learns the existence of the birthday nothing more! Alice gets only one bit $b$, exist or not. This doesn't return the count of equal birthdays.
5. Alice only queries once.
6. Mallory sends only encryption of one bit $b$! Therefore a quite band-efficient scheme.

1. Mallory prepares a bit array of size 366 initialized to zero. $$B = [b_0,b_1,\ldots,b_{366}] = 0$$

2. Mallory set the existing birthdays to 1. Like; $$B = [0,0,1,\ldots,0] $$

3. Mallory encrypts the bit array with the public key of Alice (FHE public key) and gets another array of size 366.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, B[i]) \;\; \text{for }\; 0\leq i \leq 366 $$

4. Alice prepares another bit array of size 366 where only her birthday is set to 1 rest set to 0. $$A = [0,0,0,\ldots,1,\ldots,0] $$

5. Similarly to Mallory, Alice the array with her public key and sends the resulting array to Mallory.

   $$a_i = \operatorname{FHE-Enc}(A_{pub}, A[i]) \;\; \text{for }\; 0\leq i \leq 366 $$

6. Mallory executes FHE-AND operation component wisely on the encrypted arrays. $$c_i = \operatorname{FHE-And}(A_{pub}, A[i], B[i])$$

7. Mallory OR bits of the resulting array and return the result back to Alice.

   $$b = \operatorname{FHE-OrAll}(A_{pub}, [c_0,\ldots,c_{366}])$$

8. Alice decrypts the resulting bit with their private key;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • if $b=1$ then there is at least one student with date $A$
   • if $b=0$ then there is no student with date $A$.

What is guaranteed;

1. The same as the basic scheme.
2. This time instead of encrypting 9-bit, Alice encrypt 366-bits (~40-time increase of the initial sending cost/time)
3. The Mallory, on the other hand, received a lot of improvement on the time and memory
   1. There is no need for a heavy FHE-equality operation.
   2. The size of the stored ciphertext was reduced by ~40.
4. The result, on the other hand, is still encryption of 1-bit.
5. This scheme saves a lot of time on the process.