In a two party mutual-authentication protocol, should I have

O(N^2) CPU + O(N^2) communication and if one side doesn’t trust the other neither learns anything or,

O(N^2) CPU + O(1) communication and if one side doesn’t trust the other they may still learn that the other side trusts them?