Comparing NTRU and Kyber: Which Quantum-Resistant Algorithm Is a Better Fit for Bitcoin?

Hey everyone, With quantum computing looming ahead, shouldn’t we start considering how Bitcoin’s security could be impacted? Right now, Bitcoin relies on ECDSA, but what’s gonna happen when quantum computers manage to crack it? Two algorithms in the spotlight as potential fixes are NTRU and Kyber. But seriously, which one is actually more suitable for Bitcoin? Let’s get into it. 1-Security, so I heard NTRU is built on lattice problems, which makes it pretty resilient against both regular and quantum threats. Do you think it’ll remain secure as quantum tech evolves? And then we have Kyber. It’s also lattice-based and even part of the NIST post-quantum standardization. Is it really as secure as everyone claims or are there hidden vulnerabilities? 2-Efficiency, NTRU is said to be quite efficient with its smaller key sizes. Sounds like a win for Bitcoin, especially since speed and efficiency are crucial, right? But what’s up with Kyber? It’s efficient too, but its keys are larger. Could that slow things down when we’re talking about Bitcoin’s scalability? 3-Key Sizes, so NTRU has smaller key sizes, around 1-2 KB. How critical is that for Bitcoin in terms of storage and bandwidth management? On the flip side, Kyber’s key sizes are bigger, like 3-4 KB. Will that cause issues as Bitcoin expands, or do you think it’s something we can handle? 4-Real-World Use, NTRU has been around in other cryptocurrencies for a while now. It’s been tested, but can it meet Bitcoin’s long-term demands? Kyber is relatively new but it's making waves. Is that a good sign for the future?

I think this discussion is, while interesting, a bit premature. NIST (not that bitcoin is a US thing, but the guidance here is good) released their document on the timeline for post-quantum encryption (IR 8547) last November.  Here is a decent summary from InfoSec. If you believe the table, there is some confidence that SHA256 will survive at least through 2035.  While there is some concern over its performance against a collision attack, this attack is about getting two keys that produce the same hash value, NOT finding a second key which has a particular hash value associated with another unknown key. I'd be hard pressed to find a sense of urgency that would get me designing or coding the end product - there is only about 70-80K lines of code in the entire core, so not going to be a earth shaking task.  The harder part will be designing the transition - technical and operational - from one hash to the next.  Guessing there are not too many core developers who haven't already had thoughts about how to transition the encryption, if and when needed.  I'm inclined to give this issue a few more years for the alternatives to mature and prove themselves.

Neither. NTRU and Kyber are PKE/KEM - Public Key Encryption / Key Encapsulation Mechanism. You should rather look at: FIPS 204, ML-DSA, former Dilithium FIPS 205, SLH-DSA, former SPHINCS+ FIPS 206, FN-DSA, former FALCON, not yet standardized |-------------------+-------------+------------+-----------+----------+-----------| |                   | Private Key | Public Key | Signature | security |   average | |                   |       bytes |      bytes |     bytes |     bits | block MB* | |-------------------+-------------+------------+-----------+----------+-----------| | secp256k1         |          32 |         32 |        64 |      128 |         2 | |-------------------+-------------+------------+-----------+----------+-----------| | ML-DSA-44         |        2560 |       1312 |      2420 |      128 |        78 | | ML-DSA-65         |        4032 |       1952 |      3309 |      192 |       110 | | ML-DSA-87         |        4896 |       2592 |      4627 |      256 |       150 | |-------------------+-------------+------------+-----------+----------+-----------| | SLH-DSA-SHA2-128s |             |         32 |      7856 |      128 |       164 | | SLH-DSA-SHA2-192s |             |         48 |     16224 |      192 |       339 | | SLH-DSA-SHA2-256s |             |         64 |     29792 |      256 |       622 | |-------------------+-------------+------------+-----------+----------+-----------| | Falcon-512        |        1281 |        897 |       666 |      128 |        33 | | Falcon-1024       |        2305 |       1793 |      1280 |      256 |        64 | |-------------------+-------------+------------+-----------+----------+-----------| * could be off by a factor of 2

Can you give us example which cryptocurrency actually use NTRU cryptography when cryptocurrency generally use only hash and signature cryptography? Do you even read link you shared? 1. Table on link you shared only says ECDSA (<= 256 bits) disallowed after 2035. 2. SHA-256 remains allowed by NIST roadmap. In addition, Bitcoin use hash and signature cryptography, not encryption cryptography. So Core developers don't need to think about transition of encryption cryptography.

I think if you look at Table 7 in the link I posted, it addresses hash functions.  SHA-256 has the highest security rating they give, excluding collision security, which I don't believe is relevant for bitcoin.

Of course it is relevant. If you have SHA-256 collision, then you can have one transaction, sending coins from Alice to Bob, and another transaction, sending them from Alice to Charlie. If transaction hash is identical in both cases, then you can send the first version to one part of the network, and another version to other nodes. And then, when the next block is built on top of the current chain, you can easily trigger a fork, when Bob or Charlie will try to move their coins anywhere, because then, one group of nodes will hard-reject the next mined block (and all blocks built on top of it).

It's only that as of BIP30 no two transactions can have the same transaction hash as far as I understand BIP30 (or do I misunderstand you?). I don't know what benefits one could've from this. Well and how do you control the required Bitcoin node network separation? With BIP30 in place only the first accepted transaction will be valid when it sits in mempool or gets confirmed. The second transaction with same transaction hash should be rejected by nodes who are aware of the other transaction already. Once one of the transactions is confirmed (mined in a block) the other transaction immediately becomes invalid, no block with the second one could be mined as valid. As miners are usually very well connected to each other, it seems highly unlikely to me to provoke such a malicious chain split and block denial scenario. I'm not saying that possible SHA-256 collisions can't cause other severe issues. And when SHA-256 is about to become compromisable, it will cause issues in other areas as well, likely way before this actually can happen. In my opinion quantum computers are still pretty much overhyped. Surely an interesting research field and thus the need for a lot of money to be pumped into it. Let's see when QC actually solve some real, not only academic, problems.

In case of BIP-30, there were the same coinbase transactions in different blocks. But it was no collision there. If you hash the same data, you will get the same result. But if some hash function is broken, then you have two different messages, hashing to the same value. And then, when you download a new block hash, and compute some Merkle Tree, you know, that it contains a given hash, but you don't know, which message was really hashed. It allows the attacker to fork the network. One node will hear "txid(Alice -> Bob)=0xbadc0ded", and another node will hear "txid(Alice -> Charlie)=0xbadc0ded". In a block number 1234567, everyone will see, that transaction 0xbadc0ded was confirmed, but nobody would know, which version should be used: "Alice -> Bob" or "Alice -> Charlie". Some nodes will hear "Alice -> Bob" first, and they will think, that now Bob has the coins, while other nodes will hear "Alice -> Charlie" first, and they will assume, that Charlie has the coins. Then, you will have another block, for example 1234600, with transaction "Bob -> Anyone" or "Charlie -> Anyone". And then, one group of nodes will accept it, while another group of nodes will reject it, and mark block 1234600 as invalid (and all blocks on top of it). By sending different transactions to different nodes. Some will hear "Alice -> Bob" transaction first, and some will hear "Alice -> Charlie" transaction first. Every node will check, that "txid()=0xbadc0ded", so the block number 1234567 will be accepted by everyone, but then, different nodes will save different UTXOs in their database, so when they will see "Bob -> Anyone" or "Charlie -> Anyone" transaction later, some of them will accept it, and some of them will reject it (because the previous output Script will be different). Yes, but when you have some new node, then when it starts downloading the chain, you can send "Alice -> Bob" transaction to one node, and "Alice -> Charlie" transaction to another node, during Initial Blockchain Download.

Neither, since once we need a quantum resistant algo they will both be old and outdated. Quantum is just another buzzword. We are talking such a long time away that it's like talking about SSL 1.0 in 1995. It was broken to start but it was something for Netscape to talk about. It was quickly followed by 2.0 and 3.0 (1996) but all were inferior to TLS which came out in 1999. BUT SSL 3.0 was still not broken where you could decrypt it till 2013. -Dave

This would require not only an arbitrary collision, but one in which the input relates to Bob and/or Alice (as possibly craftable if the hash function also isn't preimage-resistant). The implications of a mere collision attack should not be overestimated as long as there is no known way to compute more collisions from a given collision (as it was the case e.g. for MD5).