2
$\begingroup$

I read about the provable cryptography in Wikipedia. The article referred to tense controversies around 2007.

Do these controversies still exist?

What is the substitution for the provable-security? Is not it sufficient? I think AES does not follow provable cryptography style, am I right?

Which is the accepted/preferred view in the Cryptography community?

Why did it started in the first place, Is not proof something desirable?

What are the achievements of provable cryptography?

Where to start cryptography study/research given these controversies?

I read through some objections, I felt that it is a matter of two things: the starting assumption is not strong, and some errors that existed in some paper, am I right? I think the first is essential to even get started (given the awareness of such assumptions), and the second is individual cases (given that it is wrong) not enough to refute the whole branch of science.

$\endgroup$
0

1 Answer 1

11
$\begingroup$

In general, that article seems to be referring to the "Another Look At..." line of work. Many of the papers are collated on this website.

There are a number of "controversies" you could to attempt to summarize. The main thrust against the notion of "provable security" is that it oversells what it delivers --- provably secure schemes can be attacked for a variety of reasons. A brief summary of the reasons are:

  1. The scheme is secure under reduction to some hard problem. This hard problem is esoteric and not studied much, and is in fact easy
  2. There is a bug in the (claimed) proof
  3. The proof is done in an unrealistic model, and one can still attack the scheme in practice
  4. The reduction is "non-tight", and does not meaningfully apply for practical parameters that people use.

There are some more esoteric complaints as well (the role of non-uniformity in cryptographic proofs, for example), but the above are at least the "main complaints" with provable security that I tend to hear, and I view as fundamentally valid complaints.

What is the substitution for the provable-security? Is not it sufficient? I think AES does not follow provable cryptography style, am I right?

In general, the substitution is to be more precise in the claims of security made. With the exception of the 2nd point above, all of the above points show something about an underlying scheme. Provided one precisely describes what is being shown, there is not an issue of "overselling" a result.

Which is the accepted/preferred view in the Cryptography community?

Provable security is still the standard setting in cryptography, although since ~1 decade ago arguably the field has collected around more "standard" assumptions (which is good due to the first point in the above list).

Why did it started in the first place, Is not proof something desirable?

A proof is only as useful as the statement being proved, which is essentially the source of the arguments against provable security.

What are the achievements of provable cryptography?

This is really too large to discuss, and highly depends on what one means by "provable cryptography". At a minimum, provable cryptography tends to tell you that what you are trying to do is not fundamentally flawed. For example

  1. The worst-case to average case reductions in lattice cryptography tell you that the LWE problem is in a certain sense the "right" average-case distribution to sample hard instances from. Note that these reductions are in a certain sense an example of "bad provable cryptography", as practitioners often do not use parameters that make the reductions valid, and the reductions are not particularly tight. Fully discussing this would take more space though.

  2. Similarly in the realm of lattices, lattice-based signatures were quite difficult to construct initially (they often leaked the secret key), until a paper that made a rather intricate rejection sampling argument. It seems like it would have been difficult to find this rejection sampling argument without pursuing a proof --- incidentally, these signatures have not meaningfully been attacked.

Of course, often authors talk about certain things being "proof artifacts", which typically mean modifications that are made to make a proof go through, but besides that do not obviously seem necessary for security. This can often make schemes less efficient, so the "intricate changes to make proofs go through" can be negative as well.

Where to start cryptography study/research given these controversies?

For the most part, you can ignore the controversies. While there are some useful takeaways (in particular with treating the concrete security of schemes that are going to be concretely deployed), they are of a technical nature that I would not thrust in the face of a beginner to cryptography research.

$\endgroup$
11
  • 4
    $\begingroup$ @user2357: provable security became the standard sometime during the 1990s. The main reason is that we then started to be able to make proofs. Another is that people got tired of the make/break/fix cycle there was before that, in particular on RSA signature padding (for example the first international on RSA signature, ISO/IEC 9796(-1) had to be withdrawn). And it was a useful way for reviewers to weed out propositions of articles with protocols or asymetric cryptosystems: a proof in some model became necessary to get published in a serious crypto journal. $\endgroup$
    – fgrieu
    Commented Oct 8, 2021 at 16:50
  • 3
    $\begingroup$ @fgrieu there are probably secure hashes, for example SWIFFT (it is CR secure under some form of SIS I think, not a suitable RO though iirc). There is also Blum Blum Shub as a probably secure PRG. Both are less performant than standard design paradigms though (I remember the gap for BBS being massive, while for SWIFFT it is "only" something like a 40x throughput gap). $\endgroup$
    – Mark Schultz-Wu
    Commented Oct 8, 2021 at 17:23
  • 2
    $\begingroup$ @Mark: I learned something useful! Thanks!! I guess the heavy performance penalty is why this is not a standard requirement for now. $\endgroup$
    – fgrieu
    Commented Oct 8, 2021 at 17:31
  • 1
    $\begingroup$ @Mark you said "arguably the field has collected around more 'standard" assumptions" what are these assumptions? Where can I learn them? $\endgroup$
    – Crypt01
    Commented Oct 9, 2021 at 6:21
  • 1
    $\begingroup$ @user2357 it is somewhat hard to give a single source. In "Minicrypt" it is known that essentially all (non-hashing) primitives are equivalent, for example PRGs are equivalent to PRFs are equivalent to PRPs (you can even throw in OWFs as well). Most "cryptographic assumptions" are not used for minicrypt primitives though, but instead for cryptomania primitives. The story of having a "unified" view of cryptomania is somewhat more complex --- different hardness assumptions let you build different things. See this paper for an attempt at a unified picture. $\endgroup$
    – Mark Schultz-Wu
    Commented Oct 11, 2021 at 19:47

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.