Timeline for Clarification of the provable cryptography controversies
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2021 at 6:17 | comment | added | Crypt01 | @Mark if you can assume hardness (for symmetric ciphers), does not this make you on the provable-security site? | |
| Oct 13, 2021 at 4:30 | comment | added | Mark Schultz-Wu♦ | @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). | |
| Oct 12, 2021 at 18:23 | vote | accept | Crypt01 | ||
| Oct 12, 2021 at 4:04 | comment | added | Crypt01 | @Mark if you can assume hardness, does not this make you on the provable-security site? | |
| Oct 11, 2021 at 19:49 | comment | added | Mark Schultz-Wu♦ | 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. | |
| Oct 11, 2021 at 19:47 | comment | added | Mark Schultz-Wu♦ | @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. | |
| Oct 9, 2021 at 6:21 | comment | added | Crypt01 | @Mark you said "arguably the field has collected around more 'standard" assumptions" what are these assumptions? Where can I learn them? | |
| Oct 8, 2021 at 17:31 | comment | added | fgrieu♦ | @Mark: I learned something useful! Thanks!! I guess the heavy performance penalty is why this is not a standard requirement for now. | |
| Oct 8, 2021 at 17:23 | comment | added | Mark Schultz-Wu♦ | @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). | |
| Oct 8, 2021 at 17:08 | comment | added | Crypt01 | @fgrieu What about the symmetric ciphers, do they follow the provable-security paradigm? | |
| Oct 8, 2021 at 16:50 | comment | added | fgrieu♦ | @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. | |
| Oct 8, 2021 at 16:40 | comment | added | Crypt01 | You said "Provable security is still the standard setting in cryptography" Is it really the standard? I thought it is a new proposal. | |
| Oct 8, 2021 at 16:03 | history | answered | Mark Schultz-Wu♦ | CC BY-SA 4.0 |