Comparison: complexity measures vs. security

Question

Assume that you want to compare several cryptographic primitives (say, encryption schemes), and choose one. You need to consider several complexity measures, such as the key length, encryption time, decryption time, etc. In order for the comparison to be fair, all primitives in question must provide the same level of security.

As an example, let us consider RSA, ECC, and NTRU. Assume that we want the cryptosystem to be secure against a passive adversary, whose computational power is limited to at most $2^{100}$ operations. By "passive adversary", we mean that the adversary is limited to chosen-plaintext attacks (since we are comparing public-key encryption schemes). Now, we want to know the key length to be chosen for each scheme.

To answer this question, we consider the complexity of the most efficient attacks against RSA, ECC, and NTRU, which in turn requires a great knowledge of the literature.

Is there any resource/survey (website, paper, tool, etc.) which helps in such comparisons?

Note: The website keylength.com, while being a helpful tool in its own right, is not an answer to this question. The reason is that keylength.com merely recommends a minimum key length to be used in different scenarios (say symmetric or asymmetric encryption), but leaves out most of the concrete schemes (say, NTRU, twofish, serpent, etc.)

Answer 1

Shoup published in 2004 a paper on handling sequences of games, which targets the probability/hardness of combinations of cryptographic assumptions:

"Sequences of Games: A Tool for Taming Complexity in Security Proofs"

With those conclusions you can calculate the probabilities in your own algorithm and set the parameters accordingly.

However, real implementations have one problem with exact numbers: They are unknown in general. For example, in the strong cryptographic sense AES is "broken", because there is an attack with lower complexity than brute-force. This is just a couple of bits less complex, which is still far beyond the possibilities of today's attackers. But maybe someone comes up with an even lower number soon.

In general, starting with keylength.com, or NIST recommendations respectively: chapter 5.6.1 (page 62) gives an overview about the complexity comparisons of symmetric and asymmetric schemes. Sometimes these levels are also named like "ultra short", "short", etc.

For multiparty computation, "TASTY: tool for automating secure two-party computations" from Henecka et al. is also an interresting paper (2010), which describes a tool for automated analysis

Answer 2

Not sure what you are trying to do but are you not approaching it the wrong way?

NIST already recommends algoorithms/ciphers for use in their environments. This means they have vetted these and are deemed secure. Now you want performance as well. So use openssl and see which of the algorithms are of acceptable performance to you. Like you said choose key lengths that provide the same level security when comparing different algorithms. That way your performance numbers will be comparable.

Also I wouldn't try to go beyond any algorithms NIST recommends. For example AES is good for any application. There is no reason to use or try twofish. There are enough ways to shoot yourself in the foot just by using AES itself. Stick to one and that way even if you are creating some recommendations for your users/employees its less complicated.

Hope that helps.

Answer 3

Unfortunately it seems you'll have to do a survey on the subject on your own. This article seems to be relevant to what you're asking but I haven't read myself so I can't tell for sure. Unfortunately it seems to be outdated (1993). Quoting from the abstract:

The author reviews encryption algorithms and standards, how they compare, how they differ, and where they are headed. Attention is given to secret-key cryptosystems, public-key cryptosystems, digital signature schemes, key-agreement algorithms, cryptographic hash functions, and authentication codes. Applications considered are secure electronic mail, secure communications, directory authentication and network management, banking, and escrowed encryption.

A more recent article (if only by 4 years) is this.

If you have to present a report on state-of-the-art crypto for your employer or someone else you'll have to do the bulk of the work. Otherwise there are some good books on the subject that cover most of the aspects you seem to be after.

Introduction to Modern Cryptography by Katz and Lindell
Cryptography Engineering: Design Principles and Practical Applications by Schneier, Ferguson and Kohno