Paper 2015/250
Design and Analysis of InformationTheoretically Secure Authentication Codes with NonUniformly Random Keys
Junji Shikata
Abstract
The authentication code (Acode) is the one of the most fundamental cryptographic protocols in informationtheoretic cryptography, and it provides informationtheoretic integrity or authenticity, i.e., preventing information from being altered or substituted by the adversary having unbounded computational powers. In addition, it has a wide range of applications such as multiparty computations and quantum key distribution protocols. The traditional Acode theory states that a good Acode is characterized as an Acode which satisfies equality of a lower bound on size of secretkeys, i.e., an Acode satisfying K=\epsilon^{2}, where K} is cardinality of the set of secretkeys and \epsilon is the success probability of attacks of the adversary. However, good Acodes imply that secretkeys must be uniformly distributed. Therefore, if a nonuniformly random key is given, we cannot realize a good Acode by using it as a secretkey. Then, a natural question about this is: what is a good Acode having nonuniformly random keys? And, how can we design such a good Acode having nonuniformly random keys? To answer the questions, in this paper, we perform analysis of Acodes having nonuniformly random keys, and show the principle that guides the design for such good Acodes. Specifically, the contribution of this paper is as follows. We first derive a new lower bound on entropy of secretkeys, and it is described in terms of \R entropy. Next, we define that a good Acode having nonuniformly random keys is the one satisfying equality of the bound, and it is characterized by the minentropy (a special case of \R entropy). Furthermore, we introduce the classification methodology for Acodes which are realizable from a biased keysource. This classification is performed by using a mathematical tool, i.e., a group action on the set of authentication matrices. By this analysis, we can understand what kind of Acodes is actually constructable. Finally, we design how to construct good Acodes having 1bit messages from von Neumann sources. We also show that our construction methodology is superior to the one by applying von Neumann extractors and the traditional optimal Acode constructions. Although the case of 1bit messages may be restricted, however, this case is simple and we believe that a general case will develop from this simple case.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 authentication codesinformation theoretic securitynonuniformly random keys
 Contact author(s)
 shikata @ ynu ac jp
 History
 20150319: received
 Short URL
 https://ia.cr/2015/250
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/250, author = {Junji Shikata}, title = {Design and Analysis of InformationTheoretically Secure Authentication Codes with NonUniformly Random Keys}, howpublished = {Cryptology ePrint Archive, Paper 2015/250}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/250}}, url = {https://eprint.iacr.org/2015/250} }