Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In general, after we design a secure cryptographic protocol and make sure that it is efficient (e.g. through complexity analysis) we implement it.

Questions:

  1. Do we implement it for proof of concept?
  2. Do we implement it to support our claim that the protocol is efficient?
share|improve this question
    
@otus I meant in particular for the research papers,... . We go for the implementation, indeed if it seems to us that it is fast enough. – user153465 Jan 23 at 14:31
1  
@otus: to write a paper about it, perhaps??? – poncho Jan 23 at 15:01
    
@poncho If you think the question is not good/clear enough feel free to edit it, please. – user153465 Jan 23 at 15:22
2  
If you don't implement it, how is anyone ever to use it? – zwol Jan 23 at 19:29
1  
@LightnessRacesinOrbit If you're an academic, publishing a paper about your castle in the air might be enough. – CodesInChaos Jan 24 at 10:43
up vote 11 down vote accepted

I assume the question is related to academic work: why do we implement a protocol if we already know how efficient it is by a complexity analysis? The answer depends very much on the type of protocol. However, the answer typically is that a theoretical complexity analysis usually does not suffice to understand the concrete efficiency. If the "previously best known protocols" required a certain number of operations and your improvement is exactly the same but with less operations, then this could suffice. However, this is rarely the case. Rather, your protocol may have less exponentiations but more communication; it may have less symmetric operations but be less memory efficient. It is almost impossible to really know that it's more efficient without implementing it.

Another issue, which is certainly the case in secure multiparty computation (where I work), is that implementation helps us understand what the bottlenecks are. In fact, we are very often surprised at what the "expensive" part is. In just one example, in this paper (sorry for the self citation, but it's just a good illustrative example), we were very surprised to find out that a large percentage of the time went on a matrix inversion which had nothing to do with the cost of the cryptographic operations. Without implementing, we never would have found out about this.

One thing that as a field we have to improve upon is the quality of our work in this sense. We don't have good benchmarks and implementations and comparisons are all very ad hoc.

I will finish with one final comment. Despite the above, not all new protocols need to be implemented in order to be published. When the protocol contains an important new idea, or when it clearly beats the previous work, then it can be published without an implementation. However, follow up work with implementation is always important. (Of course, protocols whose claim is that of asymptotic and theoretical efficiency never need to be implemented.)

share|improve this answer
    
Interesting to see that you do implement to find out the bottlenecks, that's something I would usually not expect. Anyway, both answers conclude that it would be a good idea to provide implementations of a protocol ... which reminds me that I should finish one sooner rather than later. – Maarten Bodewes Jan 24 at 12:03
    
Thank you for the answer. Thus, the main aim of the implementation (in this field) is the second option in the question. Am I right? – user153465 Jan 25 at 9:58
1  
Yes, the main aim is the second option. However, there is another main aim which is for us - the protocol designers - to understand as well. There are sometimes big surprises. – Yehuda Lindell Jan 25 at 10:55

Do we implement it for proof of concept?

Absolutely. It's very easy to miss vital points if no implementation exists. W3C for instance doesn't even allow protocols to be standardized without reference implementation(s). Furthermore, an implementation may show small improvements as well.

Personally I would require an implementation of all the (minimal) options as well. If there are too many options for that, then the protocol is likely too complicated. In that case the design needs to be simplified or a choice should be made which parts should be part of minimal implementation requirements.

Note that the number of protocol types explodes exponentially with the number of options. E.g. if a protocol contains 3 block-ciphers, 3 key sizes and 3 modes-of-encryption (that can be freely combined) then you already have to implement and test $3 \times 3 \times 3 = 27$ combinations.

To provide an example, I know of a protocol that used AES-128, AES-192 and AES-256 only to find out that there was a problem because 192 is not a multiple of the 128 bit block size of AES.

A reference implementation may also provide clarification where a protocol is not completely clear. In other words, it can be used to find out the intent of the authors of the protocol. If this is the case then obviously the formal description of the protocol should be adjusted in the end.

Do we implement it to support our claim that the protocol is efficient?

This, in my opinion, is less important unless the protocol is designed for applications that require a very precise definition of efficiency on a specific platform. The reason is not that efficiency is not important; The efficiency can however normally be calculated pretty accurately.

Furthermore, efficiency is very implementation specific, so just publishing results for a reference design may not paint a complete picture. Optimizing the reference implementation may also compromise the readability and the chance of errors. Separate implementations for specific platforms are often used instead.


Notes:

  • it is impossible to provide test vectors as well if no reference implementation is provided;
  • often only test vectors for octet-aligned data is provided when the protocol or algorithm is defined to operate on bits.
share|improve this answer
    
"W3C for instance doesn't even allow protocols to be standardized without reference implementation(s)." That's kind of orthogonal to the question. It's hard to imagine that the W3C would care about standardizing a protocol that hadn't been implemented at all! – David Richerby Jan 23 at 21:20
2  
@DavidRicherby The problem - if I understood correctly - is that there were too many web related protocol standards that had issues when implemented (in e.g. a browser) - if they were implemented at all. So after a while they did the sensible thing and required an implementation. W3C doesn't however just standardize protocols after they have been in frequent use (for the first forms of HTML this was obviously the case, but not for many of the protocols that came after that, such as XHML / HTML 5). – Maarten Bodewes Jan 23 at 22:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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