Optimal Protocols

In this experiment, we experiment with two extreme cases of the metric function to see how we can benefit from the automatic protocol generation to generate optimal protocols.

In the first case, we consider a smart-card, which has a built-in cryptographic accelerator and hence, can perform fast encryption/decryption operations. But the smart-card has a slow link to the card reader. In this case, we set the cost of encryption much lower than the bandwidth cost (UNIT_ELEMENT_COST in the specification). With this metric function, we find one symmetric-key authentication protocol with minimum cost:

$Protocol:A\to B:\{N$_A,A}₈₀₇K_AB B→A:{N_A,N_B}₈₂₈K_AB A→B:N_B

In the second case, we consider a slow machine with a fast link, where the cryptographic operations are the bottleneck. In this case, we set the bandwidth cost much lower than the encryption cost in the metric function. Hence, we get the following two optimal symmetric-key protocols.

$Protocol:A\to B:N$_A,A B→A:{N_A,N_B,A}₈₉₀K_AB A→B:N_B

$Protocol:A\to B:N$_A,A B→A:{N_A,N_B,B}₉₅₂K_AB A→B:N_B

It is interesting to notice that the two protocols in the first case use one more encryption than the two protocols in the second case, while the messages are shorter. We can see a clear benefit from automatic protocol generation, since the protocols generated suit the system requirements ideally.

For the asymmetric-key protocol, in both cases, the automatic protocol generation finds the same protocol as the optimal protocol. The resulting protocol is the same as the asymmetric-key protocol listed in the previous subsection.