A method for determining a terminal ID from a message received from a terminal in a communication system avoids sending the terminal ID in the clear. In this system each terminal ID has an associated encryption key. A transmitted message comprises at least a Message Authentication Code (MAC), a n -bit hash, and encrypted message text. At least the terminal key and a nonce is used to generate the MAC, and neither the terminal ID or the terminal key are included in the transmitted message. An authentication broker stores the set of all (terminal ID, terminal key) pairs for the plurality of terminals in the communication system. The set of all terminal keys is grouped into at least two partitions, and on receipt of a message the authentication broker identifies the partition that includes the terminal key of the terminal that transmitted the received message using the n -bit hash (the search partition). The authentication broker then searches the search partition for the terminal key that authenticates the MAC to identify the terminal ID. In some embodiments the nonce is not included in the message but is known or obtainable by the terminal and the authentication broker. A partitioning function generates the «-bit hash from at least the nonce and a terminal key. In some embodiments the nonce is included in the received message and a partitioning function generates the n -bit hash by using the nonce to select n bits from the terminal ID. In some embodiments the partitions are arranged into hierarchical groups such as tree, and each node has a partition key, and the n-bit has is formed as the ordered set of MACs for the partition keys on the path from the root node to the leaf node partition that includes the terminal key.