Information Theoretically Secure Encryption with Almost Free Authentication

Abstract: In cryptology, secure channels enable the exchange of messages in a confidential and authenticated manner. The literature of cryptology is rich with proposals and analysis that address the secure communication over public (insecure) channels. In this work, we propose an informa-tion theoretically secure direction for the construction of secure channels. First, we propose a method of achieving unconditionally secure authentication with half the amount of key material required by traditional unconditionally secure message authentication codes (MACs). Key reduc-tion is achieved by utilizing the special structure of the authenticated encryption system. That is, authentication exploits the secrecy of the message to reduce the key material required for authen-tication. After the description of our method, since key material is the most important concern in unconditionally secure authentication, given the message is encrypted with a perfectly secret one-time pad cipher, we extend our method to achieve unconditionally secure authentication with almost free key material. That is, we propose a method for unconditionally authenticating arbi-trarily long messages with much shorter keys. Finally, we will show how the special structure of the authenticated encryption systems can be exploited to achieve provably secure authentication that is very efficient for the authentication of short messages