# Analysing communication complexity of a protocol

My question is more about the practical side of designing crypto. protocols and it is related to complexity. So, if you think it's irrelevant to this forum please kindly let me know and I will remove the question.

In many crypto. protocols the communication cost is very important. In the following, I consider a client-server protocol where the server computes a single value and sends it to the client. Assume the protocol requires modular arithmetics at a server-side on a finite field of size 120 bits, i.e. $\mathbb{F}_p$, where $|p|=120-bit$. Assume we have improved the previous protocol and now we can work on a smaller filed, e.g. $|p|=80-bit$.

As we know we cannot say the communication cost has been reduced by $40$ bits, as the value can be $1$ or $119$ bits value, because it involves a modular operation.

Question: How do we analyze/argue the communication improvement of the above protocol?

## 1 Answer

(Revised based on poncho's comment.)

If p is of 120-bit length, then any field element should better be sent with 120 bits. If you want to send, say 1, with a 1-bit message, then this reveals the element's length and adds the computation complexity of constructing variable-length messages for different elements. Besides, only half of the field elements may have leading 0s, so sending messages with variable lengths does not save much communication bits.

As for the communication complexity, it depends on what message you are sending and may not be linear to the field size.

• "I do not think the number of bits can vary between 1 and 119"; actually, you could use a variable length encoding technique. Of course, if you include the bits to indicate the length of the field (or otherwise make the it unambiguous), and if all $2^{120}$ values are equiprobable, then I believe it can be shown that such a variable length encoding increases the average size of the message – poncho Feb 18 '18 at 19:40
• @poncho Thanks for pointing this out! Yes, including length is possible. – Shan Chen Feb 18 '18 at 19:49