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

[Ron Garret]

On Jul 28, 2016, at 9:40 AM, Arnold Reinhold <agr at me.com> wrote:

> 
>> On Jul 26, 2016, at 2:09 PM, Ron Garret <ron at flownet.com> wrote:
>> 
>> 
>> On Jul 26, 2016, at 10:01 AM, Arnold Reinhold <agr at me.com> wrote:
> ...
>> 
>>> I attempted to show that for a fixed size block cipher there exists a finite (tho entirely impractical) algorithm for finding all possible attacks and that therefore the the question is not undecidable. I’m glad you now agree that this is obvious. (I believe my argument can be extended to discrete log public key systems by replacing the code book with a table of logarithms as a finite upper bound for the size of Turing machines to search.)
>> 
>> Yes, obviously all finite problems are decidable in principle.  Why do you think that’s relevant?  Formal decidability is not the issue here.  
> 
> You were the one who suggested that the security of cryptographic algorithms might be undecidable in the formal sense, pointing us to Aaronson's blog with an example of a formally undecidable Turing machine with just a few thousand states.

Yes, but the point of that paper was not that the machine was undecidable.  The point was that this could be done with a machine that had a small number of states (<8000).

The real point of the paper was that you could get into deeply unknown mathematical territory with very simple machines.  In addition to the undecidable machine they also exhibited machines with even fewer states corresponding to the Goldbach conjecture and the Riemann hypothesis, two notorious unsolved problems.  The point being that once you get into this level of complexity you are solidly in the realm of the mathematically unknown, and therefore possibly in the realm of the mathematically unknowable.  We don’t know.  But now we know that once a machine has more than 7917 states it, in general, impossible for us to know.

So the question on the table now is: can a TM that does an exhaustive search over *algorithms* be constructed in fewer than 7918 states.  If not, then, in the absence of a major breakthrough, the only way for us to know the result of running such a machine is to actually run it.

Note that the fact that the exhaustive search is finite is irrelevant.  What we care about in this case is not whether or not it halts — we know that it will.  What we care about is the *answer*, i.e. whether or not an attack was found.  But it is easy to convert *this* question into an instance of the halting problem: let the TM that conducts the exhaustive search and outputs YES or NO be machine M1.  Construct a new machine M2 identical to M1 but replace the code that outputs “NO” with an infinite loop.  Now M2 halts IFF M1 outputs YES.  So the question of whether M2 halts is equivalent to the question of what answer M1 produces.  If M2 has more than 7918 then this question is generally undecidable.  We happen to be able to compute an upper bound on the running time of M2 (lets call it N), and so we can determine that M2 does not halt if it runs for longer than N steps, but it might be the case that there is NO OTHER WAY to answer the question.  Finding a way to answer the question more efficiently than running T2 for N steps would (almost certainly) be a major mathematical breakthrough.

There are other ways to potentially attack this problem, like finding a TM that did an exhaustive search over algorithms in <<7918 states.  But that seems to me unlikely to be fruitful.  We don’t actually know where the boundary between the mathematically knowable and unknowable actually is, we just know it’s less than 7918 states.

>> The issue is whether or not it is worth spending scarce resources looking for proofs.  Just because a question is formally decidable doesn’t mean it’s worth pursuing the answer.  The question of whether or not the Goldabch conjecture is true for all even integers less than Graham’s number is formally decidable, but it would be the very definition of foolishness to pursue the answer in the straightforward way.
> 
> The fate of nations has depended on the security of cryptography in the past and maybe depends on it even more so today. We currently spend scarce resources on far less practical questions than finding cryptographic systems that are provably secure.

Sure.  The fate of nations also hinges on the availability of cheap energy, but that’s not a good reason to start a research program into perpetual motion machines.

>>> 
>>>  ... What I strongly disagree with is the widely stated belief that a proof that P=NP would, by itself, invalidate current cryptographic methods.
>> 
>> You’re attacking a straw man here.  I never said that it would.
>> 
> 
> I never said you did. I said it was a "widely stated belief.” Here are quotes from the Clay Mathematics Institute’s Official Description of the P Versus NP Problem http://www.claymath.org/sites/default/files/pvsnp.pdf by Stephen Cook:
> 
> "The security of the Internet, including most financial transactions, depends on complexity-theoretic assumptions such as the difficulty of integer factoring or of breaking DES (the Data Encryption Standard). If P = NP, these assumptions are all false.” ... "Even if P != NP it may still happen that every NP problem is susceptible to a polynomial-time algorithm that works on “most” inputs. This could render cryptography impossible…”
> 
> Cook, who with Leonid Levin, was the first to state the P vs NP problem, and the Clay Mathematics Institute are hardly straw men.

Fair enough.  But the misunderstandings of the relevance of P?=NP are more widespread than that.  It seems to be an equally widely held belief that if “A because B” is false then A must be false.  (Here A = “P?=NP is relevant” and B = “If P=NP it would let us break crypto algorithms because crypto algorithms are NP-hard”.)

rg

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160728/03c350cf/attachment.html>