The cr.yp.to blog
Table of contents (Access-I for index page)
| 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.