[Cryptography] State of sin (was Re: What to put in a new cryptography course)

Arnold Reinhold agr at me.com
Mon Jul 11 14:11:05 EDT 2016


> ...
> The *generic* discrete log problem (over the integers mod some N, or over an elliptic group) is considered hard because no one, after years of work, has found any attacks on it.
> 
> There's no *general* result that says these problems are hard.  What we have instead is some specific, very powerful attacks against particular instances of the problem. We eliminate those particular instances from consideration and say "the rest look good".
> 
> *As a matter of theory and mathematics*, we're living in sin:  We assume the problems we pick are hard because our best minds have brought our best methods to bear on them and have not only made no progress, they've managed to prove that *using these techniques* no progress is possible.
> ...

The lack of mathematical proofs for the security of cryptographic primitives is a reality with which the cryptographic community is perhaps too comfortable. We all know, of course that a mathematical proof of security would be traceable to the axioms of logic, and, at least for the existence of random quantitates, the laws of physics.  And that would be great. But there is something else a mathematical proof supplies: the precise statement of a theorem. It’s not just that we lack a proof that factoring is hard or that discrete logarithms in finite groups are difficult to compute, we don’t even know exactly what those words mean. 

A recent example of this is the Logjam attack for which there was no new mathematics developed, merely a realization that most the work needed in the best attack on D-H in the group of integers modulo a prime p was only dependent on p, not on the group element whose logarithm was to be computed. Since many protocols use the same p for all D-H encryption, attacks became more feasible than previously thought. The assertion "D-H is hard" omitted that bit of fine print.  What other overlooked technicalities are out there behind statements that "X is assumed to be hard"?

Arnold Reinhold


More information about the cryptography mailing list