# 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?

• "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