What is the relation between computational security and provable security?

I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security.

Let $$(E,D)$$ be an encryption scheme that uses $$n$$-bits keys to encrypt $$l(n)$$-length messages. $$(E,D)$$ is computationally secure if $$E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1)$$

And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.

"Unconditional security" (or "information-theoretic security" or "perfectly secrecy") and "computational security" are two opposite classes of security. But I do not think "computational security" and "provable security" are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm). And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.

• – fkraiem May 10 '19 at 11:48
• Provable security reduces one implementation of some algorithm to a hardness claim, stating that this scheme is no easier to crack than a particular hard mathematical problem. Thus, the scheme is secure if the underlying problem also truly is hard. Computational security means there's a minimum amount of work required to crack the algorithm / problem which exceeds the resources of your adversary. Meanwhile information theoretic security means there's no method to crack it whatsoever. – Natanael May 10 '19 at 12:50
• @ Natanael In my opinion, given a computation model (e.g Turing machine), a problem is hard in some sense means that this problem takes long time in some sense (e.g. exponential time) to decide( or search). So I think it is similar to the notion of "computational security". Although the standard of achieving the security of these two kinds of notions may be different. – TeamBright May 12 '19 at 11:36

‘Provable security’ just means there is a theorem. It is a misleading term of art that should be carefully restricted to the literature if used at all, because it gives people false confidence: a system can have ‘provable security’ in the sense that there is a theorem, and could be completely breakable. There are different kinds of theorems, but let's focus on whether there is a theorem or not and walk through some examples of provable vs. conjectured security.

1. Why do we think it is difficult to find $$x$$ given $$y = x^3 \bmod{pq}$$ when $$p$$ and $$q$$ are independent uniform random 1024-bit primes and $$x$$ is a uniform random nonnegative integer below $$pq$$?

• Some of the smartest cryptanalysts on the planet have been banging their heads against this problem for nearly half a century, and have only a consistent track record of failure to show for it. Maybe tomorrow someone will find a way to do it: we haven't ruled it out. For example, if they found a way to factor $$pq$$, they could easily compute $$y^d \bmod{pq}$$ where $$d$$ solves $$3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}.$$ Indeed, with unlimited budget or a quantum computer they could do this easily.

• This is the RSA problem, with computational conjectured security. Of course, this system is not directly useful for applications, because most applications don't naturally deal in random 1024-bit primes or uniform random ‘messages’ modulo a product of 1024-bit primes. It is primarily a building block for practical cryptosystems.

2. Why do we think it is difficult to find $$m$$ given $$m + p$$ for $$m, p \in \operatorname{GF}(2^t)$$, when the distribution on $$p$$ has statistical distance $$\varepsilon$$ from uniform and $$m$$ has any distribution?

• There is a theorem that the distinguishing advantage of any decision algorithm, that is the probability beyond 1/2 of guessing uniform random $$b$$ given $$m_b + p$$ for any choice of $$m_0, m_1$$, is bounded by $$\varepsilon$$. No breakthroughs in cryptanalysis can change the result—any failure of security is guaranteed to be a consequence of pad reuse or poor pad generation.

• This is a formulation of the one-time pad theorem, with information-theoretic provable security. Of course, this system is not directly useful for applications, because you need a method to choose $$p$$ from a space as large as your space of possible messages, and do it independently for every message. It is primarily a building block for practical cryptosystems.

3. Why do we think it is difficult to find $$m$$ given $$(x^3 \bmod{pq}, m + H(x))$$ where $$x$$ is a uniform random secret, $$p$$ and $$q$$ are uniform random secret 1024-bit primes, and $$H$$ is a uniform random public function?

• There is a theorem, using the one-time pad theorem in (2) as a lemma, that if there is a decision algorithm with distinguishing advantage $$\varepsilon$$ against this system, then there is an algorithm that recovers $$x$$ from $$x^3 \bmod{pq}$$ with high probability; in other words, if the RSA problem of (1) is hard, then decrypting $$(x^3 \bmod{pq}, m + H(x))$$ to recover $$m$$ is hard. As in (1), breakthroughs in cryptanalysis could lead to factoring $$pq$$ to break this; similarly, since we're using the random oracle model breakthroughs in cryptanalysis of the specific hash function we choose for $$H$$ could break this.

• This is a weaker version of RSA-KEM/DEM, with computational provable security. The if/then structure of this theorem, using the one-time pad lemma to prove it, enables cryptanalysts to focus their effort on the RSA problem, rather than dividing effort between the $$(x^3 \bmod{pq}, m + H(x))$$ problem, the RSASSA-PSS problem, the RSA-KEM problem, etc. Of course, this system is not actually secure in a practical sense; you want a real DEM, which $$m + H(x)$$ is not—if you used this system, you would set yourself up for EFAILure. And if anyone solved the RSA problem, this would still have computational provable security; the theorem would just be vacuous!

4. Why do we think it is difficult, given a message $$m \in x\cdot\mathbb F_q[x] \setminus \{0\}$$ and its authenticator $$a = m(r) + s$$ for uniform random $$r, s \in \mathbb F_q$$ and $$q$$ a prime power, to find another message/authenticator pair $$(m', a')$$ also satisfying $$a' = m'(r) + s$$? (Here we are interpreting a message as a polynomial over the field $$\mathbb F_q$$ with zero constant term, e.g. by breaking it into $$({\leq}\log_2 q)$$-bit chunks and injecting them into $$\mathbb F_q$$ as coefficients.)

• There is a theorem that $$\Pr[a' = m'(r) + s \mid a = m(r) + s] \leq \ell/q,$$ where $$\ell$$ is the maximum length of a message. In other words, the one-time forgery probability is bounded by $$\ell/q$$. As with the one-time pad theorem in (1), no breakthroughs in cryptanalysis will change this theorem.

• This is a universal hashing one-time authenticator, with information-theoretic provable security. Of course, this works only for a single message, so this is mainly useful as a building block for practical cryptosystems like crypto_secretbox_xsalsa20poly1305 or AES-GCM. And, of course, the security depends on the choice of parameters: the theorem is still true when $$q = 2$$, but a forgery probability bound of 1/2 is not very secure!

• An encryption scheme is "provable security" means that there is a theorem which shows that the security of this encryption is related to a mathematical problem. And this scheme is security if and only if the mathematical problem is hard to solve. If anyone solved the mathematical problem, the encryption scheme was still provable security, although it was not security any more in the sense of computational security. Do I understand your answer? – TeamBright May 14 '19 at 13:48
• Provable security just means there is a theorem. That theorem might be of the form adversary's advantage is bounded by $\varepsilon$ (like the one-time pad or one-time authenticator theorem, which is not related to any conjectured computationally hard problem), or it might be of the form *if* there is an algorithm that breaks this cryptosystem with advantage $\varepsilon$, *then* there is an algorithm that breaks some underlying hard problem with advantage $f(\varepsilon)$ (like RSA-KEM, which is related to a conjectured computationally hard problem, the RSA problem). – Squeamish Ossifrage May 14 '19 at 14:22
• You are correct that a ‘provable security’ theorem relating security of a cryptosystem to difficulty of a hard problem is worthless if the problem turns out to be easy. But that's not the only case in which you have no security in spite of having ‘porvable security’. Even in the case that there's an unconditional theorem with no underlying hard problem that could be broken, like the one-time authenticator theorem in (4), the specific cryptosystem you choose—justified by that theorem—might be completely insecure because the parameters you chose for it are insecure. – Squeamish Ossifrage May 14 '19 at 14:34

And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.

Yes.

I do not think computational security and provable security are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm).

Yes.

And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.

Provable security refers to any security that can be formally proved, even if there are no mathematical hardness assumptions (e.g., information-theoretic security does not necessarily involve those assumptions). So, computational security is only part of provable security.

• Your answer was similar to my view before I wrote my question. I was not sure, so I decided to ask it. – TeamBright May 12 '19 at 11:52
• @TeamBright OK, that's actually my answer although I used some uncertain phrases, now rephrased. – Shan Chen May 12 '19 at 16:05