2

I've heard that a modified version of Shor's algorithm can "break" ECC. But what does this mean specifically? What are all the things you can do with this algorithm? Can you:

  • decrypt messages encrypted with the private key? Does the original message have to be in a certain recognizable format in order to do this?
  • encrypt messages to look like they were encrypted with the correct private key (without actually knowing the private key)?
  • forge signatures?
  • Discover the actual private key via just an encrypted message?
  • Discover the private key via just a signature and the message it signs? Just the signature?
  • More?

And are there other ways of "breaking" ECC that have additional properties?

B T
  • 197
  • 1
  • 9

1 Answers1

3

You can take a public key, and compute the corresponding private key. This private key is identical to the private key the owner has. All operations are possible and are indistinguishable, as the keys are the same.

Peter Harmann
  • 7,728
  • 5
  • 20
  • 28
  • What if you don't have the public key? – B T Apr 26 '18 at 21:59
  • @BT Then you can't do anything. But keeping the public key secret is not an option. If it was, you could just use symmetric cryptography, that is currently believed to be immune completely. – Peter Harmann Apr 26 '18 at 22:02
  • Well I was thinking of a situation like mimble wimble where ECC is used but the public key is kept private - or at least isn't stored on the blockchain. In that case, the attacker wouldn't have access to most public keys and so wouldn't be able to derive their private keys (if there's no other way other than using the public key). This is in the context of this discussion about post facto deprivatization or inflation detection: https://www.reddit.com/r/Monero/comments/8erg8e/what_should_monero_do_about_the_soundness_problem/dy0f7os/?context=3 – B T Apr 26 '18 at 22:18
  • @BT I don't know anything about Mimble Wimble, but it sound unlikely the public keys would stay private. But if they really do, then yes, the attacker would not be able to do much. – Peter Harmann Apr 26 '18 at 22:23