The Computer Journal

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

This Article Abstract FREE Full Text (PDF) All Versions of this Article: 49/3/310    most recent bxh149v1 Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Hanaoka, G. Articles by Imai, H. Search for Related Content Social Bookmarking          What's this?

© The Author 2005. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Unconditionally Secure Anonymous Encryption and Group Authentication¹

Goichiro Hanaoka^1,*, Junji Shikata², Yumiko Hanaoka³ and Hideki Imai⁴

¹ National Institute of Advanced Industrial Science and Technology Tokyo, Japan
² Graduate School of Environment and Information Sciences, Yokohama National University Yokohama, Japan
³ NTT DoCoMo, Inc. Yokosuka, Japan
⁴ Institute of Industrial Science, The University of Tokyo Tokyo, Japan

^*Corresponding author: hanaoka-goichiro{at}aist.go.jp

Received 28 July 2005; revised 30 September 2005

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.

	1. INTRODUCTION

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
In many applications, there is a need to allow user or the author of the message to be able to transmit messages without revealing his/her identity, e.g. electronic voting. A most commonly used cryptographic technique that is used to build an actual implementation of these characters, is called anonymous channels [1,2,3]. However, if not carefully designed, i.e. when a sender uses encryption and authentication methods requiring the sender's identity for decryption or message verification, these systems can be easily compromised, thus corrupting results or violating senders' privacy. For example, if Diffie–Hellman key exchange (with certificates) [4] or (conventional) digital signatures are used, the receiver will be able to easily obtain information regarding the sender's identity, and also may leave the message contents along with the identity of the sender open to perusal. In a computationally secure setting, this problem can be solved straightforwardly by using (conventional) public-key encryption e.g. [5,6] and group signatures [7,8] shielding the sender's identity. These schemes and the infrastructure within which they operate are restricted in scope in that they rely for their security on the assumed computational difficulty of computing certain number-theoretic problems, such as factoring large composites or solving discrete logarithms in large finite fields. However, this presumption no longer assures the security of computationally secure schemes as the progress in computers as well as further refinement of various algorithms in near future make it computationally able to solve the larger size number-theoretic problems. Unfortunately, in unconditionally secure environments, where no computational difficulty is assumed, there is yet no straightforward answer to this; all of the current existing schemes use mutual information between sender and receiver, and this mutual information is utilized as a shared communication key between them. This implies that the receiver has to know certain information regarding the sender prior to selecting a shared secret, and this means loss of anonymity. (This also implies that an unconditionally secure public-key encryption scheme is essentially non-existent, since in the model of public-key cryptosystems, a sender and a receiver do not share mutual information between them.) As the increasing computational power approaches the point where security policy can no longer assume on the difficulty of computationally hard problems, it must shift its focus to assuring the solvency of unconditionally secure schemes that provides long-term security. A similar problem arises in authentication as well. In conventional authentication schemes, the identity of the sender is required for verifying integrity of a transmitted message. In order to protect the sender's privacy in a computationally secure setting, group signatures [7, 8] were proposed and since then, group signature schemes have been greatly studied in the literature. However, in an unconditional setting, there has never existed an authentication scheme that assures anonymity of the sender like that seen in the group signature schemes. For the importance of preparing for the eventual need of long-term security, an unconditionally secure setting must be considered a sine qua non for a security policy. The main contribution of this paper is to study models, bounds and constructions of novel security primitives on the above problem with no computational assumption. In this paper, we first define the unconditionally secure asymmetric encryption (USAE) scheme, which is an encryption scheme with unconditional security in which a receiver cannot obtain any information of the identity of a sender from the encrypted message. We also investigate tight lower bounds on required memory sizes from information theory and also show concrete constructions of USAE schemes based on polynomials and cover free family (CFF) [9]. A USAE based on polynomials is optimal because it matches the lower bounds. We further show another construction from combinatorial theory, a non-malleable scheme and a multi-receiver scheme. We then define and formalize the group authentication code (GA-code), which is an unconditionally secure authentication code (A-code) with anonymity like group signatures. In this proposed scheme, any authenticated user will be able to generate an authenticated message and send it to the receiver. The receiver is then able to verify the authenticity of the received message while maintaining the privacy of the user. Moreover, neither a recipient nor a group authority can obtain any meaningful information of the user who had generated the authenticated message, i.e. no one can link any message to the author who sent it. However, by cooperating with group authority, such as in the case of disputes, the receiver is able to obtain the sender's identity.

1.1. Related works
Unconditionally secure key distribution schemes. For confidentiality without computational assumptions, unconditionally secure key distribution schemes are often utilized as suitable security primitives. Blom [10] made the first attempt to construct an unconditionally secure key distribution scheme using MDS linear codes. His idea was later generalized by Matsumoto and Imai [11], viz. key predistribution schemes (KPS); they also proposed a simpler version of KPS, the linear scheme. Blundo et al. [12] proposed a concrete construction of KPS for conference key distribution and investigated lower bounds on required memory size for users and showed that their scheme, as well as Blom's original scheme and Matsumoto–Imai's scheme, all matched the lower bounds. Blundo et al. [13], as well as Kurosawa et al.[14] showed other interesting bounds on required memory sizes. In [15], an in-depth survey of various constructions of KPS has been carried out and corresponding properties have been investigated. KPS may seem to be the best building blocks for unconditionally secure communication systems; however, they are not suitable for certain applications e.g. electronic voting systems, which must ensure user's anonymity; the identity of a sender is required for a recipient to generate the communication key. In all of the existing KPS hitherto, a sender and a receiver's secret information must be used to generate the communication key, and therefore, all of the currently existing schemes do not meet the security requirements for a system with anonymity. As far as we know, there has never existed an unconditionally secure key distribution scheme without a requirement of sender's identity.

Unconditionally secure authentication schemes and group signatures. For a secure authentication without computational assumptions, unconditionally secure A-codes [16, 17] may be considered which have been intensively studied in the literature. An overall structure of A-codes is as follows. In the first stage of A-codes, a trusted authority generates secret information for each of sender and receiver. Then, the sender generates an authenticated message using his given secret information and transmits it to the receiver. Finally, the receiver verifies the validity of the authenticated message with his secret information. Here, no adversary succeeds in impersonation or substitution attack even if the adversary has unlimited computational power. There have also been many attempts to modify A-codes with the aim of enhancing the codes with desirable properties other than anonymity, such as asymmetricity [18] and multireceiver-authenticity [19]. However, in none of these attempted modifications, receivers were able to identify the sender of the message. Thus, there were no existing A-codes and their variants that were applicable concerning the protection of the sender's identity, i.e. no anonymity. Though there are some unconditionally secure digital signature schemes [20, 21, 22] that do exist, these schemes yet too, do not provide anonymity. However, in computationally secure settings, anonymity can be achieved by using group signatures [7, 8]. For a group signature, a user is able to prove that he is a legitimate user of the group by using the secret information given to him by a group authority; in the case of a dispute, the group authority can identify the user from a published signature signed by the user. Group signature is therefore a suitable authenticating scheme that can be used especially in cases where the privacy of the user has to be maintained. However, all the existing group signature schemes are based on computational assumptions and will be broken if certain computationally hard problems, e.g. discrete logarithm or factoring, are solved.

1.2. Our results
We start this paper by defining USAE with formal definitions. USAE is an encryption scheme with unconditional security in which a receiver cannot gain any information of a particular user from an encrypted message. We investigate from information theory, the lower bounds for the required memory sizes of a ciphertext, a sender and a receiver's secrets. Further, we propose concrete constructions of USAE based on polynomials and also constructions based on CFFs. Polynomial-based construction is optimal because it matches the lower bounds which in turn implies that the lower bounds are all tight. One important fact that bears mention: it is quite remarkable to see that these bounds that we have shown are significantly different from those shown in Shannon's model of conventional unconditionally secure symmetric encryption. For example, in our model, required memory sizes for ciphertext, encryption key and decryption key are at least log₂|M| + log₂|S| bits, log₂|M| + log₂|S| bits and (k + 1) log₂|M| bits respectively, where M is the message space, S is the set of all senders and k is the maximum number of dishonest senders. Comparisons between polynomial-based and CFF-based schemes are also made. In addition, we study an extension of USAE, that with non-malleability. More precisely, a formal definition of non-malleability, a concrete non-malleable scheme and a security proof are investigated. Furthermore, another extension of USAE, for multiple-receiver setting, is shown. We continue by defining the GA-code with formal definitions. GA-code is an unconditionally secure A-code with anonymity like group signatures. In GA-codes, any user in a group can generate an authenticated message and verify it as long as it has been sent from a legitimate user in a group. Moreover, a receiver is not able to obtain any meaningful information of a particular user who had generated the authenticated message. However, in the case of disputes, a receiver is able to obtain the sender's identity by cooperating with a group authority. It is important to note here that the group authority or the receiver by itself will be insufficient to obtain any information regarding the user i.e. they must cooperate with each other. We then show two concrete constructions of GA-code with formal security proofs. One construction is based on polynomials and the other on CFFs and A-codes. Organization of this paper is as follows: in Section 2, we study the model, bounds and constructions for USAE. Polynomial-based USAE construction is optimal because it matches the lower bounds. This in turn implies that the lower bounds are all tight. We also show other efficient and secure implementations of USAE. In Section 3, we show model and concrete construction for GA-code with formal security proof.

	2. UNCONDITIONALLY SECURE ASYMMETRIC ENCRYPTION

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
In this section, model, security definition, lower bounds and concrete constructions of USAE are shown. One of our constructions is optimal in terms of required memory sizes for a ciphertext, an encryption key and a decryption key. It should be noted that the definition that we use for ‘asymmetric encryption’ in this paper is not equivalent to the meaning of ‘public-key encryption’ in a general sense. Here, in USAE, ‘asymmetric’ is used as a pair of encryption and decryption keys that are asymmetric, and where an encryption key is not public.

2.1. Model
Since no computational difficulty is assumed in USAE, it is impossible for a sender to secretly transmit a message using only the public information. This means that in order to construct a USAE, a different assumption (rather than computational assumptions) will be required, e.g. existence of a noisy channel, that of a quantum channel, bounds of memory or threshold of the number of malicious users. For simplicity, we introduce the trusted initializer model (R. Rivest, unpublished data) in which we assume a trusted initializer who honestly distributes each user's secret in the initial phase and deletes his memory after the distribution of the secrets. We should note that the trusted initializer can be removed by using multi-party computation [23] if the number of malicious users is less than a third of the total number of users and there exists a private channel between each pair of users.

In the model of USAE, there are n + 2 participants, a set of n senders {S₁,...,S_n}, a receiver R and a trusted initializer TI. TI generates encryption keys e₁,...,e_n for S₁,...,S_n respectively, and a decryption key d for R. After distributing these keys, TI deletes his memory. In order to send a plaintext m to R with confidentiality, s{S₁,...,S_n} encrypts m by using e_i and transmits a ciphertext c to R. R decrypts c by using d and recovers m.

2.2. Definition
Here, we formally define the security of USAE. It should be noted that, in addition to confidentiality, anonymity of a sender is also required for USAE.

Let , _i (i = 1,...,n), , and denote the random variables induced by s, e_i (i = 1,...,n), d, m and c respectively. For a random variable , H() denotes the entropy of . For , let X {x|Pr( = x) > 0}. |X| denotes the cardinality of X. We assume that at most k(0 k n – 1) authorized senders are malicious. Then, the security of USAE is formally defined as follows:

DEFINITION 1
We say that (₁,...,_n, , , ) is a (k,n)-one-time USAE if

1. R can correctly decrypt m from c, that is, H(|,) = 0.
   
2. Any set of k malicious senders has no information on m from c. Namely, for any set of k malicious senders such that , .
   
3. R obtains no information on the identity of s from c; viz. H(|) = H().
   
4. Additionally, we assume that a ciphertext c is uniquely determined from a plaintext m and an encryption key e_i, i.e. H(|,_i) = 0 for any i.
   

2.3. Lower bounds
In this subsection, lower bounds on required memory sizes for a ciphertext, an encryption key and a decryption key in USAE are shown. These bounds are all tight since we also show a construction which matches them (see Section 2.4, for details).

We begin by showing a lower bound on the required memory size for a ciphertext.

THEOREM 1. In a (k,n)-one-time USAE, H()H() + H().

Proof. Let C_i (1 i n) be sets of all possible ciphertexts generated by e_i (1 i n) respectively. First, we show C_i C_j = (i j) for all i,j(1i n, 1 j n). Suppose that c_i C_i, c_j C_j, c_i = c_j and that m_i, m_jM are plaintexts of c_i and c_j respectively. Here, it should be noted that the receiver R can utilize only c_i(=c_j) and d, and that R has no information on which of e_i and e_j was used to generate the ciphertext. This is because of what was stated in the third condition of Definition 1. Also, due to the first condition of Definition 1, we have m_i = m_j. This implies that S_j can recover m_i from c_i when S_j can generate c_j such that c_j = c_i. However, due to the second condition of Definition 1, S_j cannot decrypt a ciphertext that he cannot generate. This is a contradiction. Therefore, C_i C_j = (i j) for all i,j (1 i n, 1 j n). Then, we have

(1)

From the first and the fourth conditions of Definition 1, a mapping _i : C_i M, such that for any c C_i, _i(c)M is the corresponding plaintext of c, is bijective, for any i (1 i n). Therefore, Equation (1) becomes

which proves the theorem.

Theorem 1 implies that the required memory size for a ciphertext is always larger than that for a plaintext by at least H() bits.

Next is a lemma that shows the relationship between the required memory size for an encryption key e_i and for a ciphertext c in USAE.

LEMMA 2.1
In a (k,n)-one-time USAE, H(_i)H(), for any i.

Proof. From the second condition of Definition 1, we have

(2)

And, it is obvious that

(3)

Then, from the fourth condition of Definition 1, Equations (2) and (3), we have

which proves the theorem.

Lemma 2.1 implies that the memory size requirement for an encryption key in USAE is equal to or greater than that for a ciphertext. This is also closely related to the famous Shannon's result [24]. That is, in unconditionally secure symmetric encryption, it is a well-known fact that the required memory size for an encryption key is equal to or greater than that for a plaintext, assuming that a ciphertext is uniquely determined from a plaintext and an encryption key.

Now, a lower bound on the required memory size for an encryption key is shown.

THEOREM 2
In a (k,n)-one-time USAE, H(_i)H() + H(), for any i.

Proof. From Lemma 2.1 and Theorem 1, we have H(_i) H() + H() for any i.

Theorem 2 implies that the required memory size for an encryption key is always larger than that for a plaintext by at least H() bits.

Finally, we show a lower bound on the required memory size for a decryption key.

THEOREM 3
In a (k,n)-one-time USAE, H() (k + 1)H() if the equality in Lemma 2.1 is satisfied for any i.

Proof. Let C_i (1 i n) be the set of all possible ciphertexts generated by e_i (1 i n) respectively, and (1 i n) be random variables in C_i (1 i n). We note that Pr() = Pr( = S_i) Pr( = c|e_i). For any set of k + 1 encryption keys , we have

(4)

This is due to the second condition of Definition 1 and Lemma 2.2. Then, from Equations (4),

(5)

Since H(_i|,) = 0 for any i if H(_i) = H(), we have

(6)

Therefore, from Equations (5) and (6),

which proves the theorem.

LEMMA 2.2
Let C_i (1 i n) be the set of all possible ciphertexts generated by e_i (1 i n) respectively, and (1 i n) be random variables in C_i. Then, H(_i | ) H() for any i.

Proof. In general, we have

(7)

From the first and second conditions of Definition 1, H(|) = H() and H(|_i, ) = 0. Therefore, Equation (7) becomes H(_i|) H().

Theorem 3 implies that the required memory size for a decryption key is (k + 1) times larger than that for a plaintext.

2.4. Constructions
Now, we show two concrete constructions of USAE. One of the constructions is based on polynomials over finite fields, and the other one on CFF [9]. The polynomial-based construction is optimal in terms of required memory sizes for a ciphertext, an encryption key and a decryption key. For the CFF construction, security parameters can be flexibly determined.

In this subsection, we assume that the distribution of the sender is uniform, that is, Pr( = S_i) = 1/n for any i (1 i n).

2.4.1. Optimal construction from polynomial
Here, we show an optimal (k,n)-one-time USAE which meets all our bounds. This means that the lower bounds in the previous subsection are all tight.

DEFINITION 2
A (k,n)-one-time USAE is optimal if one has equalities in Theorems 1, 2 and 3.

Optimal (k,n)-one-time USAE based on polynomials

1. Setting up. Let |M| = q, where q is a prime power and q n. TI chooses a uniformly random polynomial over GF(q). TI also chooses distinct numbers b_i (1 i n) from a set BGF(q) uniformly at random, where |B|=n. B may be public to all players. Next, TI gives f(x) to R as his decryption key, and also gives {b₁,f(b₁)}, {b₂,f(b₂)},...,{b_n,f(b_n)} to S₁,S₂,...,S_n as encryption keys respectively. TI deletes his memory after distributing the keys.
   
2. Encryption. Sender S_i encrypts m by c={b_i, c'}, where c':=f(b_i) + m.
   
3. Decryption. Receiver R decrypts c by f(x) as follows: .
   

THEOREM 4
The above scheme is an optimal (k,n)-one-time USAE.

Proof. In the above scheme, H() = H() + log₂ n, H(_i) = H() + log₂ n (1 i n) and H() = (k + 1)H(). It is clear that the above scheme satisfies the first condition of Definition 1. Suppose that colluders , such that , can obtain certain information on m from c. This implies that the colluders have certain information on f(b_i). However, this is impossible because deg f(x) = k and the colluders know only the k points of f(x). Hence, the above scheme satisfies the second condition of Definition 1. Finally, since, for a ciphertext c = {b,c'} such that bB and c'=f(b) + m, any of S₁,...,S_n can be a possible sender of the ciphertext from R's point of view, and therefore, R can determine who the sender of the ciphertext is with probability at most 1/n. Hence, the above scheme satisfies the third condition of Definition 1 as well.

2.4.2. Construction from CFF
Here, we show a construction of USAE based on CFF [9] which allows a more flexible parameter setting than the polynomial-based one, viz. in CFF-based construction, it is possible to choose parameters n and |M| with |M| < n, while, in polynomial-based construction, these two parameters must always be determined to be |M| n.

DEFINITION 3
Let L {₁,₂,...,_t} and F={F₁,...,F_n} be a family of subsets of L. We call (L,F) an (n,t,k) CFF if F₀ F₁ ... F_k for all F₀, F₁,...,F_kF, where F_iF_j if ij.

A trivial CFF is the family consisting of single-element subsets, in which case n=t. It should also be noted that there exist non-trivial constructions of CFF with n>t. Construction of CFFs is intensively studied in various areas of mathematics such as finite geometry, design theory and probability theory. Concrete methods for generating CFFs are given in [25].

(k,n)-one-time USAE based on (n,t,k)-CFF

1. Setting up. TI first generates an (n,t,k)-CFF such that each of _i (1 i t) is an element of GF(q), where =GF(q). TI also chooses distinct numbers r_i (1i n) from {1,2,...,n} uniformly at random. An algorithm that generates F_i (1 i n) from i and L may be public to all players. Next, TI gives L to R as his decryption key. TI also gives {r_i, ⁽ⁱ⁾} (1 i n) to S_i (1 i n) respectively, as encryption keys, where . After distributing the keys, TI deletes his memory.
   
2. Encryption. Sender S_i encrypts m by c={r_i,c'}, where c' = m + ⁽ⁱ⁾.
   
3. Decryption. Receiver R generates from L and r_i. Then, R computes m as .
   

THEOREM 5
The above scheme is a (k,n)-one-time USAE.

Proof. It is obvious that the above scheme satisfies all conditions in Definition 1.

The required memory sizes for the above construction are formally addressed as follows:

THEOREM 6
The required memory sizes in the above construction are given as follows:

It should be noted that the CFF-based construction matches the lower bounds on the required memory sizes for a ciphertext and an encryption key.

2.5. Comparison
In this subsection, comparison between polynomial- and CFF-based constructions is explored. Given the above fact, our polynomial construction is optimal in terms of required memory sizes. Therefore, the polynomial-based construction is theoretically superior to the CFF-based construction storage-wise. However, polynomial-based constructions can only be implemented when |M| n although, in most practical situations, this restriction may be ignored. On the other hand, for the CFF-based construction, it allows even for |M| <n when there exists an appropriate CFF. We now show an example of system parameter settings in the case where this restriction applies. For the following situation, the CFF-based construction will be more suitable than the polynomial-based construction in terms of required memory sizes.

Example. Assume that the message space is {yes,no} and we need a (127,128)-one-time USAE. For the polynomial-based construction, a finite field GF(q) with q 128 is required. Consequently, the size of a ciphertext will be at least 14 bits. A receiver and a sender must then store at least 896 bits and 14 bits, respectively. For the CFF-based construction, (128,128,127)-CFF (trivial CFF) over GF(2), the size of a ciphertext will be 8 bits at the least, and a receiver and a sender store at least 128 bits and 8 bits respectively. For the described situation, we can see a significant advantage of the CFF-based construction over the polynomial-based construction.

In summary, different constructions are advantageous for different perspectives, so, one construction may do better than another under certain circumstances. However, the polynomial-based construction is generally most suitable for typical security parameter settings in USAE. However, for the case when |M|<n, the CFF-based construction is better.

Memory size requirements can be reduced further for the above example if we utilize non-trivial CFF instead. However, in a non-trivial CFF, the number of malicious senders cannot be set to a considerably larger number than the total number of the senders. This fact is due to the following proposition:

PROPOSITION 1
([25]) In a non-trivial (n,t,k)-CFF with n > t, [k(k – 1)]/2 n.

2.6. Non-malleable scheme
In this subsection, we consider non-malleability [26] of the proposed USAE. Frankly, non-malleability means an adversary's inability i.e. given a challenge ciphertext c, to generate a different ciphertext such that the plaintexts underlying these two ciphertexts are meaningfully related. For computational encryption schemes, formal definitions of non-malleability are given in [27, 28]. Here, we give a definition of non-malleability for USAE.

DEFINITION 4
Let be another ciphertext which could have been generated by s instead of c in USAE, and be a plaintext underlying . Let and denote random variables induced by and respectively. A USAE is perfectly non-malleable if the following equation holds:

(8)

for any set of k malicious senders such that .

The above definition is reasonable since Equation (8) implies that even if an adversary knows a pair of {c,m}, there is no other ciphertext which can give further information except the information that its underlying plaintext is not identical to m. In other words, no adversary can generate a ciphertext whose plaintext is meaningfully related to m when Equation (8) holds.

A USAE which satisfies perfect non-malleability is constructed as follows:

Non-malleable (k,n)-one-time USAE based on polynomials

1. Setting up. Let |M|=q, where q is a prime power and q n. TI chooses a uniformly random polynomial over GF(q). TI also chooses distinct numbers b_i (1 i n) from a set B GF(q) uniformly at random, where |B|=n, such that f₂(b_i) 0 for any i (1 i n). B may be public to all players. Next, TI gives f₁(x) and f₂(x) to R as his decryption key, and also gives {b₁,f₁(b₁),f₂(b₁)},{b₂,f₁(b₂),f₂(b₂)},...,{b_n,f₁(b_n),f₂(b_n)} to S₁,S₂,...,S_n as encryption keys respectively. TI deletes his memory after distributing the keys.
   
2. Encryption. Sender S_i encrypts m by c={b_i,c'}, where c' f₁(b_i) + mf₂(b_i).
   
3. Decryption. Receiver R decrypts c by f₁(x) and f₂(x) as follows: .
   

THEOREM 7
The above scheme is a perfectly non-malleable (k,n)-one-time USAE.

Proof. Similar to the proof of Theorem 4, it can be proved that the above scheme is a (k,n)-one-time USAE. Now, we show that the above scheme satisfies the equality of Equation (8). It is obvious that

(9)

Next, we show that is equivalent to that in Equation (9). Since both deg f₁(x) and deg f₂(x) are k, information on f₁(x) and f₂(x) cannot be obtained even if e₁,...,e_k are used. Then, a set of all possible values for (f₁(x),f₂(x)) becomes {(₁,₂)|c' =₁ + m₂, ₂ 0}. Consequently, for given , a set of all possible plaintext underlying is . From Lemmas 2.3 and 2.4, we have M' = M–{m} and a mapping : M', such that , is bijective. Hence, we have

(10)

From Equations (9) and (10), Equation (8) holds.

LEMMA 2.3
For a given ciphertext c(={b_i,c'})C and its corresponding plaintext mM, let {(₁,₂)|c=₁ + m₂, ₂ 0}. Then, for any , such that , if (₁,₂).

Proof. Suppose that there exist (₁,₂), such that . Then, . Since , this is a contradiction.

LEMMA 2.4
For a given ciphertext c(={b_i, c'})C and its corresponding plaintext mM, let {(₁,₂)|c=₁ + m₂, ₂0}. Then, for any , such that , if (₁₁,₁₂)q(₂₁,₂₂) and (₁₁,₁₂),(₂₁,₂₂).

Proof. Suppose that there exist (₁₁,₁₂),(₂₁,₂₂), such that . Letting , we have . Hence,

(11)

Also, since c'=₁₁ + m₁₂=₂₁ + m₂₂, it is clear that

(12)

From Equations (11) and (12), it is obvious that (₁₁–₂₁)=(₁₂–₂₂)=0 or m'=m. When (₁₁–₂₁)=(₁₂–₂₂)=0, we get (₁₁,₁₂)=(₂₁,₂₂). This is a contradiction. On the other hand, when m'=m, this is also a contradition due to Lemma 2.3

Similar to the above scheme, a non-malleable (k,n)-one-time USAE based on CFF can be constructed and the CFF- based scheme will again be more efficient for |M|<n in terms of required memory size as in the discussion in Section 2.5.

2.7. Multiple-receiver scheme
The model of USAE described in Section 2.1 is built for a single receiver. That is, there exists only one receiver for the entire model. From this, we can extend the model to be a multiple receiver model, which is called USAE with multiple receivers (MUSAE), and we show a concrete construction of MUSAE.

Model. In the model of extended MUSAE, there are n₁ + n₂ + 1 participants, a set of n₁ senders , a set of receivers and a trusted initializer, TI. TI generates encryption keys respectively for each , and similarly, the decryption keys are generated respectively for each . To send a plaintext m to R_i(1 i n₂) with confidentiality, S_j (1 j n₁) encrypts m by using e_j and transmits the ciphertext c to R_i. R_i decrypts c by using d_i which will recover m. In the multiple-receiver model, a sender may also be a receiver, concurrently.

Construction. (k₁, k₂,n₁,n₂)-one-time MUSAE can be defined in like manner to (k,n)-one-time USAE: let k₁, k₂, n₁ and n₂ be the number of malicious senders, malicious receivers, total number of senders, total number of receivers respectively. A trivial construction of (k₁,k₂,n₁,n₂)-one-time MUSAE uses n₂ different (k₁,n₁)-one-time USAEs simultaneously. In a MUSAE construction, an encryption key size of a sender becomes approximately n₂ times larger than that of the encryption key size of a sender in a (k₁,n₁)-one-time USAE. A more efficient construction based on polynomials when the encryption key size is significantly reduced to the trivial construction will be discussed next.

Let |M| = q, where q is a prime and q max (n₁,n₂). TI chooses a uniformly random bivariate polynomial over GF(q). TI also chooses distinct numbers b_i (1 i n₁) from a set B GF(q) uniformly at random, where |B| = n. B may be public to all players. Next, TI gives to respectively, as decryption keys, assuming that each receiver's identity can be expressed by an element in GF(q). TI also gives {b₁,f(b₁,y)},{b₂,f(b₂,y)},..., to respectively, as encryption keys. TI deletes his memory after distributing all the keys. When S_i wants to transmit message m to R_j, S_i encrypts m by {b_i,f(b_i,y)} as follows: c={b_i, c'}, where c'f(b_i,R_j) + m. R recovers m by .

In the above construction, a sender must store at least (k₂ + 1) log₂q + log₂ n₁ bits while in the trivial construction, (n₂ + 1) log₂q + log₂n₁ bits at least, are needed to be stored. Hence, we can say that the reduction made in the required memory size for an encryption key is considerable.

	3. GROUP AUTHENTICATION CODE

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
In this section, we show a model, security definition and a concrete construction of GA-code, which is an unconditionally secure A-code code with anonymity like group signatures. With the combination of USAE and GA-code, a secure communication system, which assures confidentiality, authenticity, and user's anonymity can be constructed without any computational assumptions.

3.1. Model
Similar to what we saw in the model of USAE, we introduce the trusted initializer model for the GA-code as well. In the GA-code model, there are n + 3 participants: a set of n senders {S₁,...,S_n}, a receiver R, a group authority G and a trusted initializer, TI. TI generates secret information u₁,...,u_n for S₁,...,S_n respectively, and secret information v for R. TI also generates secret information w for G. After distributing these keys, TI deletes his memory. In order to send a plaintext m to R with authenticity, s{S₁,...,S_n} generates an authenticated message from m by using u_i and transmits to R. R verifies the validity of by using m and v. In a situation where R wants to reveal the identity of the sender, R can obtain it by cooperating with G only if G approves R's request.

3.2. Definition
Here, we formally define the security of the GA-code. In GA-code, a sender is able to prove that he is a legitimate member of a group, {S₁,...,S_n}. In addition, by cooperating with G, R can obtain the identity of the sender fairly simply. However, each of R and G alone, cannot reveal the sender's identity.

An adversary can perform impersonation or substitution by constructing a fraudulent code-word. The attack is considered successful if the receiver accepts the code-word. In impersonation, an adversary is assumed to not have seen any prior communication, while in substitution, the adversary have seen at least one transmitted code-word. Both impersonation and substitution can be performed by either senders or outsiders, where none of TI, G, R, S₁,...,S_n is included in the collusion of the outsiders. Also, senders' attack is considered to be successful if a fraudulent code-word is accepted by the receiver and no fraudulent message is traced back by the receiver and a group authority to the malicious sender who wrote the message. Outsiders' attack is considered successful if the receiver accepts the fraudulent code-word. Note that, a mixed collusion attack delivered together by senders and outsiders is referred to as an attack made only by senders.

Let , (i=1,...,n), ,, and denote the random variables induced by s,u_i (i=1,...,n),v,w,m and respectively. For , let X {x|Pr( = x)>0}. |X| denotes the cardinality of X.

We assume that at most k (0 k n –1) authorized senders are malicious. Then, the security of GA-code is formally defined as follows:

DEFINITION 5
We say that (,...,, ,, ,) is a (p,k,n)-one-time GA-code if:

1. Any set of k malicious senders can perform impersonation with probability at most p, viz. for any set of k malicious senders ,
   

   
   

2. Any outsider can perform impersonation with probability at most p, i.e. maxPr(R accepts ) p.
   
3. Any set of k malicious senders can perform substitution with probability at most p, viz. letting , for any set of k malicious senders such that ,
   

   
   

   where ' is taken over the set of valid authenticated messages which can be generated by .
   

4. Any set of outsiders can perform substitution with probability at most p, i.e. letting ' be an authenticated message which is generated by an honest user, Pr(R accepts|') p.
   
5. R obtains no information on the identity of s from , viz. Pr( = S_i | ,v) = Pr( = S_i) for any and i (1 i n).
   
6. G obtains no information on the identity of s from , viz. Pr(=S_i|,w)=Pr( = S_i) for any and i (1 i n).
   
7. Cooperating with G, R can reveal the identity of the sender of the authenticated message with probability more than , where is the sender of .
   

3.3. Construction
In this subsection, we show a couple of constructions of GA-codes; one is based on polynomials and the other based on CFFs.

3.3.1. Construction from polynomial
Based on polynomials, a GA-code can be constructed as follows:

GA-code based on polynomials

1. Setting up. Let M=GF(q)–{0}, where q is a prime power and q n. TI chooses uniformly random polynomials f(x) and g(x) over GF(q) such that deg f(x) k + 1 and deg g(x) k + 1. TI also chooses distinct numbers b_i (1 i n) from B GF(q) uniformly at random, where |B| = n such that f(b_i) f(b_j) for any i,j with 1i,j n, i j. Next, TI gives f(x) and g(x) to R as v, and also gives {b₁,f(b₁),g(b₁)},{b₂,f(b₂),g(b₂)},...,{b_n, f(b_n),g(b_n)} to S₁,S₂,...,S_n as u₁,u₂,...,u_n respectively. TI also generates a mapping :GF(q) S such that (f(b_i))=S_i and gives it to G as w. TI deletes his memory after distributing keys.
   
2. Message generation. Sender S_i generates an authenticated message for m as ={m,b_i,h}, where hf(b_i)m + g(b_i).
   
3. Verification. Receiver R accepts as valid if h is identical to .
   
4. Tracing. When R wants to reveal the identity of the sender, R first sends a request to G. If R's request is approved by G, R transmits f(b_i) to G via a secure channel. Then, G reveals the sender's identity by S_i=(t) and transmits this result back to R.
   

The security of the above scheme is addressed as follows:

LEMMA 3.1
In the above scheme, colluders, which include at most k of {S₁,S₂,...,S_n}, can perform impersonation with probability at most 1/q. (See conditions (i) and (ii) of Definition 5.)

Proof. For impersonation to succeed by collusion of senders , adversaries need to produce a fraudulent message {b,m',h'} such that h'=f(b)m' + g(b) and . Since the malicious senders have only k points of g(x), it is therefore impossible to obtain any information on g(b), and accordingly, they also have no information on h'. Therefore, the probability of the attack succeeding will be at most 1/q. In a manner similar to this, we can also prove that the probability of outsiders' impersonation succeeding is at most 1/q.

LEMMA 3.2
In the above scheme, colluders, which include at most k of , can perform substitution with probability at most 1/(q–k), where is the honest sender who sends a valid authenticated message ' to R. (See conditions (iii) and (iv) of Definition 5.)

Proof. For substitution by senders to succeed, adversaries need to produce a fraudulent message {b,m',h'} such that h'=f(b)m' + g(b), and , where is an authenticated message generated by .

For the fraudulent message {b,m',h'}, we consider the following cases: (i) and m' m, (ii) and m' = m, (iii) and m' m.

For case (i) and m' m, we have

(13)

Since the adversaries only have , and deg f(x) = k + 1, the only information the adversaries have is . Consequently, there are q – k possible values for f(b). Hence, from Equation (13), there also exist q – k different values for h' for any . This implies that the probability for the substitution succeeding does not exceed 1/(q–k).

For case (ii) and m' = m, we have deg(f(x)m' + g(x)) = k + 1 and the adversaries have only and . Hence, the adversaries have no information on h=f(b)m' + g(b); consequently, the probability for the substitution succeeding also does not exceed 1/q.

For case (iii) and m' m, we have deg g(x) = k + 1 and the adversaries only have and . This means, the adversaries have no information on g(b). Also, this implies that they do not have any information on h' because h'=f(b)m' + g(b); consequently, the probability for substitution to succeed also does not exceed 1/q.

Similarly, we can also prove that the probability of outsiders' substitution succeeding will be at most 1/q.

Together, that any adversaries can succeed in their impersonation or substitution has probability at most 1/(q–k).

LEMMA 3.3
R or G can determine who had generated the authenticated message with probability at most . Additionally, cooperating with G, R can reveal the identity of the sender of the authenticated message with probability 1, if is valid. (See conditions (v)–(vii) of Definition 5.)

Proof. As regards the sender's anonymity, it is clear that R has no information on the identity of the sender since R does not know the mapping . Hence, R can only determine the probability of the generator of the authenticated message to be at most . On the other hand, though G knows , G too, has no information regarding the identity of the sender since G does not know . The probability of G determining the identity of the generator of is at most . However, by cooperating with G, R can identify the sender with probability 1 if is valid.

THEOREM 8
The above scheme is a (1/(q–k),k,n)-one-time GA-code.

Proof. From Lemmas 3.1, 3.2 and 3.3, it is obvious that the above theorem is true.

In the security definition of GA-code, it is assumed that G does not join any colluders who try to perform impersonation or substitution. We should note that the probability of the substitution succeeding can be increased when G joins a collusion attack. Since G knows f(b_i) which is assigned to S_i, for example, he can substitute a valid authenticated message {m,b_i,f(b_i)m + g(b_i)} with a forged message ' {m + 1,b_i, f(b_i)(m + 1) + g(b_i)} which will be accepted by R. If such an attack is to be avoided, we can secure the above scheme with a slight modification as follows: TI uniformly at random chooses two mappings ₁:{1,2,...,n}{1,2,...,n} and ₂ : {1,2,...,n}S such that ₂(₁(b_i))=S_i instead of . Then, {f(x),g(x),₁} and ₂ are given to R and G as v and w respectively.

The required memory sizes for the above construction are formally addressed as follows:

THEOREM 9
The required memory sizes in the above construction are given as follows:

3.3.2. Construction from CFF
Another construction of GA-code is based on CFF. An advantage of using the CFF-based GA-code is recalling USAE, it does not always require |M| + 1 n while the requirement is an absolute for the polynomial-based GA-code.

In order to construct a GA-code from CFF, we also introduce ‘classical’ A-codes [16, 17] which include only one sender and one receiver. In such A-codes, there are three participants: a sender , a receiver and a trusted initializer . generates secret information and for and respectively, such that . In order to send a plaintext to , generates his authenticated message from by using and transmits to . verifies the validity of by using and . We note that or may generate and in order to remove .

DEFINITION 6
Let ,() and denote the random variables induced by ,(,) and respectively. We say that (,(,),) is a p-authentication code (A-code) if

1. Any outsiders (which do not include , or ) can perform impersonation with probability at most p. Namely, Pr( accepts ) p.
   
2. Any set of outsiders can perform substitution with probability at most p, viz. letting be an authenticated message which is generated by , accepts |)p.
   

Construction methods of A-codes are given in, for example, [16, 17]. In the following, for simplicity, let f : denote a mapping such that . Additionally, notations for CFF are the same as that in Definition 3.

GA-code based on CFFs

1. Setting up. Let . TI first generates an (n,t,k)-CFF such that each of _i (1 i t) is an element of . TI also chooses distinct numbers r_i (1 i n) from {1,2,...,n} uniformly at random. An algorithm that generates F_i (1 i n) from i and L may be public to all players. TI further uniformly at random chooses two mappings ₁ : {1,2,...,n}{1,2,...,n} and ₂ : {1,2,...,n}S such that ₂(₁(r_i)) = S_i for 1 i n. Next, TI gives {L,₁} to R as v. TI also gives to S_i (1 i n) respectively, as u_i. In addition, ₂ is given to G as w. After distributing the keys, TI deletes his memory.
   
2. Message generation. Sender S_i generates an authenticated message for m as
   

   where , assuming that .
   

3. Verification. Receiver R first generates from L and r_i. Then, R accepts as valid if is identical to for all .
   
4. Tracing. When R wants to reveal the identity of the sender, R first sends a request to G. If R's request is approved by G, R calculates t=₁(r_i) and transmits it to G. Then, G can now reveal the sender's identity by S_i=₂(t) and transmits this result back to R via a secure channel.
   

THEOREM 10
The above scheme is a (p,k,n)-one-time GA-code.

The proof of the theorem is straightforward.

The required memory sizes for the above construction are formally addressed as follows:

THEOREM 11
The required memory sizes in the above construction are given as follows:

assuming that all are of the same size |F|.

As mentioned so far, we see that the above scheme does not always require |M| + 1 n while the polynomial-based GA-code can be utilized only when |M| + 1 n. In addition, it should be noticed that the size of can be reduced if each of contains the same m.

	4. CONCLUSIONS

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
In this paper, we proposed models and concrete constructions of USAE- and GA-codes which unconditionally secure encryption and have authentication with sender anonymity. By combining the two, USAE- and GA-codes, we can build a secure communication system with confidentiality, authenticity and guarantee sender's anonymity as well. Security of such a system is proven without any computational assumptions and, therefore, assures long-term security. A potential application for such a system is electronic voting. Each voter can send his vote to a ballot-counting server without having to reveal his identity as long as there is an appropriate anonymous channel. What needs to be emphasized for such a system is that it can guarantee security unconditionally, i.e. even against adversaries with extremely high computational power. Dishonest voters, if any exist, can be traced back using the traceability property of the GA-code. As you can see USAE- and GA-codes exhibit their advantage especially for important ‘top-secret’ elections. Moreover, we investigated lower bounds on the required memory sizes for USAE and showed an optimal construction that meets the bounds (i.e. bounds are tight). Furthermore, we gave two extensions of USAE, i.e. a multi-receiver scheme (MUSAE) and a non-malleable scheme. For GA-codes we only showed a single-receiver model, but a multiple-receiver extension can be done similarly as in MUSAE for GA-code. A concrete construction will be shown in our future work. Investigating the tight bounds for the memory sizes in GA-code becomes an important issue when analyzing optimality. It is definitely an interesting open problem.

	ACKNOWLEDGEMENTS

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
We would like to thank the anonymous referees for their helpful comments.

	NOTES

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 
¹A preliminary version of this paper was presented at Asiacrypt'02 [Hanaoka, G., Shikata, J., Hanaoka, Y. and Imai, H. (2002) Unconditionally secure anonymous encryption and group authentication. In Proc. ASIACRYPT'02, Queenstown, December 1–5, pp. 81–99. Springer-Verlag, Berlin.].

	REFERENCES

TOP 1. INTRODUCTION 2. UNCONDITIONALLY SECURE... 3. GROUP AUTHENTICATION CODE 4. CONCLUSIONS ACKNOWLEDGEMENTS NOTES REFERENCES

 

[1] Chaum D. (1981) Untraceable electronic mail, return address, and digital pseudonyms. Commun. ACM 24 84–88.[CrossRef]

[2] Chaum D. (1987) The dining cryptographers problem: unconditional sender and recipient untraceability. J. Cryptol. 1((1)) 65–75.

[3] Abe M. (1998) Universally verifiable mix-net with verification work independent of the number of mix-servers. Proc. EUROCRYPT'98May 31–June 4, Espoo Berlin Springer-Verlag pp. 437–447.

[4] Diffie W. and Hellman M. E. (1976) New directions in cryptography. IEEE Trans. Inform. Theor. IT-22 644–654.[CrossRef]

[5] Rivest R., Shamir A., Adleman L. (1978) A method for obtaining digital signature and public-key cryptosystems. Commun. ACM 21((2)) 120–126.[CrossRef]

[6] ElGamal T. (1985) A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theor. IT-31((4)) 469–472.[CrossRef]

[7] Chaum D. and van Heyst E. (1991) Group signatures. Proc. EUROCRYPT'91April 8–11, Brighton Berlin Springer-Verlag pp. 257–265.

[8] Camenisch J. and Stadler M. (1997) Efficient group signature schemes for large groups. Proc. CRYPTO'97August 17–21, Santa Barbara, CA Berlin Springer-Verlag pp. 410–424.

[9] Erdös P., Frankl P., Furedi Z. (1982) Families of finite sets in which no sets is covered by the union of two others. J. Combin. Theor. Ser. A 33 158–166.[CrossRef]

[10] Blom R. (1983) Non-public key distribution. Proc. CRYPTO'82August, Santa Barbara, CA New York Plenum pp. 231–236.

[11] Matsumoto T. and Imai H. (1988) On the Key Predistribution System: a practical solution to the key distribution problem. Proc. CRYPTO'87August 16–20, Santa Barbara, CA Berlin Springer-Verlag pp. 185–193.

[12] Blundo C., De Santis A., Herzberg A., Kutten S., Vaccaro U., Yung M. (1993) Perfectly secure key distribution for dynamic conferences. Proc. CRYPTO'92August 16–20, Santa Barbara, CA Berlin Springer-Verlag pp. 471–486.

[13] Blundo C., Frota Mattos L. A., Stinson D. R. (1996) Trade-offs between communication and storage in unconditionally secure schemes for broadcast encryption and interactive key distribution. Proc. CRYPTO'96August 18–22, Santa Barbara, CA Berlin Springer-Verlag pp. 387–400.

[14] Kurosawa K., Yoshida T., Desmedt Y., Burmester M. (1998) Some bounds and a construction for secure broadcast encryption. Proc. ASIACRYPT'98October 18–22, Beijing Berlin Springer-Verlag pp. 420–433.

[15] Stinson D. R. (1997) On some methods for unconditionally secure key distribution and broadcast encryption. Design. Code. Cryptogr. 12 215–243.[CrossRef]

[16] Gilbert E. N., J. MacWilliams F., Sloane N. J. A. (1974) Codes which detect deception. Bell Syst. Tech. J. 53 405–425.

[17] Simmons G. J. (1985) Authentication theory/coding theory. Proc. CRYPTO'84August 19–22, Santa Barbara, CA Berlin Springer-Verlag pp. 411–431.

[18] Simmons G. J. (1988) Message authentication with arbitration of transmitter/receiver disputes. Proc. EUROCRYPT'87April 13–15, Amsterdam Berlin Springer-Verlag pp. 151–165.

[19] Desmedt Y., Frankel Y., Yung M. (1992) Multi-receiver/Multi-sender network security: efficient authenticated multicast/feedback. Proc. IEEE Infocom'92May 4–8, Florence Piscataway, NJ IEEE pp. 2045–2054.

[20] Hanaoka G., Shikata J., Zheng Y., Imai H. (2000) Unconditionally secure digital signature schemes admitting transferability. Proc. ASIACRYPT'00December 3–7, Kyoto Berlin Springer-Verlag.

[21] Hanaoka G., Shikata J., Zheng Y., Imai H. (2002) Efficient and unconditionally secure digital signatures and a security analysis of a multireceiver authentication code. Proc. PKC'02February 12–14, Paris Berlin Springer-Verlag pp. 64–79.

[22] Shikata J., Hanaoka G., Zheng Y., Imai H. (2002) Security notions for unconditionally secure signature schemes. Proc. EUROCRYPT'02April 28–May 2, Amsterdam Berlin Springer-Verlag pp. 434–449.

[23] Ben-Or M., Goldwasser S., Wigderson A. (1988) Completeness theorems for non-cryptographic fault-tolerant distributed computation. Proc. STOC'88May 2–4, Chicago, IL New York, NY ACM pp. 1–10.

[24] Shannon C. E. (1949) Communication theory of secrecy systems. Bell Syst. Tech. J. 28 656–715.

[25] Erdös P., Frankl P., Furedi Z. (1985) Families of finite sets in which no sets is covered by the union of r others. Israel J. Math. 51 79–89.

[26] Dolev D., Dwork C., Naor M. (1991) Non-malleable cryptography. Proc. STOC'91May 6–8, New Orleans, LA New York, NY ACM pp. 542–552.

[27] Bellare M., Desai A., Jokipii E., Rogaway P. (1997) A concrete security treatment of symmetric encryption. Proc. FOCS'97October 19–22, Miami Beach, FL Piscataway, NJ IEEE pp. 394–403.

[28] Bellare M., Desai A., Pointcheval D., Rogaway P. (1998) Relations among notions of security for public-key encryption schemes. Proc. CRYPTO'98August 23–27, Santa Barbara, CA Berlin Springer-Verlag pp. 26–45.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract FREE Full Text (PDF) All Versions of this Article: 49/3/310    most recent bxh149v1 Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Hanaoka, G. Articles by Imai, H. Search for Related Content Social Bookmarking          What's this?

Online ISSN 1460-2067 - Print ISSN 0010-4620

Copyright © 2009 British Computer Society

Oxford Journals Oxford University Press

• Site Map
• Privacy Policy
• Frequently Asked Questions

Other Oxford University Press sites: Oxford University Press Oxford Journals China Oxford Journals Japan American National Biography Booksellers' Information Service Children's Fiction and Poetry Children's Reference Corporate & Special Sales Dictionaries Dictionary of National Biography Digital Reference English Language Teaching Higher Education Textbooks Humanities International Education Unit Law Medicine Music Online Products Oxford English Dictionary Reference Rights and Permissions Science School Books Social Sciences Very Short Introductions World's Classics