Abstract:
Provided are a tag generation device, method and program which are capable of parallel execution, need no precomputation, and are capable of reducing block-cipher calls to the minimum necessary using one block cipher key when a tag to be attached to a message is generated. A tag generation device is provided with: an input means ( 100 ) which divides a message into a plurality of blocks; an intermediate chunk hash means ( 101 ) to which the blocks included in the message are inputted as an object to be processed, and which, in units of a predetermined number of blocks, using one key, executes encipherment processing and post-processing of encipherment on the blocks in parallel to generate an intermediate output, and designates, as a next object to be processed, a message created by coupling the intermediate output and unprocessed blocks; and a final chunk hash means ( 102 ) which, when the number of block in the message or the number of blocks in the message created by coupling the intermediate output and the unprocessed block is a predetermined value or less, generates a tag corresponding to the message.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates to a message authentication technique using a symmetric-key block cipher, and particularly relates to a tag generation device, tag generation method, and tag generation program capable of parallel processing with no need for precomputation before processing start. 
       BACKGROUND ART 
       [0002]    Message authentication is a technique of assuring the authenticity of a message by attaching, to the message, a tag that can be computed only by those who know a secret key. For example, the use of message authentication enables the detection of whether or not communication between two parties sharing a secret key has been tampered with by a third party. A specific example is given below. Let K be a secret key shared by the sender and receiver of a message. For a message M, the sender sends a tag T=MAC (K, M) computed by assigning M and K to a message authentication code (MAC) function F, to the receiver. Having received a message M′ and a tag T′, the receiver computes a tag T″ from the shared key K and M′, and checks whether or not the received tag T′ and the computed tag T″ match. The receiver can thus verify whether or not the message M′ is from the stated sender. 
         [0003]    One of the message authentication schemes is a CBC-MAC scheme using a block cipher. The term “message authentication scheme” is hereafter referred to as “MAC scheme” or simply “MAC”. CBC-MAC is a MAC that uses, as its component, an encryption function E(K, *) of an n-bit block cipher with K as a key. CBC-MAC operates as follows. Let |M| be the length of a message M. In the case where |M| is a multiple of n, M is first divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m]|=n), where m is the number of blocks. Then, Y[m] is output as a tag through the following computation. 
         [0000]        Y[ 1]= E ( K,M[ 1]), Y[ 2]= E ( K,M[ 2]+ Y[ 1]), . . .  Y[m]=E ( K,M[m]+Y[m− 1]). 
         [0004]    Here, 0̂n is an n-bit all-zero sequence, and “+” denotes a bitwise exclusive-or (XOR). 
         [0005]    In the case where the length of the message is not a multiple of n, the message is first padded to make its length a multiple of n, before applying CBC-MAC. Simple CBC-MAC is easy to be forged when the message length is variable. For example, in the case where Y[1]=E(K, M[1]) is obtained as a tag for M=M[1], a tag generated for M′=(M[1], M[1]+Y[1]) is invariably Y[1]. 
         [0006]    OMAC described in Non Patent Literature (NPL)  1  is an improvement of CBC-MAC that removes the above-mentioned security drawback. OMAC is equivalent to CMAC recommended by NIST, and so is hereafter referred to as “CMAC”. In CMAC, the result of encrypting 0̂n is held beforehand, and an intermediate variable of CBC-MAC is changed using the held value only in the encryption of the last block. In detail, CMAC operates as follows. When a message M is given, M is divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m−1]|=n, 1≦|M[m]|≦n), and Y[m] is output as a tag using the following Formula 1. 
         [0000]        L=E ( K, 0̂ n ),
 
         [0000]        Y[ 1]= E ( K,M[ 1]), Y[ 2]= E ( K,M[ 2]+ Y[ 1]), . . . , Y[m− 1]= E ( K,M[m− 1]+ Y[m− 2]), 
         [0000]        Y[m]=E ( K,M[m]+Y[m− 1]+2 L ) if | M[m]|=n,    
         [0000]        Y[m]=E ( K ,( M[m]| 10*)+ Y[m− 1]+4 L ) if | M[m]|≦n   (Formula 1).
 
         [0007]    Here, (M[m]|10*) is an n-bit sequence obtained by padding M[m] with 10 . . . 0. 2L is multiplication by a generator of a finite field (Galois field) GF(2̂n) where L is an element of the field, and corresponds to multiplication by 2 in the finite field. 4L denotes 2(2L), and corresponds to multiplication by 2 twice.  FIG. 5  is an explanatory diagram illustrating tag output in CMAC. In  FIG. 5 , E K  denotes an encryption function of an n-bit block cipher with K as a key. “|” denotes a concatenation operator for a bit string. 
         [0008]    CMAC has the feature that, by computing L in Formula 1 beforehand, any message M can be processed with ceiling(|M|/n) block cipher calls. One block typically needs at least one block cipher call, according to security definition. Hence, this number of block cipher calls is a minimum number, except for precomputation. 
         [0009]    TMAC described in NPL 2 and XCBC described in NPL 3 are approximately the same process as CMAC mentioned above but, instead of using 2L or 4L in the last block, use a value generated from a key other than the block cipher key K. TMAC and XCBC therefore do not need precomputation of E(K, 0̂n), but have a drawback in that the MAC key is longer than that of CMAC. 
         [0010]    GCBC described in NPL 5 is an improvement for omitting the precomputation in CMAC while using only the block cipher key K as the MAC key. In GCBC and particularly GCBC1 described in NPL 5, Y[m] is output as a tag using the following Formula 2. 
         [0011]    When |M|&gt;n, 
         [0000]        Y[ 1]= E ( K,M[ 1]), Y[ 2]= E ( K,M[ 2]+ Y[ 1]), . . . , Y[m− 1]= E ( K,M[m− 1]+ Y[m− 2]), 
         [0000]        Y[m]=E ( K,M[m ]+( Y[m− 1]&lt;&lt;&lt;1)) if | M[m]|=n,    
         [0000]        Y[m]=E ( K ,( M[m]| 10*)+( Y[m− 1]&lt;&lt;&lt;2)) if | M[m]|≦n   (Formula 2).
 
         [0012]    Here, (Y[m−1]&lt;&lt;&lt;i) is the value obtained by shifting (logical shift) Y[m−1] left by i bits, where the right bits are filled in with zeros. When |M|=n, Y[2] is output as a tag in GCBC1 using the following formula. 
         [0000]        Y[ 1]= E ( K,M[ 1]), Y[ 2]= E ( K ,(10̂ n− 1)+( Y[ 1]&lt;&lt;&lt;2)).
 
         [0013]    When |M|&lt;n, Y[2] is output as a tag in GCBC1 using the following formula. 
         [0000]        Y[ 1]= E ( K ,( M[ 1]|10*)), Y[ 2]= E ( K ,(0̂ n )+( Y[ 1]&lt;&lt;&lt;2)).
 
         [0014]    In GCBC1, when |M|&gt;n, the process is completed with ceiling(|M|/n) block cipher calls with no need for precomputation. When |M|&lt;n, on the other hand, two block cipher calls are needed.  FIG. 6  is an explanatory diagram illustrating tag output in GCBC. In  FIG. 6 , “&lt;&lt;i” denotes an i-bit logical left shift.  FIG. 6(   a ) illustrates the process in the case where the number m of blocks of the message is 2 or more.  FIG. 6(   b ) illustrates the process in the case where the number m of blocks of the message is 1. 
         [0015]    Each of the schemes described above makes one block cipher call per message block, and so is incapable of processing blocks in parallel. 
         [0016]    PMAC described in NPL 4 is a MAC scheme capable of processing blocks in parallel. When a message M is given, M is divided into blocks M[1], M[2], . . . , M[m] (|M[1]|= . . . =|M[m−1]|=n, 1&lt;|M[m]I&lt;n), as in CMAC. Then, T is output as a tag using the following Formula 3. In the formula, 3L denotes 2L+L. 
         [0000]        L=E ( K, 0̂ n ),
 
         [0000]        S[i]=E ( K ,(2̂ i ) L+M[i ]) for  i= 1, . . . , m− 1
 
         [0000]        V=S[ 1]+ S[ 2]+ . . . + S[m− 1] 
         [0000]        T=E ( K,V+M[m]+ 2̂( m− 1) L 3 L ) if | M[m]|=n,  
 
         [0000]        T=E ( K,V +( M[m]| 10*)+2̂( m− 1) L (3̂2) L ) if | M[m]|≠n   (Formula 3).
 
         [0017]    PMAC differs from CBC-MAC, CMAC, and GCBC in that it is parallelizable except for the last one block. Moreover, PMAC can complete the entire process with ceiling(|M|/n) block cipher calls if L is precomputed, as with CMAC.  FIG. 7  is an explanatory diagram illustrating tag output in PMAC. In  FIG. 7 , 2 m-1 L, i.e. 2 i L, denotes multiplication by 2 i  in a finite field GF(2̂n) of L, and 3 2 L, i.e. 3 i L, denotes multiplication by 3 i  in the finite field GF(2̂n) of L. 
         [0018]    Other MAC schemes that are parallelizable include XOR MAC described in NPL 6. In XOR MAC, however, input to a block cipher includes information other than an input message, such as block indices. Accordingly, XOR MAC typically needs ceiling(|M|/m) block cipher calls (for some m&lt;n) for a message M, which is larger than the number of block cipher calls in PMAC. 
         [0019]    The schemes described in NPL 1, NPL 4, and NPL 5 are MAC schemes capable of computing output from only a secret key and a message. Such schemes are called deterministic MACs. 
         [0020]    PAT described in NPL 7 is known as another MAC that is parallelizable. However, PAT needs random number generation for MAC generation, and belongs to randomized MACs. In randomized MACs, a random number used needs to be included in part of output, which causes an increase in output size as compared with deterministic MACs. 
         [0021]    There is a message authentication device that combines a block cipher and part of its components to attain higher speed than existing block cipher authentication schemes, exhibit theoretical security, and improve efficiency in the preprocessing and the amount of memory used (for example, see Patent literature (PTL) 1). There is also a device that reads a plurality of blocks of an input message in parallel and reduces each block to decrease the number of data inputs to the subsequent encrypter, thus improving the authenticator generation speed (for example, see PTL 2). 
       CITATION LIST 
     Patent Literature 
       [0000]    
       
         PTL 1: Domestic Re-publication of PCT International Application No. WO2007/052477 
         PTL 2: Japanese Patent Application Publication No. 63-050223 Non Patent Literature 
         NPL 1: T. Iwata, K. Kurosawa, OMAC: One-Key CBC MAC. Fast Software Encryption-FSE 2003, Lecture Notes in Computer Science (LNCS) vol. 2887, February 2003 
         NPL 2: Kaoru Kurosawa, Tetsu Iwata: TMAC: Two-Key CBC MAC. IEICE Transactions vol. E87-A, No. 1: pp. 46-52 (2004) 
         NPL 3: John Black, Phillip Rogaway: CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions. CRYPTO 2000: vol. 1888, pp. 197-215 
         NPL 4: P. Rogaway. Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC, Advances in Cryptology-ASIACRYPT &#39;04. LNCS vol. 3329, pp. 16-31, 2004 
         NPL 5: M. Nandi. Fast and Secure CBC-Type MAC Algorithms, Fast Software Encryption-FSE &#39;09. LNCS vol. 5665, pp. 375-393, 2009 
         NPL 6: M. Bellare, R. Guerin, and P. Rogaway. XOR MACs: New methods for message authentication using finite pseudorandom functions. In CRYPTO &#39;95, volume 963 of LNCS, pages 15-28. Springer-Verlag, 1995 
         NPL 7: William E. Hall, Charanjit S. Jutla. Parallelizable authentication tree for random access storage, U.S. Pat. No. 7,451,310 
         NPL 8: D. E. Daykin. On the Rank of the Matrix f(A) and the Enumeration of Certain Matrices over a Finite Field, Journal of the London Mathematical Society, 1960, pp. 36-42 
       
     
       SUMMARY OF INVENTION 
     Technical Problem 
       [0032]    Here, a MAC scheme in which the number of necessary block cipher calls for a message M of two or more blocks except for precomputation is ceiling(|M|/n) is said to be “quasi-optimal” in computation cost, and a MAC scheme having the same feature for a message of one or more blocks is said to be “optimal” in computation cost. 
         [0033]    CMAC and PMAC are optimal in computation cost, but need precomputation of L=E(K, 0̂n), as mentioned above. For example in the case where the key is frequently changed or a large number of different keys are used for fast processing, the cost of precomputation becomes problematic. Besides, memory usage may be restricted in a computational environment in which resources are limited, such as a sensor network. CMAC and PMAC are not suitable in such an environment because it is hard to hold L. 
         [0034]    GCBC makes precomputation unnecessary and overcomes the above-mentioned problem, by limiting its achievement in computation cost to quasi-optimality while keeping the number of keys to one. However, GCBC is not parallelizable, as with CMAC. 
         [0035]    Thus, none of these MAC schemes satisfies all of the following requirements 1 to 4: 
         [0036]    1. quasi-optimal computation cost, that is, a message M of m blocks can be processed with m block cipher calls if m≧2; 
         [0037]    2. parallelizability; 
         [0038]    3. one block cipher key; and 
         [0039]    4. no precomputation such as L=E(K, 0̂n). 
         [0040]    The present invention therefore has an object of providing a block cipher-based deterministic MAC scheme that satisfies these four conditions. In detail, the present invention has an object of providing a tag generation device, tag generation method, and tag generation program that are parallelizable, need no precomputation, use one block cipher key, and require a minimum number of block cipher calls, when generating a tag to be attached to a message. 
       Solution to Problem 
       [0041]    A tag generation device according to the present invention includes: 
         [0042]    input means for dividing a message into a plurality of blocks; 
         [0043]    intermediate chunk hash means for receiving blocks included in the message as a processing target, performing encryption processing and post-processing of encryption for blocks using one key in units of a predetermined number of blocks in parallel to generate an intermediate output, and repeating the encryption processing and the post-processing of encryption on a message obtained by concatenating the intermediate output and unprocessed blocks as a next processing target; and 
         [0044]    last chunk hash means for, in the case where the number of blocks of the message or the number of blocks of the message obtained by concatenating the intermediate output and the unprocessed blocks is less than or equal to a predetermined value, performing the encryption processing and the post-processing of encryption on the message to generate a tag. 
         [0045]    A tag generation method according to the present invention includes: 
         [0046]    dividing a message into a plurality of blocks; 
         [0047]    receiving blocks included in the message as a processing target, performing encryption processing and post-processing of encryption for blocks using one key in units of a predetermined number of blocks in parallel to generate an intermediate output, and repeating the encryption processing and the post-processing of encryption on a message obtained by concatenating the intermediate output and unprocessed blocks as a next processing target; and 
         [0048]    performing, in the case where the number of blocks of the message or the number of blocks of the message obtained by concatenating the intermediate output and the unprocessed blocks is less than or equal to a predetermined value, the encryption processing and the post-processing of encryption on the message to generate a tag. 
         [0049]    A tag generation program, according to the present invention, for causing a computer to execute: 
         [0050]    a process of dividing a message into a plurality of blocks; 
         [0051]    a process of receiving blocks included in the message as a processing target, performing encryption processing and post-processing of encryption for blocks using one key in units of a predetermined number of blocks in parallel to generate an intermediate output, and repeating the encryption processing and the post-processing of encryption on a message obtained by concatenating the intermediate output and unprocessed blocks as a next processing target; and 
         [0052]    a process of, in the case where the number of blocks of the message or the number of blocks of the message obtained by concatenating the intermediate output and the unprocessed blocks is less than or equal to a predetermined value, performing the encryption processing and the post-processing of encryption on the message to generate a tag. 
       Advantageous Effects of Invention 
       [0053]    According to the present invention, when generating a tag to be attached to a message, such tag generation that is parallelizable, needs no precomputation, uses one block cipher key, and requires a minimum number of block cipher calls can be realized. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0054]      FIG. 1  is a block diagram illustrating the structure of Exemplary embodiment 1 of a tag generation device according to the present invention. 
           [0055]      FIG. 2  is an explanatory diagram illustrating the process of a block cipher and a partial sequence cyclic shift. 
           [0056]      FIG. 3  is an explanatory diagram illustrating the combination of the process by intermediate chunk hash means and the process by last chunk hash means. 
           [0057]      FIG. 4  is a flowchart illustrating the operation of the tag generation device in exemplary embodiment 1. 
           [0058]      FIG. 5  is an explanatory diagram illustrating tag output in CMAC. 
           [0059]      FIG. 6  is an explanatory diagram illustrating tag output in GCBC. 
           [0060]      FIG. 7  is an explanatory diagram illustrating tag output in PMAC. 
           [0061]      FIG. 8  is a block diagram illustrating the minimum structure of the tag generation device according to the present invention. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
     Exemplary Embodiment 1 
       [0062]    The following describes an exemplary embodiment 1 of the present invention with reference to drawings. 
         [0063]    In this exemplary embodiment, unless otherwise noted, “+” denotes a bitwise exclusive-or, the length of one block is n bits, |X| denotes the bit length of a binary sequence X, and |X|_n denotes ceiling(|X|/n), that is, |X|_n denotes the number of blocks when X is divided into n-bit blocks. Moreover, X=(X[1], X[2], . . . , X[i]) denotes that X includes i blocks. In the case where |X| is not a multiple of n, the length of the last block is less than n. The last block of X in this case is a partial block. 
         [0064]    In this exemplary embodiment, when an n-bit block cipher is denoted by E and its key by K, a ciphertext generated from an n-bit plaintext X using the key K is written as E(K, X). In this exemplary embodiment, K is a single key, and accordingly E(K, X) is abbreviated as E(X) unless otherwise noted. 
         [0065]    In this exemplary embodiment, a positive integer u greater than or equal to 2 is defined as a parameter. In actual use environments, the highest computation efficiency is attained by setting the positive integer u to be equal to or a multiple of the number of parallelizable units. 
         [0066]      FIG. 1  is a block diagram illustrating the structure of the exemplary embodiment 1 of a MAC tag generation device (hereafter simply referred to as “tag generation device”) according to the present invention. 
         [0067]    The MAC tag generation device according to the present invention includes input means  100 , intermediate chunk hash means  101 , last chunk hash means  102 , and output means  103 . 
         [0068]    The input means  100  receives a message M that is subjected to tag generation. The message M is any bit string. The input means  100  receives the message M, for example, from a character input device such as a keyboard. 
         [0069]    The intermediate chunk hash means  101  hashes an n(u+1)-bit input to n bits using an n-bit block cipher E, where u is a positive integer greater than or equal to 2. 
         [0070]    In detail, the intermediate chunk hash means  101  first receives n(u+1) bits, i.e. u+1 n-bit blocks, and encrypts u blocks from among the u+1 blocks using the n-bit block cipher E to obtain u ciphertexts. The intermediate chunk hash means  101  then performs post-processing of encryption on the obtained u ciphertexts. As the post-processing of encryption, the intermediate chunk hash means  101  in this exemplary embodiment applies each of the u ciphertexts to a post-processing function, to obtain a post-processing output block for each ciphertext. Lastly, the intermediate chunk hash means  101  computes an exclusive-or of an exclusive-or of the u post-processing output blocks and the (u+1)th block, to obtain an n-bit output (hereafter referred to as “intermediate output”). 
         [0071]    The intermediate chunk hash means  101  holds beforehand a set of a post-processing functions pp(0, X), pp(1, X), . . . , pp(a−1, X) that each have an n-bit binary sequence X as an input. Each pp(i, X) has an n-bit output, and a is greater than or equal to u+2. Here, i is a parameter representing an index. 
         [0072]    The positive integer u and the post-processing function pp are stored beforehand in a storage device (not illustrated) such as memory included in the MAC tag generation device. 
         [0073]    When the input is X (=X[1], X[2], . . . , X[u+1] (|X[i]|=n for all i=1, . . . , u+1)), the intermediate chunk hash means  101  outputs the computation result of the following Formula 4 using the set of post-processing functions. 
         [0000]        pp (0, E ( X[ 1]))+ pp (1, E ( X[ 2]))+ . . . + pp ( u− 1, E ( X[u ]))+ X[u+ 1]  (Formula 4).
 
         [0074]    For an n-bit uniform random number R and any non-empty subset A={i — 1, . . . , i_t} of a set {0, 1, . . . , a−1}, the set of pp functions has the feature that the probability expressed by the following Formula 5 has a small upper bound for any y. 
         [0000]        Pr[pp ( i   — 1, R )+ pp ( i   — 2, R )+ . . . + pp ( i   —   t,R )= y]   (Formula 5).
 
         [0075]    Here, Pr(A) denotes the probability that A occurs. For example, the function set having such a feature can be realized by a cyclic shift (partial sequence cyclic shift) for a partial sequence having a special prime number length. Let VL be the first z bits of V which is the output block of the post-processing function (post-processing output block), VR be the latter (n-z) bits of V, and rotate(i, V) be an i-bit left cyclic shift of VL. Then, pp(i, V) can be expressed as shown in Formula 6. Here, z is a prime number, and includes 2 as a primitive root modulo z. 
         [0000]        pp ( i,V )=rotate( i− 1, VL )&lt;&lt;&lt; VR   (Formula 6).
 
         [0076]    From the study result described in NPL 8, it can be understood that a function set {pp(0, *), . . . , pp(z−1,*)} has the property that the probability computed according to Formula 5 is at most 2/2̂n. For example, z satisfying the above-mentioned condition is 61, 107. 
         [0077]      FIG. 2  is an explanatory diagram illustrating the process of the block cipher and the partial sequence cyclic shift. In  FIG. 2 , “&lt;&lt;&lt; k i” denotes an i-bit cyclic shift of the first k-bit sequence.  FIG. 2(   a ) illustrates the process in the case where the number m of blocks of the message is 2 or more.  FIG. 2(   b ) illustrates the process in the case where the number m of blocks of the message is 1. 
         [0078]    The last chunk hash means  102  hashes an input that is greater than or equal to 1 bit and less than or equal to n(u+2) bits, to n bits using the above-mentioned positive integer u as a parameter. 
         [0079]    The last chunk hash means  102  uses the set of post-processing functions pp(0, *), pp(1, *), . . . , pp(a−1, *), as with the intermediate chunk hash means  101 . The last chunk hash means  102  defines cst1 and cst2 as constants with no duplicate from integers 0 to a−1 beforehand, where cst1 and cst2 are greater than or equal to the positive integer u. These are necessary to guarantee the difference from the first argument of the pp functions used by the intermediate chunk hash means  101  and ensure security. 
         [0080]    In the case where there is a possibility that the input message is one block, the last chunk hash means  102  additionally defines two constants cst_z1 and cst_z2. These constants may be any values, e.g. cst_z1=0 and cstz2=1. 
         [0081]    The last chunk hash means  102  holds cst1, cst2, cst_z1, and cst_z2 beforehand. In detail, cst1, cst2, cst_z1, and cst_z2 are stored beforehand in a storage device such as memory included in the MAC tag generation device. 
         [0082]    The detailed process by the last chunk hash means  102  when the input X is blocks X[1], X[2], . . . , X[x] (|X[i]|=n for all i=1, . . . , x−1, 1|X[x]|&lt;n) is described below. 
         [0083]    In the case where the input X is greater than n bits, i.e. x≧2, the last chunk hash means  102  sets S to the following. 
         [0000]        pp (0, E ( X[ 1]))+ pp (1, E ( X[ 2]))+ . . . + pp ( x− 3, E ( X[x− 2])). 
         [0084]    In the case where x=2, the last chunk hash means  102  sets S to 0̂n. 
         [0085]    If the last block X[x] is exactly n bits, the last chunk hash means  102  outputs the following. 
         [0000]        E ( S+pp ( cst 1, E ( X[x− 1]))+ X[x ]). 
         [0086]    If X[x] is a partial block, i.e. less than n bits, the last chunk hash means  102  outputs the following. 
         [0000]        E ( S+pp ( cst 2, E ( X[x− 1]))+ X[x]| 10*). 
         [0087]    Here, X[x]|10* is an n-bit sequence obtained by padding X[x] with 10 . . . 0 sequence. 
         [0088]    In the case where the input X is less than or equal to n bits, i.e. x=1 and X=X[1], on the other hand, if X[1] is exactly n bits, the last chunk hash means  102  outputs the following. 
         [0000]        E ( pp ( cst   —   z 1, E (0̂ n ))+ X[ 1]).
 
         [0089]    If X[1] is a partial block, i.e. less than n bits, the last chunk hash means  102  outputs the following. 
         [0000]        E ( pp ( cst   —   z 2, E (0̂ n ))+ X[ 1]|10*).
 
         [0090]    Here, 0̂n is an n-bit all-zero sequence. Any n-bit constant may be used instead of the all-zero sequence. 
         [0091]    In the MAC tag generation device, the process by the intermediate chunk hash means  101  and the process by the last chunk hash means  102  are performed in combination. 
         [0092]      FIG. 3  is an explanatory diagram illustrating the combination of the process by the intermediate chunk hash means  101  and the process by the last chunk hash means  102 .  FIG. 3(   a ) illustrates the combination of the process by the intermediate chunk hash means  101  and the process by the last chunk hash means  102 .  FIG. 3(   b ) illustrates the process inside the intermediate chunk hash means  101 .  FIG. 3(   c ) illustrates the process inside the last chunk hash means  102 . 
         [0093]    In detail, when the message M is input to the MAC tag generation device, the input means  100  extracts the first u+1 blocks of the intermediate input, assuming that the message M is the initial value of the intermediate input. The input means  100  supplies the extracted blocks to the intermediate chunk hash means  101  as X (=X[1], X[2], . . . , X[u+1]), and acquires an output H from the intermediate chunk hash means  101 . 
         [0094]    The input means  100  then concatenates the output H and the (u+2)th and succeeding blocks of the intermediate input, as the new intermediate input. The input means  100  repeats the above-mentioned process until the intermediate input becomes less than or equal to u+2 blocks. 
         [0095]    Lastly, once the intermediate input has become less than or equal to u+2 blocks, the input means  100  supplies the whole intermediate input to the last chunk hash means  102 . The last chunk hash means  102  then outputs a tag T as the final output. 
         [0096]    In the case where the message M is less than or equal to u+2 blocks from the beginning, only the process by the last chunk hash means  102  is performed without the process by the intermediate chunk hash means  101 . 
         [0097]    In the case where the message is one block, the block cipher is called twice. In the case where the message is longer, on the other hand, the input to the last chunk hash means  102  is not one block, and accordingly no excess block cipher call takes place. This indicates that, except in the case where the message is one block, the number of blocks of the message and the number of block cipher calls match and quasi-optimal computation cost is achieved. 
         [0098]    The output means  103  outputs the tag T output from the last chunk hash means  102 , to a display device, a printer, or the like. 
         [0099]    The input means  100 , the intermediate chunk hash means  101 , the last chunk hash means  102 , and the output means  103  are, for example, realized by a computer operating according to a tag generation program. In this case, a CPU reads the tag generation program and, according to the program, operates as the input means  100 , the intermediate chunk hash means  101 , the last chunk hash means  102 , and the output means  103 . Alternatively, the input means  100 , the intermediate chunk hash means  101 , the last chunk hash means  102 , and the output means  103  may be realized by separate hardware. 
         [0100]    The following describes the operation in this exemplary embodiment. 
         [0101]      FIG. 4  is a flowchart illustrating the operation of the tag generation device in the exemplary embodiment 1. 
         [0102]    First, upon input of the input message M, the input means  100  divides the message M into n-bit blocks. In detail, the input means  100  obtains M[1], M[2], . . . , M[m] from the message M (step S 101 ), where |M[i]|=n for all i=1, . . . , m−1, 1&lt;|M[m]|&lt;n. The number m of blocks can be expressed as ceiling(|M|/n), i.e. |M|_n, using the ceiling function. 
         [0103]    In the case where the message M is one block, i.e. M=M[1] (step S 102 : yes), the input means  100  outputs the message M directly to the last chunk hash means  102 . The last chunk hash means  102  outputs the tag T computed from the message M, to the output means  103  as the final output (step S 103 ). 
         [0104]    Otherwise (step S 102 : no), the input means  100  outputs the message M to the intermediate chunk hash means  101  as the initial value of the intermediate input. Here, in the case where the message M is less than or equal to u+2 blocks (step S 104 : yes), the input means  100  outputs the message M not to the intermediate chunk hash means  101  but to the last chunk hash means  102 . The last chunk hash means  102  outputs the tag T computed from the message M, to the output means  103  as the final output (step S 106 ). 
         [0105]    In the case where the message M is greater than or equal to u+3 blocks (step S 104 : no), the input means  100  extracts the first u+1 blocks of the message M, and outputs the extracted blocks to the intermediate chunk hash means  101 . The intermediate chunk hash means  101  hashes the received blocks of the message M, to obtain the output H as the intermediate output (step S 105 ). 
         [0106]    After the output H is obtained, the input means  100  concatenates the output H and the remaining blocks of the message M, as the new intermediate input. The input means  100  outputs the new intermediate input to the intermediate chunk hash means  101 . The input means  100  and the intermediate chunk hash means  101  repeat the process of steps S 104  and S 105  in sequence, until the number of blocks of the intermediate input, i.e. |M|_n, becomes less than or equal to u+2. 
         [0107]    In the case where the number of blocks of the intermediate input has become less than or equal to u+2 (step S 104 : yes), the input means  100  outputs the whole intermediate input to the last chunk hash means  102 . The last chunk hash means  102  outputs the tag T computed from the whole intermediate input, to the output means  103  as the final output (step S 106 ). 
         [0108]    Lastly, the output means  103  outputs the tag T to the display device or the like (step S 107 ). 
         [0109]    As described above, in this exemplary embodiment, the block cipher function E K  is used only m times for the message M of m blocks if m is greater than or equal to 2, as illustrated in  FIG. 2 . In other words, the process is completed with m block cipher calls. There is also no need to precompute a ciphertext E(0̂n) of a constant plaintext, unlike PMAC. Moreover, only one key K is used. 
         [0110]    Further, in this exemplary embodiment, setting the predetermined parameter u to be equal to (or a multiple of) the number of parallelizable units makes it possible to always process a message in units of u blocks in parallel. The maximum possible value of u depends on the post-processing function pp used. 
         [0111]    The condition to be satisfied by the post-processing function pp is to ensure that, when R is an n-bit uniform random number, the probability of the following Formula 7 holding true is sufficiently small for any n-bit value y and any subset {i — 1, i — 2, . . . , i_t}⊂{0, 1, . . . , u, cst1, cst2} of all parameter values. 
         [0000]        pp ( i   — 1, R )+ pp ( i   — 2, R )+ . . . + pp ( i   —   t,R )= y   (Formula 7).
 
         [0112]    For example, suppose n is a prime number satisfying a specific condition, in the case where pp(i, R) is an i-bit cyclic shift of R (the direction of the cyclic shift may be left or right as long as it is uniform) and the range of the argument i is limited to {0, 1, . . . , n−2}. It is derived from the study result described in NPL 8 that the probability of Formula 7 holding true is a sufficiently small value (2/2̂n). 
         [0113]    The block size n is normally a power of 2, such as 64 or 128, and so is not a prime number. However, the same effect can be attained by setting, as the part to be cyclically shifted, not the whole block but the prime number length satisfying the condition. For example, the maximum prime number less than or equal to 64 and satisfying the condition is 61, and the maximum prime number less than or equal to 128 and satisfying the condition is 107. By setting the pp function as the cyclic shift by such length, a sufficiently large number of parallelizable units, such as 57 or 103, can be achieved even when overhead due to reserved words or the like is taken into account. 
         [0114]    PMAC has the structure in which the blocks except the last one block are all arranged in parallel, and so is in principle capable of parallel processing of up to m−1 units for a message of m blocks. In other words, PMAC has the property of unlimited parallelizability, that is, the property of being “fully parallelizable”. In practice, however, the number of parallelizable units is typically limited in some way. The parallelizability achieved by the present invention is therefore sufficiently practical. 
         [0115]    In this exemplary embodiment, for a message of two or more blocks, the last one block needs to be processed alone. This property that the last one block cannot be processed in parallel with the rest of the blocks is, however, the same as PMAC. 
         [0116]    Thus, according to this exemplary embodiment, when generating a tag to be attached to a message, such tag generation that uses one block cipher key, requires a minimum number of block cipher calls for a message of two or more blocks, has a practically sufficient level of parallelizability, and needs no precomputation can be realized. 
         [0117]    Moreover, in this exemplary embodiment, the message length of a message input to the MAC authentication tag generation device has no restriction. Hence, a message of any length can be processed according to this exemplary embodiment. 
         [0118]    The present invention is applicable to message authentication in wireless or wired data communication, detection of tampering with a database, verification of the validity of memory in a device, and so on. 
         [0119]      FIG. 8  is a block diagram illustrating the minimum structure of the tag generation device according to the present invention. As illustrated in  FIG. 8 , the tag generation device includes input means  100  for dividing a message into a plurality of blocks. The tag generation device also includes intermediate chunk hash means  101  for receiving blocks included in the message as a processing target, performing encryption processing and post-processing of encryption for blocks using one key in units of a predetermined number of blocks in parallel to generate an intermediate output, and repeating the encryption processing and the post-processing of encryption on a message obtained by concatenating the intermediate output and unprocessed blocks as a next processing target. The tag generation device further includes last chunk hash means  102  for, in the case where the number of blocks of the message or the number of blocks of the message obtained by concatenating the intermediate output and the unprocessed blocks is less than or equal to a predetermined value, performing the encryption processing and the post-processing of encryption on the message to generate a tag. 
         [0120]    With this structure, tag generation that uses one block cipher key, requires a minimum number of block cipher calls for a message of two or more blocks, has a practically sufficient level of parallelizability, and needs no precomputation can be realized. 
         [0121]    The following tag generation device is also disclosed in the foregoing exemplary embodiment. 
         [0122]    (1) The last chunk hash means of the tag generation device holds any two constants cst_z1 and cst_z2, as additional parameters of the post-processing function pp(i, *) and applies, in the case where the input X′ is less than n bits in length, a ciphertext obtained by encrypting any n-bit constant using the n-bit block cipher E to the post-processing function pp(i, *) having cst_z1 as a parameter to obtain a post-processing output block W, takes an exclusive-or of the post-processing output block W and the input X′ that has been padded to n bits, encrypts the exclusive-or using the n-bit block cipher E, and outputs the encrypted exclusive-or as the tag. The last chunk hash means applies, in the case where the input X′ is n bits in length, the ciphertext to the post-processing function pp(i, *) having cst_z2 as a parameter to obtain the post-processing output block W, takes an exclusive-or of the post-processing output block W and the input X′, encrypts the exclusive-or using the n-bit block cipher E, and outputs the encrypted exclusive-or as the tag. The input means supplies the message M to the last chunk hash means, in the case where the message M is less than or equal to n bits in length. 
         [0123]    With this structure, tag generation that uses one block cipher key, requires a minimum number of block cipher calls for a message of two or more blocks, has a practically sufficient level of parallelizability, and needs no precomputation can be realized. 
         [0124]    (2) The last chunk hash means of the tag generation device holds any two constants cst_z1 and cst_z2, as additional parameters of the post-processing function pp(i, *) and applies, in the case where the input X′ is less than n bits in length, a ciphertext obtained by encrypting any n-bit constant using the n-bit block cipher E to the post-processing function pp(i, *) having cst_z1 as a parameter to obtain a post-processing output block W, takes an exclusive-or of the post-processing output block W and the input X′ that has been padded to n bits, encrypts the exclusive-or using the n-bit block cipher E, and outputs the encrypted exclusive-or as the tag. The last chunk hash means applies, in the case where the input X′ is n bits in length, the ciphertext to the post-processing function pp(i, *) having cst_z2 as a parameter to obtain the post-processing output block W, takes an exclusive-or of the post-processing output block W and the input X′, encrypts the exclusive-or using the n-bit block cipher E, and outputs the encrypted exclusive-or as the tag. The input means supplies the message M to the last chunk hash means, in the case where the message M is less than or equal to n bits in length. 
         [0125]    With this structure, tag generation that uses one block cipher key, has a practically sufficient level of parallelizability, and needs no precomputation can be realized for a message less than or equal to n bits in length, i.e. a message of one block. Moreover, since only two block cipher calls are needed, the number of necessary block cipher calls can be minimized even in the case where the message is one block. 
         [0126]    (3) The post-processing function pp(i, *) of the tag generation device is a function of performing a cyclic shift not on a whole bit string subjected to the post-processing but on a bit string of a predetermined prime number length. 
         [0127]    With this structure, a practically sufficient level of parallelizability can be achieved even in the case where the block size n by which the message is divided is not a prime number. 
         [0128]    This application claims priority based on Japanese Patent Application No. 2013-041890 filed on Mar. 4, 2013, the disclosure of which is incorporated herein in its entirety. 
         [0129]    Though the present invention has been described with reference to the foregoing exemplary embodiment, the present invention is not limited to the foregoing exemplary embodiment. Various changes understandable by those skilled in the art within the scope of the present invention can be made to the structures and details of the present invention. 
       REFERENCE SIGNS LIST 
       [0000]    
       
         
           
               100  input means 
               101  intermediate chunk hash means 
               102  last chunk hash means 
               103  output means