Hash value calculation device, hash value calculation method, and non-transitory computer-readable storage medium including computer executable instruction

1. A hash value calculation device that calculates a hash value using an encryption function for a block cipher having an n-bit plaintext length and a k-bit (k>n) key length, the hash value calculation device comprising:

a default-length value input part, implemented by circuitry, that receives L (L is an integer of 2 or more) of values M[ 1 ], . . . , M[L] each having k-n bits;

a compression function calculation part, implemented by the circuitry, that, for each integer i of i=1, . . . , L in an ascending order: calculates a function f[i] which, upon input of a value M[i] received by the default-length value input part, an n-bit value y 1 [ i− 1](a value y 1 [ 0 ] is a predetermined value IV 1 ), and an n-bit value y 2 [ i− 1](a value y 2 [ 0 ] is a predetermined value IV 2 ), outputs an n-bit value x 1 [ i ], an n-bit value x 2 [ i ], a k-bit value k 1 [ i ], and a k-bit value k 2 [ i ]; for the value x 1 [ i ] as a plaintext and the value k 1 [ i ] as a key, calculates an n-bit value y 1 [ i ] with the encryption function; and for the value x 2 [ i ] as a plaintext and the value k 2 [ i ] as a key, calculates an n-bit value y 2 [ i ] with the encryption function; and

a hash value calculation part, implemented by the circuitry, that, upon input of a value y 1 [L] and a value y 2 [L] which are calculated by the compression function calculation part, calculates a hash value with an injective function g.

2. The hash value calculation device according to claim 1 ,

wherein, for each integer i=1, . . . , L, the function f[i] is injective, and where the value M[i] is a fixed value, an injective relation holds between the value x 1 [ i ], the value x 2 [ i ] and the value y 1 [ i ], the value y 2 [ i ], and the value x 1 [ i ] and the value x 2 [ i ] are not equal, or the value k 1 [ i ] and the value k 2 [ i ] are not equal.

3. The hash value calculation device according to claim 1 ,

wherein, for each integer i of i=1, . . . , L, the function f[i] is a function that makes the value y 1 [ i− 1] into the value x 1 [ i ], makes the value y 1 [ i− 1] into the value x 2 [ i ] through conversion with a substitute function p, and makes the value y 2 [ i− 1] and the value M[i] in combination into the value k 1 [ i ] and the value k 2 [ i].

4. The hash value calculation device according to claim 1 ,

wherein, for each integer i of i=1, . . . , L, the function f[i] is a function that makes the value y 1 [ i− 1] into the value x 1 [ i ], makes the value y 2 [ i− 1] into the value x 2 [ i ] through inversion of respective bits, makes the value M[i] and the value y 2 [ i− 1] in combination into the value k 1 [ i ], and makes the value M[i] and the value y 1 [ i− 1] in combination into the value k 2 [ i].

5. The hash value calculation device according to claim 1 ,

wherein, for each integer i of i=1, . . . , L, the function f[i] is a function that makes the value y 1 [ i− 1] into the value x 1 [ i ], makes the value y 2 [ i− 1] into the value x 2 [ i ], makes the value M[i] and the value y 2 [ i− 1] in combination into the value k 1 [ i ], and makes a value made from the value y 1 [ i ] and the value M[i] in combination into the value k 2 [ i ], the value y 1 [ i ] being calculated by the encryption function upon input of the value x 1 [ i ] and the value k 1 [ i].

6. The hash value calculation according to claim 1 , further comprising:

an arbitrary-length value input part, implemented by the circuitry, that receives a value M having an arbitrary bit length;

a padding part, implemented by the circuitry, that adds a predetermined value to the value M received by the arbitrary-length value input part and outputs a value M* having a bit length that is L times as large as (k-n) bits; and

a partitioning part, implemented by the circuitry, that partitions the value M* generated by the padding part into L and outputs values M[ 1 ], . . . , M[L] each having k-n bits,

wherein the default-length value input part receives the values M[ 1 ], . . . , M[L] outputted by the partitioning part.

7. A hash value calculation method of calculating a hash value using an encryption function for a block cipher having an n-bit plaintext length and a k-bit (k>n) key length, the method comprising:

a default-length value input step of, with an input device, receiving L (L is an integer of 2 or more) of values M[ 1 ], . . . , M[L] each having k-n bits;

a compression function calculation step of, with a processing device, for each integer i of i=1, . . . , L in an ascending order: calculating a function f[i] which, upon input of a value M[i] received in the default-length value input step, an n-bit value y 1 [ i− 1](a value y 1 [ 0 ] is a predetermined value IV 1 ), and an n-bit value y 2 [ i− 1](a value y 2 [ 0 ] is a predetermined value IV 2 ), outputs an n-bit value x 1 [ i ], an n-bit value x 2 [ i ], a k-bit value k 1 [ i ], and a k-bit value k 2 [ i ]; for the value x 1 [ i ] as a plaintext and the value k 1 [ i ] as a key, calculating an n-bit value y 1 [ i ] with the encryption function; and for the value x 2 [ i ] as a plaintext and the value k 2 [ i ] as a key, calculating an n-bit value y 2 [ i ] with the encryption function; and

a hash value calculation step of, with the processing device, upon input of a value y 1 [L] and a value y 2 [L] which are calculated by the compression function calculation step, calculating a hash value with an injective function g.

8. A non-transitory computer-readable storage medium including computer executable instructions, wherein the instructions, when executed by a computer, cause the computer to perform a method of calculating a hash value using an encryption function for a block cipher having an n-bit plaintext length and a k-bit (k>n) key length, the method comprising:

receiving L (L is an integer of 2 or more) of values M[ 1 ], . . . , M[L] each having k-n bits;

calculating a function f[i] which, for input of a value M[i] received by the receiving, an n-bit value y 1 [ i− 1](a value y 1 [ 0 ] is a predetermined value IV 1 ), and an n-bit value y 2 [ i− 1](a value y 2 [ 0 ] is a predetermined value IV 2 ) for each integer i of i=1, . . . , L in an ascending order, outputs an n-bit value x 1 [ i ], an n-bit value x 2 [ i ], a k-bit value k 1 [ i ], and a k-bit value k 2 [ i ]; for the value x 1 [ i ] as a plaintext and the value k 1 [ i ] as a key, calculating an n-bit value y 1 [ i ] with the encryption function; and for the value x 2 [ i ] as a plaintext and the value k 2 [ i ] as a key, calculating an n-bit value y 2 [ i ] by the encryption function; and

upon input of a value y 1 [L] and a value y 2 [L] which are calculated by the calculating, calculating a hash value through an injective function g.