Is it possible to have perfectly secure public-key cryptography with oracles?

It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme. That’s because the adversary can search through all possible private keys.

But I’m wondering if it can be made possible using oracles. My question is, do there exist sets of natural numbers $$A$$ and $$B$$ such that if Alice has access to an oracle for $$A$$ and Bob has access to an oracle for $$B$$, then these oracles can be used as private keys for a perfectly secure public-key encryption scheme?

I’m thinking that perfect security may be possible in this setting since there are uncountably many sets for the adversary to search through.

• How an adversary is going to search for all possible keys? I think you are confusing some terms; OTP is an informationally secure cipher even for an unbounded adversary. We consider bounded adversaries. For example, in a key search for AES256, a computationally bounded adversary cannot brute-force. – kelalaka Sep 4 '20 at 15:47
• A good oracle for RSA,ECC is having CSPRNG ( Cryptographically Secure Pseudo-Random Number Generator) – kelalaka Sep 4 '20 at 15:49
• uncountably many sets != perfect secrecy. And, also, how do you handle uncountably many sets is not clear.. – kelalaka Sep 4 '20 at 15:50
• @kelalaka: the question's first paragraph is correct. Indeed, for the arbitrarilly powerful adversary assumed in perfect secrecy, the public key is enough to find the private key, by trying all these, and trying if it works for all messages and all random inputs of the encryption or signature algorithms. – fgrieu Sep 4 '20 at 15:59
• Random oracles are not sufficient to do public-key cryptography (or equivalently, key-exchange). This is a classical result of Impagliazzo and Rudich. There is a one-to-one correspondence between functions and the real numbers (see §6 in Rudich's thesis, linked). Therefore, a random oracle can be implemented given random access to a randomly sampled real from $[0,1]$. It follows that even in the presence of a infinitely long bit string, public-key encryption is not possibile. – Occams_Trimmer Sep 5 '20 at 13:09

Yes, it is possible to have perfectly secure public-key cryptography with oracles (though the oracles I'll exhibit do not seem quite reducible to those of the question).

As pointed in the question, there can't be a completely public encryption procedure that works (in the sense that decryption is possible with the appropriate secret) and is perfectly secure (in the sense that an arbitrary powerful adversary can't decipher).

Proof (without invoking a private key): the encryption is an algorithm, which can be reduced to a deterministic algorithm with as input the plaintext to encipher and an extra bitstring, random in normal use. The arbitrary powerful adversary can try inputs ordered by increasing maximum length until finding one that enciphers to the ciphertext. Since decryption is possible, there can be only one.

An even simpler reasoning shows that there can't be a completely public signature verification procedure that works (in the sense that signing is possible with the appropriate secret) and is perfectly secure.

If we replace the encryption procedure with an encryption oracle doing the encryption, that problem can be solved.

I'll use the notation $$\tilde x$$ for the integer coded by bitstring $$x$$ per big-endian binary.

Let an encryption oracle for messages of $$b$$ bits, usable $$2^t$$ times

• contain
• $$2^{t+b}$$ bitstrings $$s_{i,j}$$ of $$m$$ bits each, with $$i\in[0,2^t)$$, $$j\in[0,2^b)$$, chosen at random except that $$\forall i,j,j'$$, it holds $$b_{i,j}=b_{i,j'}\implies j=j'$$.
• a $$t$$-bit bitstring $$n$$, initialy all-zero
• and on input of a $$b$$-bit message $$m$$
• if $$n$$ is not all-ones
• compute $$c\gets n\mathbin\|s_{\tilde n,\tilde m}$$
• change its stored $$n$$ to $$n'$$ such that $$\tilde n'=\tilde n+1$$
• output ciphertext $$c$$

Let the corresponding decryption oracle

• contain
• the same $$2^{t+b}$$ bitstrings $$s_{i,j}$$
• and on input of a $$t+b$$-bit ciphertext $$c$$
• split $$c$$ into $$t$$-bit $$n$$ of and $$b$$-bit $$x$$
• find bitstring $$m$$ such that $$s_{\tilde n,\tilde m}=x$$
• output ciphertext $$c$$

The following easily verified properties can be considered perfect secrecy:

1. The decryption oracle deciphers correctly the ciphertexts produced by the encryption oracle;
2. Any adversary with access to the same encryption oracle as the legitimate user has no advantage in the IND-CPA game, just as for the OTP.

An adversary with access to a single copy of the encryption oracle used by the legitimate user (rather than the original encryption oracle) has a tiny, quantifiable advantage (the best strategy makes a guess of the plaintext, submits it for encryption, and if the ciphertext matches: outputs that guess; otherwise outputs another guess of the message). It is possible to reduce that advantage arbitrarily by appending a random bitstring to $$n$$ at encryption.

If we are willing to give up some more of perfect secrecy, we can assume that the adversary is limited in the number of queries to the encryption oracle. In that case, the encryption oracle can be simplified to a single large fixed random permutation, and the decryption oracle to the inverse permutation. Textbook RSA is sometime modeled in this way (and that's a fair model if the queries made are random, masking the multiplicative property and some special input/output pairs).

What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time for the key. The issue is, this basically equates to having a key of infinite size which is just as impossible to use for encryption, since the time to encrypt increases as well - just not as fast as the time to break it.

However, if we assume your oracles $$A$$ and $$B$$ operate in a finite amount of time (somehow you manage to encrypt using an infinitely large key) you would have a perfectly secure scheme, as you describe.

@fgrieu's answer uses a stateful oracle, which I think is cheating a bit. The problem is impossible with stateless oracles (and perfect correctness).

Suppose the encryption algorithm is written as $$E^{\mathcal O}(pk,m;r)$$ where $$\mathcal O$$ is any stateless oracle; $$pk$$ is the public key; $$m$$ is the plaintext; $$r$$ is the randomness; $$E$$ is a deterministic function.

In the CPA security game, the adversary chooses distinct plaintexts $$m_0, m_1$$ and receives an encryption $$c$$ of one of them. The eavesdropper can simply guess $$r'$$ and re-run $$E^{\mathcal O}(pk,m_0;r')$$. If the result equals $$c$$ then output a guess of $$b=0$$. Otherwise make a random guess of $$b$$. Here it is important that the same inputs to $$E$$ always give the same output (this means $$\mathcal{O}$$ must be stateless). It is also important that we never have $$E^{\mathcal O}(pk,m_0;r') = E^{\mathcal O}(pk,m_1;r)$$ for distinct $$m_0,m_1$$ (this means the scheme must have perfect correctness).

This strategy will guess $$b$$ correctly with probability $$\frac12 + \Theta(1/|R|)$$, where $$R$$ is the set of possible random strings. So the scheme can't be perfectly secure.