Existence of functions that only tests memberships without revealing any information about the members

Question

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically or probabilistically), BUT no adversary can ever learn/extract any (member) strings from the program (in polynomial time)?

Can we have such functions with computational assumptions (such that they are secure even in the post quantum regime)?

---

Note: We can also entertain a program that takes, as input, a valid $s$ that is a member of P, to verify the membership of $s'$.

Answer 1

Yes. This is known as the problem of obfuscating a point function. There are standard schemes. See, e.g., the following papers:

On Obfuscating Point Functions. Hoeteck Wee. STOC 2005.

Technically, a point function is a function $f_s(x)$ given by $f_s(x)=1$ if $x=s$ and $f_s(x)=0$ for all $x \ne s$. There are standard schemes for obfuscating point functions. This corresponds to the special case of your problem where $n=1$ (hiding a single value $s$). However, the techniques all generalize to arbitrary $n$, as long as the number $n$ of values is exponentially small compared to the size of the domain of the function.

Answer 2

You can use a one-way permutation. Pad all strings to the same length. Let $f$ be a one-way permutation. Store $S = \{f(s_1),\ldots,f(s_n)\}$. You can test whether $x \in \{s_1,\ldots,s_n\}$ by checking whether $f(x) \in S$. However, depending on the security properties of $f$, you shouldn't be able to learn anything about $S$ without a lot of effort.

Answer 3

One way to do this is to compute and store a secure hash of the each of the strings (e.g., using SHA). Then the program $P$, given a string, checks to see if its hash is among the stored list of hashes. A one-way permutation could be used, instead of a hash, but this would require more time and space (especially if the strings are long, relative to the secure hash size). However, the drawback of using a hash, rather than a one-way permutation, is that it is theoretically possible that the program can give a false positive output, i.e. incorrectly say a string was in the list when it in fact was not; but such false positive cases in practice will never be observed (barring some major algorithmic/technological breakthrough), provided the hash size is chosen large enough.

Of course, there is a potential attack of simply trying the possible strings by brute force; this will be a problem if some of the strings are short or are formed in a predictable way.

In any case, it would not be easy to mathematically prove that an attacker with a classical computer can never extract any strings from $P$ in polynomial time (much less could we prove that the scheme is secure even against attacks from a quantum computer). Such a proof would give a proof that $P \neq NP$, since if an attacker could solve NP-complete problems in polynomial time then they could extract the strings in polynomial time as well.