Information-theoretically Secure Key Agreement over Partially Corrupted Channels
This addresses a fundamental cryptographic challenge for secure communication in scenarios with partial adversarial control, representing an incremental advance over prior impossibility results.
The paper tackles the problem of secure key agreement when an adversary partially controls the communication channel, showing that secret key agreement is possible as long as some symbols remain private and unchanged, with derived bounds and constructions achieving these bounds.
Key agreement is a fundamental cryptographic primitive. It has been proved that key agreement protocols with security against computationally unbounded adversaries cannot exist in a setting where Alice and Bob do not have dependent variables and communication between them is fully public, or fully controlled by the adversary. In this paper we consider this problem when the adversary can "partially" control the channel. We motivate these adversaries by considering adversarial corruptions at the physical layer of communication, give a definition of adversaries that can "partially" eavesdrop and "partially" corrupt the communication. We formalize security and reliability of key agreement protocols, derive bounds on the rate of key agreement, and give constructions that achieve the bound. Our results show that it is possible to have secret key agreement as long as some of the communicated symbols remain private and unchanged by the adversary. We relate our results to the previous known results, and discuss future work.