-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It's hard to understand your question, could you rephrase it? $\endgroup$ – Geoffroy Couteau Jan 19 '18 at 17:55
  • $\begingroup$ Has the Unique Shortest Vector Problem (SVP) been solved? Appears to be a separate question altogether $\endgroup$ – Ella Rose Jul 4 '18 at 13:11
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\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 Feb 20 '18 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$ – indiscreteLogarithm Feb 20 '18 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$ – indiscreteLogarithm Feb 20 '18 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 Mar 4 '18 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$ – indiscreteLogarithm Mar 4 '18 at 11:41
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.