Efficient Keyless Authentication for Communication in Unsecured Environments



In scenarios where users wish to ensure reliable communication over an unsecured channel, the ability to reliably detect the presence of a malicious adversary can be of high value. This problem, known as authentication, is a relaxation of the more general arbitrarily varying channel (AVC): in both settings, the channel takes as inputs both a legitimate transmission and an adversarial state. The adversary maliciously chooses a state with the goal of causing a decoding error at the receiver. Over the AVC, the receiver then attempts to recover the legitimate transmission in spite of the adversary's interference.


A plethora of variations on the AVC appear in the literature, in which the adversary has varying degrees of power and knowledge of the legitimate transmission, and the sender and receiver may or may not have access to a shared key. In the authentication setting, the receiver also succeeds if the presence of adversarial interference is detected. That is, if no adversary is present, the receiver must decode the intended message correctly; otherwise, the receiver must either decode correctly or detect the adversary.


Under the AVC, traditional approaches to authentication for communication systems are not able to operate at the highest speeds. The difficulty in realizing practical implementations is a key barrier, as is the reliance upon pre-shared secrets. Any system that uses a shared secret requires a solution for key distribution and management in order to maintain the integrity of the authentication protocol. Key distribution and management solutions are not easily deployed in many situations.


Invention Description

Researchers at Arizona State University have developed a structured coding scheme for keyless authentication over a discrete memoryless binary-input, symmetric adversarial channel. This scheme allows for coding rates up to the non-adversarial capacity of the underlying channel, as well as bounded-complexity decoding.


Two different codewords are used to provide the authentication without requiring any secret keys to be previously shared. A first codeword offers good security without requiring any shared secrets, but is low rate. A second codeword is high rate, but requires a shared secret. The core innovation of the design is its use of the first codeword to transmit a small secret key and the second codeword to transmit the message itself at a high rate.


Potential Applications

•       Sensitive communication requiring authentication

•       Military communications


Benefits and Advantages

•       Low computation cost

•       Bypasses the need for pre-shared secret keys

•       Allows for coding rates up to the non-adversarial capacity of the channel



Related Publication (PDF): Structured Coding for Authentication in the Presence of a Malicious Adversary


Faculty Profile of Professor Oliver Kosut

Case ID:
Last Updated:

For More Information, Contact