1
$\begingroup$

Boiled down to the core as I understand it:

A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time.

If my understanding is correct then cryptographic algorithms like RSA / Diffie-Hellman are not considered to be provable secure since they would be broken to an adversary with unlimited computational power / time.

The only classical algorithm I know of that behaves in this manner is the OTP. I'm specifically asking about classical algorithms because I know that there exist quantum cryptographic algorithms that are provable secure, i.e. QKD.

My questions are:

  • Is my understanding of provable security correct?

  • And if so, are there any other classical algorithms that are provable secure?

Improve this question
$\endgroup$
2
  • $\begingroup$ Also relevant: crypto.stackexchange.com/a/68606 $\endgroup$
    – Squeamish Ossifrage
    Jun 20, 2019 at 14:37
  • $\begingroup$ In brief, your understanding is an unfortunately common misconception of what the term ‘provable security’ means (which not your fault—this is why the term and its kin ‘security proof’ are dangerous jargon). It has nothing to do with whether something is ‘secure’ in the sense that ordinary people would understand the word; it has everything to do with whether there is a theorem about some formalization of security or not, and that's all. The theorem might come in one of many flavors; the theorem might have completely useless consequences. $\endgroup$
    – Squeamish Ossifrage
    Jun 20, 2019 at 14:39

1 Answer 1

Reset to default
3
$\begingroup$

A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time.

Is my understanding of provable security correct?

It doesn't appear to be accurate. It appears to be mixing up "provably secure" and "information-theoretically secure".

You can have a system that is provably secure as some problem X, and it could easily be the case that X is easily solved. "Provably secure as X" does not mean "it's unbreakable". It's a relation, not an absolute statement.

And if so, are there any other classical algorithms that are provable secure?

So this question should probably read:

are there any other classical algorithms that are information-theoretically secure?

The standard goals of information security are confidentiality, integrity, and availability.

One Time Pads are for the goal of confidentiality.

One Time Macs are the analogous algorithm that provide information-theoretically secure integrity.

I don't believe there is any such algorithm for availability. It's not clear what information-theoretically secure would even mean in such a context.

For the One Time Pad, I think there is a proof that any encryption algorithm that is information-theoretically secure is equivalent to a One Time Pad, but I can't think of a paper/answer to point to off hand. I think the proof I am thinking of is that any information-theoretically secure encryption algorithm requires a key that is at least as large as the plaintext.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ "I think there is a proof that any encryption algorithm that is information-theoretically secure is equivalent to a One Time Pad, but I can't think of a paper/answer to point to off hand." This heavily depends on your definition of "equivalent", e.g. one can imagine running the OTP in CBC mode (with the group elements being the blocks) at which point this looks different and doesn't have the 1-1 correspondence anymore that you normally expect from OTP but should still be provably secure. $\endgroup$
    – SEJPM
    Jun 20, 2019 at 14:31
  • $\begingroup$ Also, do you admit any additive group, where the key is drawn uniform random, or just over bits? Transformations between encodings don't always work, so proving equivalence is tricky. $\endgroup$
    – tylo
    Jun 20, 2019 at 22:40
  • 1
    $\begingroup$ One might also want to mention perfectly hiding (x)or binding commitments? $\endgroup$
    – Fleeep
    Jun 21, 2019 at 12:02
  • $\begingroup$ IIUC if a new primitive has a security proof, it does not mean it is computationally unbreakable? A primitive that's broken due to a bad security proof would be broken, do I say it is no longer provable secure? $\endgroup$
    – WeCanBeFriends
    Jun 29, 2019 at 17:34
  • 1
    $\begingroup$ @WeCanBeFriends I think what you have written there sounds right, for the most part $\endgroup$
    – Ella Rose
    Jun 29, 2019 at 20:28

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