0
$\begingroup$

Suppose I had a new public-key or key exchange protocol. How do I objectively evaluate it so as to determine if it is worth sharing with the broader community? Whenever developing a cryptosystem, it is important to ask "who cares?", to see if it addresses any challenges that current systems face, but it is unclear exactly how to answer that "who cares?" question.

For example, is there a "threshhold of uniqueness" where if your new public-key cryptosystem passes that threshold then it is worth sharing? Are there any standard tests that one could put the system through to test its efficacy, and hence its worth? What if its security reduces to known hard problems? To what extend does speed and key-size matter, and how would you test if such quantities for your public-key crypto-system are "good"?

$\endgroup$

1 Answer 1

4
$\begingroup$

Suppose I had a new public-key or key exchange protocol. How do I objectively evaluate it so as to determine if it is worth sharing with the broader community?

The first question anyone should ask is "why would we think that it is secure?". Until you tackle that question, how it performs is not that relevant.

What if its security reduces to known hard problems?

That would be good (assuming that these are well studied hard problems; not quite as good if the hard problem is something you invented, but not a deal-breaker either). On the other hand, for public key encryption, you need to show that, given the public key and a large number of ciphertexts, if you can extract any information about the plaintexts, you can solve the hard problem (and that still holds even if you give the attacker the facility to query his own ciphertexts). For key exchange, it's not quite that broad (you can assume that, for key exchange, you use a public key only once and throw it away), but still you need to show that finding the shared secret is still equivalent to the hard problem.

And, at this point, it is of interest whether your hard problem is "Quantum Resistant", that is, whether it remains infeasible even if the attacker has a Cryptographically Relevant Quantum Computer) - if we don't care about Quantum Resistance, then it is frankly hard to beat ECC.

Assuming the above (and that you can set the security parameters such that the hard problem is infeasible to solve), then further questions come into play:

  • Is the hard problem one which previously proposed public key encryption or key exchange algorithms use? If it is based on (say) ideal lattices, then you will need to show that it is actively better than what's out there now; if it's based on something that hasn't been used, or only lightly used, the requirements is less stringent, as you don't need to be 'better', 'usable' may be good enough, as there is something to be said about relying on independent hard problems.

  • What is the public key size? Ciphertext size? Private key size is less important, but not completely irrelevant.

  • How does it perform, in public key generation, public key encryption and public key decryption?

  • Is it well suited for small devices (e.g. IOT or HSMs)? How much memory does it need to perform its internal computations? How easy is it to protect against side channel attacks (timing, cache based, DPA-style attacks, fault attacks)?

  • Is it well suited for large devices needing high performance (e.g. TLS servers)?

  • Does it have additional features, such as working in a threshold manner (where several parties jointly share a private key, and $t$ of them are needed to decrypt without disclosing their share of the private key)?

$\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.