0
$\begingroup$

As far as I know, a secret key corresponding to a given public key is not unique. So, for example, there are actually multiple secret keys that can produce the same digital signature under RSA signature scheme.

What I wonder is, how can I compute the expected time to find a matching secret key of a given public key? I assume some details are given like the length of keys, the key generation algorithm etc.

Also, is there a public-key encryption scheme s.t. there's a unique secret key for each public key?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Although I guess that having a single private key isn't a requirement for asymmetric primitives to be secure, the idea that you can calculate multiple keys without knowing any other key would of course mean that you can trivially break the scheme. Breaking a scheme commonly means finding the private key; so for each scheme you simply have to check the security strength, e.g. on keylength.com . The time to find a private key is then at least the complexity shown - assuming the system / implementation isn't broken. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 1, 2019 at 2:02

1 Answer 1

Reset to default
2
$\begingroup$

The expected time to compute a secret key from a public key is of course entirely dependent on the scheme and the security parameter. Of course for the scheme to be secure, the probability that an adversary can make such computation in poly time must be negligible.

Regarding your second question, you might want to look here. Again this is entirely dependent on the scheme.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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