NTRU vs Kybe: Which Quantum Resistant Algorithm Is Better for Bitcoin?

[Newuserfriendly]

Hey guys,
With quantum computing on the horizon, don’t you think it’s time to start thinking about how Bitcoin’s security might be affected? Right now, Bitcoin uses ECDSA, but what happens when quantum computers can break it? There are two algorithms that are getting a lot of attention as possible solutions: NTRU and Kyber. But which one is actually better for Bitcoin? Let’s dive into it  .

1-Security, Have you heard that NTRU is based on lattice problems? It’s pretty resistant to both regular and quantum attacks.  But do you think it’ll stay secure as quantum computing advances?
Then there’s Kyber.  It’s also lattice-based and is actually part of the NIST post-quantum standardization.  Do you think it’s as solid as they say, or could there be weaknesses we haven’t found yet?

2–Efficiency, NTRU is known for being pretty efficient with smaller key sizes.  Doesn’t that sound like a win for Bitcoin, especially when speed and efficiency matter?
But what about Kyber? It’s efficient too, but its key sizes are bigger.  Do you think that could slow things down when it comes to Bitcoin’s scalability?

3–Key Sizes, NTRU uses smaller key sizes (around 1-2 KB).  How important do you think that is for Bitcoin’s storage and bandwidth?
But Kyber uses larger key sizes (around 3-4 KB).  Could this be a problem as Bitcoin grows, or do you think it’s manageable?

4–Real-World Use, NTRU has been used in other cryptos for years.  It’s proven, but do you think it’ll be able to handle the demands of Bitcoin in the long run?
Kyber is newer but is already gaining a lot of attention.  Could it be the future of quantum-resistant crypto, or is it too early to say?

So, what do you think? NTRU looks fast and efficient, but is it strong enough for the future? Or is Kyber the way to go, with its solid reputation and growing support? Let me know your thoughts!

[Queuemech]

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.

[j2002ba2]

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

[ABCbits]

4–Real-World Use, NTRU has been used in other cryptos for years.  It’s proven, but do you think it’ll be able to handle the demands of Bitcoin in the long run?
Kyber is newer but is already gaining a lot of attention.  Could it be the future of quantum-resistant crypto, or is it too early to say?

Can you give us example which cryptocurrency actually use NTRU cryptography when cryptocurrency generally use only hash and signature cryptography?

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.

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.

[Queuemech]

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.

[stwenhao]

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).

[Cricktor]

~~~

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.

[stwenhao]

no two transactions can have the same transaction hash as far as I understand BIP30

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.

I don't know what benefits one could've from this.

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).

Well and how do you control the required Bitcoin node network separation?

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).

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.

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.

[DaveF]

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

[zeuner]

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).

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).