Are there lattice-based cryptosystems based i.e., SIS (Short Integer Solutions) and LWE (Learning with Errors) blockchain solutions for a post quantum world?
Has the Unique Shortest Vector Problem (SVP) been solved?
$\begingroup$
$\endgroup$
2
2 Answers
$\begingroup$
$\endgroup$
10
Are there [...] blockchain solutions for a post quantum world?
Quantum Computing and related algorithms are no threat to the current protocol of Bitcoin (and most other blockchain systems I am familiar with) at all. Indeed, Shor's algorithm can solve the Discrete Logarithm Problem (DLP) efficiently, and a modified version exists for the elliptic curve analogue (ECDLP). Blockchain systems in their conventional form are based on
- preimage and collision resistance of the employed hash functions for most functions, including transaction IDs, block IDs, and the Proof-of-Work (PoW) scheme in mining
- hardness of DLP/ECDLP for security of transaction signatures and user addresses (so that private keys can not be found)
At the current state of research, most consider hash functions quantum resistant due to their lack of mathematical structure. As mentioned, (EC)DLP is not resistant.
However, if user addresses are never re-used then this is irrelevant, since an attacker will only learn a users clean (i.e. non-hashed) public key once a transaction is signed in the name of said user address/public key. As long as the hash function (e.g. SHA-256) is preimage-resistant, an attacker has nothing to apply Shor's algorithm on. So there is no pressing need for alternatives yet.
Nonetheless, lattice-based crypto is a proposal that comes up once in a while - to my knowledge no actual blockchain implementation exists as of today. As for the Shortest Vector Problem (SVP): the most efficient known algorithms are mentioned in the Wikipedia article.
answered Jan 19, 2018 at 17:16
-
2$\begingroup$ I am not an expert, but I highly doubt that bitcoin is secure if the signature scheme used for transactions is broken. After sending bitcoins to someone, the sender knows the public key of the receiver. If the scheme is broken, he could then forge a transaction valid under that public key and transfer the money back to his accounts. Or no? $\endgroup$mti– mti2018-02-20 00:58:37 +00:00Commented Feb 20, 2018 at 0:58
-
$\begingroup$ @mti well this is less on-topic for crypto SE but rather a protocol design decision (with security considerations). yes, someone can forge the signature for the attacked address. But as I wrote, this does not matter if addresses are used only once. You see, each transaction empties the address and spends all coins: the desired amount goes to the destination, the rest is spend as "change" back to an address controlled by the sender. So if you always change your address an attacker can sign in the name of an address which has balance 0. $\endgroup$indiscreteLog– indiscreteLog2018-02-20 08:42:09 +00:00Commented Feb 20, 2018 at 8:42
-
$\begingroup$ "he could then forge a transaction valid under that public key and transfer the money back to his accounts" no, reversing transactions is not possible in the network. $\endgroup$indiscreteLog– indiscreteLog2018-02-20 10:28:22 +00:00Commented Feb 20, 2018 at 10:28
-
$\begingroup$ If the signature scheme is broken, then one can create signatures valid with a given public wallet key without knowing the corresponding secret transaction key. This means, however, that one can spend the coins associated with the corresponding wallet. It seems impossible to maintain coin ownership in such a setting! $\endgroup$mti– mti2018-03-04 11:33:53 +00:00Commented Mar 4, 2018 at 11:33
-
$\begingroup$ @mti each "public wallet key" is essentially the hashed public key of a generated elliptic-curve key pair. In the setting we discuss (quantum computer adversary), an attacker can find out private keys to given public keys. But a user's public key only becomes known to the network when it is used to spend coins for the first time - before that, only the hashed Base58 encoded version is known. As I said in my answer: "As long as the hash function (e.g. SHA-256) is preimage-resistant, an attacker has nothing to apply Shor's algorithm on." $\endgroup$indiscreteLog– indiscreteLog2018-03-04 11:41:21 +00:00Commented Mar 4, 2018 at 11:41
$\begingroup$
$\endgroup$
This paper talks about that. From what I can understand although difficult in theory an attack can be used to retrieve the private key and spend all the coins if the used signature scheme is based on elliptic curve cryptography (as in bitcoin). Also advances in quantum computing can arrive a lot faster than expected so btc devs should start working on using lattice-based crypto.
Has the Unique Shortest Vector Problem (SVP) been solved?Appears to be a separate question altogether $\endgroup$