Score:2

Clarification of the provable cryptography controversies

us flag

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.

Score:11
ng flag

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.

user2357 avatar
us flag
You said "Provable security is still the standard setting in cryptography" Is it really the standard? I thought it is a new proposal.
fgrieu avatar
ng flag
@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.
user2357 avatar
us flag
@fgrieu What about the symmetric ciphers, do they follow the provable-security paradigm?
Mark avatar
ng flag
@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).
fgrieu avatar
ng flag
@Mark: I learned something useful! Thanks!! I guess the heavy performance penalty is why this is not a standard requirement for now.
user2357 avatar
us flag
@Mark you said "arguably the field has collected around more 'standard" assumptions" what are these assumptions? Where can I learn them?
Mark avatar
ng flag
@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](https://eprint.iacr.org/2019/108.pdf) for an attempt at a unified picture.
Mark avatar
ng flag
To see what primitives people use "in practice", you can look at things like NIST competitions. In particular, if you look at the NIST PQC finalists, and throw in some common classical assumptions (RSA, Finite-Field/EC DLog and CDH/DDH, and a pairings-based assumption, I think SXDH?), you'll have a pretty good start of the "core assumptions" used in cryptography.
user2357 avatar
us flag
@Mark if you can assume hardness, does not this make you on the provable-security site?
Mark avatar
ng flag
@user2357 not really, I'm unaware of any serious proposals for public-key cryptography that do not assume hardness of some underlying computational problem. Of course these problems may be somewhat specific to the cryptosystem (say "The RSA assumption", rather than the general factoring problem), but generally they are isolated, and the cryptosystem is proven secure (provided the isolated problem is hard).
user2357 avatar
us flag
@Mark if you can assume hardness (for symmetric ciphers), does not this make you on the provable-security site?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.