In one way to improve the security of bilateral authentication procedures while keeping transmission overhead to a minimum, a first party wishing to initiate communications with a second party generates a random number having a first number of digits. The first party the enciphers the random number using a secret ciphering key to obtain an enciphered version of the random number that has a second number of digits greater or equal to the first number. A third number of selected digits of the enciphered random number are then transmitted to the second party, where the third number is less than the first number. The second party receives the digits transmitted from the first party and expands the third number of digits in a pre-agreed manner to obtain the second number of digits. The second party then deciphers the second number digits using the second party's secret key to obtain the first number of digits, which is not equal to the original random number chosen by the first party. The so-obtained first number of digits is then used by the second party as a ciphering key to encipher the second party's secret key thereby obtaining an enciphered key containing the second number of digits. A fourth number of digits less than the second number are then selected by the second party and transmitted to the first party. The first party also expands the third number of digits it transmitted to the first party in the same pre-agreed manner to obtain the second number of digits and then deciphers this so-obtained second number of digits using its secret key to obtain a first number of digits once more. The first party then selects from these a fourth number of digits less than the second number in the same manner as the second party, and compares the selected fourth number of selected digits with the fourth number of digits received from the second party. If a match is detected, the first party has verified that the second party possesses the same secret key as itself. The roles may be reversed to allow the second party to verify the identity of the first party, either by repeating the above procedure starting with a new random number chosen by the second party, or else continuing to derive a number of digits to be returned from the first party to the second party based on the digits received from the second party and the first party's secret key.