Why do we implement a protocol? 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:


Do we implement it for proof of concept?
Do we implement it to support our claim that the protocol is efficient?
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.)