The Computer Journal Advance Access originally published online on December 1, 2005
The Computer Journal 2006 49(3):310-321; doi:10.1093/comjnl/bxh149
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
Unconditionally Secure Anonymous Encryption and Group Authentication1
1 National Institute of Advanced Industrial Science and Technology Tokyo, Japan
2 Graduate School of Environment and Information Sciences, Yokohama National University Yokohama, Japan
3 NTT DoCoMo, Inc. Yokosuka, Japan
4 Institute of Industrial Science, The University of Tokyo Tokyo, Japan
*Corresponding author: hanaoka-goichiro{at}aist.go.jp
Anonymous channels or similar techniques that achieve sender's anonymity play important roles in many applications, e.g. electronic voting. However, they will be meaningless if cryptographic primitives containing sender's identity are carelessly used during the transmission. In computationally secure settings, this problem may be easily overcome by using public key encryption and group signatures. However, in an unconditionally secure setting, in which no computational difficulty is assumed, this is not an easy case as such. As the increasing computational power approaches the point where security policy can no longer assume the difficulty of solving factoring or discrete logarithm problems, it must shift its focus to assuring the solvency of unconditionally secure schemes that provide long-term security. The main contribution of this paper is to study the security primitives for the above problem. In this paper, we first define the unconditionally secure asymmetric encryption scheme, which is an encryption scheme with unconditional security and where it is impossible for a receiver to deduce the identity of a sender from the encrypted message. We also investigate tight lower bounds on required memory sizes from an information theoretic viewpoint and show an optimal construction based on polynomials. It is remarkable to see that these bounds are considerably different from those in Shannon's model of the conventional unconditionally secure symmetric encryption. Other than the polynomial-based scheme, we also show a construction based on combinatorial theory, a non-malleable scheme and a multi-receiver scheme. Then, we define and formalize the group authentication code (GA-code), which is an unconditionally secure authentication code with anonymity like group signatures. In this scheme, any authenticated user will be able to generate and send an authenticated message while the receiver can verify the legitimacy of the message—that it has been sent from a legitimate user but at the same time retains his anonymity. However, by cooperating with the group authority, such as in the case of disputes, the receiver is able to obtain information of the user's identity. For GA-code, we show two concrete constructions.