Bas Westerbaan writes: > From a performance perspective BAT ( https://eprint.iacr.org/2022/031 ) > improves considerably over ML-KEM in certain use cases: its > ciphertexts and public keys are smaller, but its keygen is slower.
I'll fill in some numbers here, and then point out other options that remove the "certain use cases" restriction. I'll skip commenting on security since I'd suggest CFRG as a better venue for that; also, I won't comment on patents in this message. To be clear, I'm not endorsing any of the proposals listed below; I'm just giving performance numbers. Quantitatively, https://eprint.iacr.org/2022/031 says that BAT-512 has a 521-byte public key, 473-byte ciphertext, 29 million cycles (on Intel Coffee Lake) for keygen, 11135 cycles for enc, and 59745 cycles for dec. Kyber-512 has an 800-byte public key, 768-byte ciphertext, 23028 cycles (https://bench.cr.yp.to/results-kem/amd64-r24000.html, also Coffee Lake) for keygen, 35172 cycles for enc, and 27404 cycles for dec. https://cr.yp.to/papers.html#pppqefs includes conversion of bytes and cycles to dollar costs, in particular showing how to buy 2^51 cycles per dollar and roughly 2^40 bytes of Internet traffic per dollar. Let's imagine for purposes of comparison that these are exact numbers. The total cost of pk+enc+ct+dec is then * 0.94 nanodollars for BAT-512 and * 1.45 nanodollars for Kyber-512. Meanwhile BAT-512 keygen is 12.9 nanodollars, so a key doesn't have to be reused many times before BAT-512 has lower total cost than Kyber-512. As you note, BAT-512 doesn't score so well when a key is used just once: * 13.8 nanodollars for BAT-512 and * 1.46 nanodollars for Kyber-512. It's still not clear that this extreme is actually a problem with BAT-512. Sending 2MB for a below-average web page is 1800 nanodollars, and the number of connections per web page has dropped to 10, never mind the impact of session reuse. But, for people who are worried about this cost maybe being a problem for BAT-512, let's pick another competitor: SMAUG-T. https://bench.cr.yp.to/results-kem/amd64-r24000.html shows smaugt1 as 36942 cycles for keygen, 22192 cycles for enc, and 34546 cycles for dec. https://bench.cr.yp.to/results-kem.html shows 672 bytes for public key and 672 bytes for ciphertext. Even if a key is used just once, this costs just 1.26 nanodollars. For comparison, a key exchange with fresh X25519 keys costs only about 2^17 cycles on each side (see https://lib25519.cr.yp.to/speed.html), plus sending 2^5 bytes each way, for a total cost (both sides together) of 0.16 nanodollars. This means * 1.62 nanodollars for X25519+kyber512, * 1.46 nanodollars for kyber512, * 1.42 nanodollars for X25519+smaugt1, and * 1.26 nanodollars for smaugt1. As a side note, I don't know how anyone looking at these numbers would think that the second line is the right one to aim for. We can't have security as the top priority because 1.61 nanodollars per key exchange could be a big problem with gazillions of key exchanges, so we should move to 1.45 nanodollars but not to 1.26 nanodollars? The second line is in an uncomfortable position of prioritizing neither security nor cost. To be clear, SMAUG-T is just one of the proposals that's more efficient than Kyber. For example, https://eprint.iacr.org/2023/1298 says that NEV'-512 has a 615-byte public key, a 615-byte ciphertext, 20620 cycles for keygen (on Haswell), 30787 cycles for enc, and 23841 cycles for dec. That's just 1.15 nanodollars. ---D. J. Bernstein _______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
