2
$\begingroup$

A cryptosystem can be entirely dependent on its underlying problem or it can have a reduction to other known problems. Solvability can be affordable if there exists a reduction of the base problem to another problem, and the last is feasible.

I understand that a cryptosystem is provable secure if it has been well studied during years giving rigorous proofs on:

  • Cryptanalysis. By analyzing the base problem with existing techniques, measuring complexity (computational hardness), attempting to reduce to an affordable/easier problem.
  • Implementation. There is an efficient way to describe the cryptosystem in a resource bounded device, where security must be achieved.
  • Future expectation. Security facts based on theoretical cryptanalytic techniques, where the application of these methods is not feasible nowadays but theorized in the future.

Q: Is there any other condition for a cryptosystem to be stated as provable secure?

Q: Provable secure is not the same as probable secure. Does this last term has a broader definition in Cryptography?

Example, in maths a probable prime it's a pseudoprime (prime with probability threshold). And a provable prime is a prime that has been proved to be prime (i.e satisfies Fermat test and is not a Carmichael Number).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Q: Is there any other condition for a cryptosystem to be stated as provable secure?

The term "provably secure" is commonly made about a set of mathematical assumptions about a cryptosystem. The proof is performed by showing that the assumptions hold within the mathematical model or domain. The assumptions can be proven "by hand" or to use computer assisted applications such as SAT solvers, in which case the assumptions should be rigorously described.

Cryptanalysis

It does not depend on the time it takes to study the problem; studying time is not part of the model in which the assumptions are proven to be secure after all. Neither does the proof of security rely on cryptanalysis the way that you state. Cryptanalysis can just nullify the assumptions made on the system in which a system is proven to be secure; it should not nullify the proof itself.

For instance; if RSA encryption has been assumed to be secure and quantum computers render it insecure then replacing RSA encryption with a post quantum algorithm should fix the security proof. The security proof only relies on a the definition of a secure asymmetric cryptosystem consisting of ${Gen, Enc, Dec}$.

Is it of course possible that the proof itself is invalid or that the system is specified incorrectly. It happens regularly that mathematical solutions to stated problems are shown to be incorrect after all. Sometimes these errors can be fixed, fixed partially (e.g. by adding more constraints to the system) and sometimes the proof is completely destroyed. In that sense it is of vital importance that a proof is validated by other parties. An example of this is what happened to the RSA OAEP security proof which was invalidated and partially fixed.

Implementation

Implementations cannot fully be proven to be secure as the underlying system generally cannot be proven to be secure. It is however possible - but often very hard - to prove that software implements a provably secure protocol successfully. It is even possible to certify such software - software consists of mathematical formulas after all. But such security evaluation is generally only performed on very simple systems because most software systems are simply too complex to prove secure.

Future expectation

Future expectation doesn't have anything to do with provable security. In math something is secure or it isn't. If the system is insecure then something is either wrong with the model, some assumptions that were made concerning the model made are proven to be incorrect or the implementation is deemed to be insecure. The provable security is only destroyed if the model was proven insecure (but that's of little consolation if your security has been breached by sidestepping the security proof).

Q: Provable secure is not the same as probable secure. Does this last term have a broader definition in Cryptography?

I'm not sure if there is a good definition of "probably secure". You should have to look at the context to understand what it is supposed to mean. But it will undoubtedly have a broader definition than provably secure.

Example, in maths a probable prime it's a pseudoprime (prime with probability threshold). And a provable prime is a prime that has been proved to be prime (i.e satisfies Fermat test and is not a Carmichael Number).

Exactly: a provable prime has mathematically been proven to be prime. Nothing can be done to make it non-prime, not analysis, nor implementation nor future expectation.

A probable prime is just considered a prime because it adheres to strong heuristics to show that it is very likely prime. But it can still be proven to be otherwise.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Both answers are great! "Neither does the proof of security rely on cryptanalysis [...] Cryptanalysis can just nullify the assumptions made on the system in which a system is proven to be secure" I was referring to Cryptanalysis as tool to apply in the proof writing, to demonstrate that actual techniques don't apply. The future expectation was the theoretical attacks not possible nowadays i.e quantum attacks. But it makes sense to put it on the cryptanalitic part. $\endgroup$
    – kub0x
    Commented Oct 27, 2018 at 9:05
  • $\begingroup$ What I learnt here is that provable security is a security claim made by a construction based on assumptions where a cryptosystem is build on top of these. But that doesn't mean is secure generally, it can be nullified under certain assumptions (factorization, DLP & hidden subgroup problem under quantum attacks, etc) but replacing the cryptographic algorithms with a proven secure maintains the proof. $\endgroup$
    – kub0x
    Commented Oct 27, 2018 at 9:15
  • $\begingroup$ I've read that provable security has been criticized because some researchers have built proofs that rely on false assumptions. Personally, I'm on the point to give such a proof of security in my research and the more I read the more it will help me to understand how to construct it. $\endgroup$
    – kub0x
    Commented Oct 27, 2018 at 9:24
  • $\begingroup$ Having provable security has a lot of benefits and it helps a lot when advertising a product. You should however not treat it as a panacea, not to you nor to customers. Any system with a high complexity is hard to describe and security proofs can be faulty or irrelevant, mainly because the description of the system is not correct. So if you can do it, please do, but don't overestimate the result. As OAEP has shown, it is hard enough even for relatively simple algorithms. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 27, 2018 at 12:45
  • 1
    $\begingroup$ (I haven't made my own security proofs, but I have previously tried to bring down the expectations of somebody who was showing one to a large audience without enough peer review ... fortunately the proof could be fixed later) $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 27, 2018 at 12:48
6
$\begingroup$

Provably secure doesn't actually mean secure. Plenty of provably secure cryptosystems were broken and not because the proof had a flaw. When something is provably secure, it just meant some statement regarding it's security has been proven. There are any number of such statements.

A proof always starts off with some assumptions, such as the hardness of some underlying problem, or security property of some building block. A statement about something else can then be build on top of those assumptions. But when that statement is formalized, it is never as broad as: "$X$ is secure". Instead the statement would be a more specific statement such as: "If you can invert $F$ you can also invert $G$, but $G$ is believed to be hard to invert. In this protocol under such and such assumption an attacker learns nothing more then he knew initially."

WPA is provably secure. They went all out on this proof. It was not just proven that the specification was secure in that no key material could leak. The implementation was proven to match the specification and the compiler was proven to work correctly.

And yet WPA was horribly broken. The proof didn't say anything about an attacker being able to coerce an all zero key. The attacker learned nothing, the security proof was not violated.

Provably secure does not imply Secure. It implies only whichever claims were actually proven.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I accepted Marteen's answer. I know that he he came later plus both answers solved my doubt, but he has more concrete definitions. Anyways, I upvoted and I really appreciate your help. $\endgroup$
    – kub0x
    Commented Oct 27, 2018 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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