The cr.yp.to blog

Newer (Access-K): 2015年11月20日: Break a dozen secret keys, get a million more for free: Batch attacks are often much more cost-effective than single-target attacks. #batching #economics #keysizes #aes #ecc #rsa #dh #logjam

Older (Access-J): 2015年02月18日: Follow-You Printing: How Equitrac's marketing department misrepresents and interferes with your work. #equitrac #followyouprinting #dilbert #officespaceprinter

Table of contents (Access-I for index page)

2025年10月05日: MODPOD: The collapse of IETF's protections for dissent. #ietf #objections #censorship #hybrids

2025年10月04日: NSA and IETF: Can an attacker simply purchase standardization of weakened cryptography? #pqcrypto #hybrids #nsa #ietf #antitrust

2025年09月30日: Surreptitious surveillance: On the importance of not being seen. #marketing #stealth #nsa

2025年04月23日: McEliece standardization: Looking at what's happening, and analyzing rationales. #nist #iso #deployment #performance #security

2025年01月18日: As expensive as a plane flight: Looking at some claims that quantum computers won't work. #quantum #energy #variables #errors #rsa #secrecy

2024年10月28日: The sins of the 90s: Questioning a puzzling claim about mass surveillance. #attackers #governments #corporations #surveillance #cryptowars

2024年08月03日: Clang vs. Clang: You're making Clang angry. You wouldn't like Clang when it's angry. #compilers #optimization #bugs #timing #security #codescans

2024年06月12日: Bibliography keys: It's as easy as [1], [2], [3]. #bibliographies #citations #bibtex #votemanipulation #paperwriting

2024年01月02日: Double encryption: Analyzing the NSA/GCHQ arguments against hybrids. #nsa #quantification #risks #complexity #costs

2023年11月25日: Another way to botch the security analysis of Kyber-512: Responding to a recent blog post. #nist #uncertainty #errorbars #quantification

2023年10月23日: Reducing "gate" counts for Kyber-512: Two algorithm analyses, from first principles, contradicting NIST's calculation. #xor #popcount #gates #memory #clumping

2023年10月03日: The inability to count correctly: Debunking NIST's calculation of the Kyber-512 security level. #nist #addition #multiplication #ntru #kyber #fiasco

2023年06月09日: Turbo Boost: How to perpetuate security problems. #overclocking #performancehype #power #timing #hertzbleed #riskmanagement #environment

2022年08月05日: NSA, NIST, and post-quantum cryptography: Announcing my second lawsuit against the U.S. government. #nsa #nist #des #dsa #dualec #sigintenablingproject #nistpqc #foia

2022年01月29日: Plagiarism as a patent amplifier: Understanding the delayed rollout of post-quantum cryptography. #pqcrypto #patents #ntru #lpr #ding #peikert #newhope

2020年12月06日: Optimizing for the wrong metric, part 1: Microsoft Word: Review of "An Efficiency Comparison of Document Preparation Systems Used in Academic Research and Development" by Knauff and Nejasmic. #latex #word #efficiency #metrics

2019年10月24日: Why EdDSA held up better than ECDSA against Minerva: Cryptosystem designers successfully predicting, and protecting against, implementation failures. #ecdsa #eddsa #hnp #lwe #bleichenbacher #bkw

2019年04月30日: An introduction to vectorization: Understanding one of the most important changes in the high-speed-software ecosystem. #vectorization #sse #avx #avx512 #antivectors

2017年11月05日: Reconstructing ROCA: A case study of how quickly an attack can be developed from a limited disclosure. #infineon #roca #rsa

2017年10月17日: Quantum algorithms to find collisions: Analysis of several algorithms for the collision problem, and for the related multi-target preimage problem. #collision #preimage #pqcrypto

2017年07月23日: Fast-key-erasure random-number generators: An effort to clean up several messes simultaneously. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs

2017年07月19日: Benchmarking post-quantum cryptography: News regarding the SUPERCOP benchmarking system, and more recommendations to NIST. #benchmarking #supercop #nist #pqcrypto

2016年10月30日: Some challenges in post-quantum standardization: My comments to NIST on the first draft of their call for submissions. #standardization #nist #pqcrypto

2016年06月07日: The death of due process: A few notes on technology-fueled normalization of lynch mobs targeting both the accuser and the accused. #ethics #crime #punishment

2016年05月16日: Security fraud in Europe's "Quantum Manifesto": How quantum cryptographers are stealing a quarter of a billion Euros from the European Commission. #qkd #quantumcrypto #quantummanifesto

2016年03月15日: Thomas Jefferson and Apple versus the FBI: Can the government censor how-to books? What if some of the readers are criminals? What if the books can be understood by a computer? An introduction to freedom of speech for software publishers. #censorship #firstamendment #instructions #software #encryption

2015年11月20日: Break a dozen secret keys, get a million more for free: Batch attacks are often much more cost-effective than single-target attacks. #batching #economics #keysizes #aes #ecc #rsa #dh #logjam

2015年03月14日: The death of optimizing compilers: Abstract of my tutorial at ETAPS 2015. #etaps #compilers #cpuevolution #hotspots #optimization #domainspecific #returnofthejedi

2015年02月18日: Follow-You Printing: How Equitrac's marketing department misrepresents and interferes with your work. #equitrac #followyouprinting #dilbert #officespaceprinter

2014年06月02日: The Saber cluster: How we built a cluster capable of computing 3000000000000000000000 multiplications per year for just 50000 EUR. #nvidia #linux #howto

2014年05月17日: Some small suggestions for the Intel instruction set: Low-cost changes to CPU architecture would make cryptography much safer and much faster. #constanttimecommitment #vmul53 #vcarry #pipelinedocumentation

2014年04月11日: NIST's cryptographic standardization process: The first step towards improvement is to admit previous failures. #standardization #nist #des #dsa #dualec #nsa

2014年03月23日: How to design an elliptic-curve signature system: There are many choices of elliptic-curve signature systems. The standard choice, ECDSA, is reasonable if you don't care about simplicity, speed, and security. #signatures #ecc #elgamal #schnorr #ecdsa #eddsa #ed25519

2014年02月13日: A subfield-logarithm attack against ideal lattices: Computational algebraic number theory tackles lattice-based cryptography.

2014年02月05日: Entropy Attacks! The conventional wisdom says that hash outputs can't be controlled; the conventional wisdom is simply wrong.

2015年03月14日: The death of optimizing compilers: Abstract of my tutorial at ETAPS 2015. #etaps #compilers #cpuevolution #hotspots #optimization #domainspecific #returnofthejedi

"ETAPS" [home page] [Wikipedia page] is a conference federation, the "European Joint Conferences on Theory and Practice of Software". ETAPS 2015, which combines

CC 2015 (24th International Conference on Compiler Construction),
ESOP 2015 (24th European Symposium on Programming),
FASE 2015 (18th International Conference on Fundamental Approaches to Software Engineering),
FoSSaCS 2015 (18th International Conference on Foundations of Software Science and Computation Structures),
POST 2015 (4th International Conference on Principles of Security and Trust), and
TACAS 2015 (21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems),

will be held next month in London.

I was invited to give one of two 90-minute tutorials at ETAPS 2015. I decided to speak on "The death of optimizing compilers", which perhaps wasn't exactly what the organizers wanted to hear. Coincidentally, the ETAPS 2015 web page ran out of space to hold my abstract and had to compress the abstract to one paragraph, so I'm posting the complete abstract here.

[2022年01月09日 update: Updated links above.]

Abstract: In the ancient days, computers were slow, and compilers were stupid, and the software engineer's solemn duty was to manually squeeze every last cycle out of the software. Today the situation is quite different, but not in the direction one might expect.

Have computers become so fast that nobody cares about optimization any more? Certainly not: most users still spend time waiting for computers. As computation has become cheaper, users have correspondingly expanded the volume of data that they are handling, and optimization remains a critical challenge for the occasional "hot spots" in the code.

Most programmers today never touch these hot spots. The reduced cost of computation means that more and more code runs freezingly cold, freeing up more and more programmers to ignore performance. However, the hot spots still exist. This tutorial will focus on how these hot spots are handled in the real world.

Have compilers become so smart that they automatically turn clean high-level code for these hot spots into optimized code, removing the need for humans to be optimization experts? The reality, unfortunately, is very much the opposite: general-purpose "optimizing" compilers are falling farther and farther behind the actual capabilities of modern processors.

This tutorial is an introduction to (1) what current and near-future processors are capable of; (2) how modern high-speed software libraries actually work; and (3) the increasing dominance of domain-specific tools to engineer high-speed software. This tutorial is designed to be fully comprehensible to audience members who are not optimization experts.

Version: This is version 2022年01月09日 of the 20150314-optimizing.html web page.