In DH76 'New Directions in Cryptography', it states that

3) for almost every $K \in \{K\}$, each easily computed algorithm equivalent to $D_K$ is computationally infeasible to derive from $E_K$

($E_K$ and $D_K$ means an encryption and decryption algorithm with key $K$, respectively.)

Then, why 'almost every', and not just 'every'?

  • $\begingroup$ When an algorithm has possible keys where that isn't true, that's called a weak class of keys. If the key generation algorithm can avoid them, it won't typically be a problem when using it. $\endgroup$ – Natanael May 8 at 13:18

As pointed out in the comments, this allows for a small and negligible number of weak keys which can be avoided.

Let us not forget that this pioneering paper was published before any examples of public key cryptosystems were known in the open literature. The authors took the astute position that if good cryptosystems were discovered, a few weak keys should not rule such algorithms out of contention for publication, analysis, and possible improvement.

Furthermore, from the theoretical point of view, one can sometimes prove strength of cryptosystems, for almost all keys, or for almost all choices of some design parameter, especially for randomized cryptosystems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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