Neal Koblitz, som förutom att han åkt tåg i Peru är professor i matematik vid University of Washington:

Neal har skrivit en tankeväckande och läsvärd artikel publicerad i senaste numret av American Mathematical Society Notices, kallad The Uneasy Relationship Between Mathematics and Cryptography om förhållandet mellan matematik och kryptologi samt varför han inte tror på begreppet bevisbar säkerhet.

Jag är inte kryptolog, och (kan jag erkänna) har aldrig känt mig helt komfortabel och naturligt hemma i matematikens magiska och fantastiska värld. För mig är det därför fascinerande att läsa en artikel av en person som tittar på kryptologi från det motsatta hållet (om man kan kalla det det).

Neal Koblitz börjar med en kort bakgrund till sitt engagemang inom kryptologin och hur han som matematiker var med och publicerade dom första rönen vad gäller att använda olika typer av kurvor (exempelvis elliptic curve) för att skapa assymetriska krypton. Men huvudelen av artikeln är fokuserad på matematikers och kryptologers olika bakgrund, hur man förhåller sig till sin forskning samt vad som egentligen är ett bevis.

En skillnad mellan kryptologi och matematik som Neal tar upp är hur resultat publiceras:

In 1996 I was the program chair of Crypto. To someone trained in mathematics this was an unsettling experience. About two-thirds of the submissions arrived by courier mail within 48 hours of the final deadline. Many had obviously been rushed and were full of typesetting errors. One author had sent me only the odd-numbered pages. A few had violated the requirement of anonymity (there was a policy of double-blind reviews). Several had disregarded the guidelines that had been sent to them.
And in many cases the papers had little originality; they were tiny improvements over something the same authors had published the year before or a minor modification of someone else’s work.

Mathematical publishing works differently. In the first place, most articles appear in journals, not conference proceedings—and journals don’t have deadlines. In the second place, people in mathematics tend to have a low opinion of authors who rush into print a large number of small articles—the derogatory term is LPU (least publish- able unit)—rather than waiting until they are ready to publish a complete treatment of the subject in a single article.

Mathematicians, who are part of a rich tradition going back thousands of years, perceive the passing of time as an elephant does. In the grand scheme of things it is of little consequence whether their big paper appears this year or next. Computer science and cryptography, on the other hand, are influenced by the corporate world of high technology, with its frenetic rush to be the first to bring some new gadget to market. Cryptographers, thus see time passing as a hummingbird does. Top researchers expect that practically every conference should include one or more quickie papers by them or their students.

Neal Koblitz verkar alltså anse att kryptologin som en del av datavetenskap skyndar med sina resultat, och detta syns inte minst på de bevis som används. Koblitz skriver:

The idea of “provable security” is to give a mathematically rigorous proof of a type of conditional guarantee of the security of a cryptographic protocol. It is conditional in that it typically has the form “our protocol is immune from an attack of type X provided that the mathematical problem Y is computationally hard.

The form that proofs of security take is what is known as a reduction. Reductions from one problem to another occur implicitly throughout mathematics; in computer science, reductions are the main tool used to compare and classify problems according to their difficulty.

In provable security papers the authors try to prove that a mathematical problem that is widely believed to be computationally hard, such as factoring large integers or finding elliptic curve discrete logs, reduces to a successful attack of a prescribed type on their cryptographic protocol.

Och vad är då kruxet? Jo ett stort krux som Koblitz pekar på är att även om de problem som man försöker reducera sitt säkerhetsproblem till är asymptotiskt svåra, innebär det inte att säkerhetsproblemen är säkra i de data/nyckelstorlekar som används praktiskt:

What had happened was that people had made recommendations for parameter values that were based on an asymptotic theorem. That theorem said that in the limit as N​ approaches infinity, you can securely generate O (log​log​N​) pseudorandom
bits each time you perform a squaring modulo the composite number N​. (Here “securely” means, roughly speaking, that no one can distinguish between the sequence and a truly random one by an algorithm that runs in reasonable time.) However, as I mentioned when discussing Joe Silverman’s xedni calculus, it is fallacious to use an asymptotic result as a practical guarantee of security. Rather, one needs to perform a detailed analysis using realistic ranges for the parameters.

Koblitz tar som exempel upp problemet med OAEP och den förbättring som Krawczyk publicerade 2005.

Jag kan som sagt för lite för att bedöma om Koblitz har rätt eller ej, men jag tycker att hans artikel är läsvärd och inte så lite småskrämmande. Koblitz ser ut att få stöd av iaf James A. Donald som på maillistan Cryptography postade följande tanke:

If a proof is a record of a mental journey in which one person has discovered an important truth, and then made a record of that journey adequate so that a second person can walk the same path and see the same truth, then cryptography could do with more and better proofs.

If, on the other hand, a proof is an argument impressively decorated with mathematical sounding jargon, cryptography could do with a good deal fewer of them.

Vad tror du?