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.