2
$\begingroup$

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'$.

$\endgroup$

migrated from cstheory.stackexchange.com Mar 17 '15 at 2:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ An all-powerful adversary can just run $P$ successively on all strings until he finds those that he wants. $\endgroup$ – Emil Jeřábek Mar 16 '15 at 15:47
  • $\begingroup$ Of the many Bloom filter variants, which have you investigated and found wanting? $\endgroup$ – jbapple Mar 16 '15 at 15:51
  • $\begingroup$ Thank @EmilJeřábek, and yes, of course, I should have mentioned we also allow quantum resources, else we are willing to settle with computational assumptions that are secure in the post-quantum regime. $\endgroup$ – Subhayan Mar 16 '15 at 15:51
  • $\begingroup$ @jbapple thanks, I am looking at bloom filters now. Can you please refer to some paper that might help (while respecting the PQ-crypto assumptions) and make this an answer perhaps? $\endgroup$ – Subhayan Mar 16 '15 at 16:27
  • $\begingroup$ bloom filters will not work, for one thing the false positives. Also because they are in no way satisfy the criteria- "no adversary can ever learn/extract any (member) strings from the program?" $\endgroup$ – Subhayan Mar 16 '15 at 21:00
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "such false positive cases in practice will never be observed" -- where never means "with low probability", I assume? $\endgroup$ – Raphael Mar 17 '15 at 6:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.