a. Consider a variant of Ajtais collision-resistant hash function satisfying the following functionality specifications:

Function modulus must be q = 251.

Set of function inputs must have bit length `in, where `in is a positive integer parameter (which you can adjust subject to satisfying the specifications).

Each coordinate in the input vector x has two bits (i.e. xi {0, 1, 2, 3}, each of these integers has a binary representation of maximal 2 bits).

Function Compression Ratio (CR) must be exactly equal to 4 (recall that CR is the ratio between the bit length of the function input and the functions output, when the latter is encoded in binary.

The dimension parameter n (number of rows of the matrix A) of Ajtais hash function should be left as a free parameter that you will adjust later to satisfy the security requirements below. Given n and the functionality specifications above, determine suitable values (expressed in terms of n) for the following parameters of the collision-resistant hash function:

Function output bit length: `out.

Function input bit length: `in.

Number of columns of matrix A: m. b

b. For your variant of Ajtais hash function from part (a), consider the following security specification:

It should not be possible to find collisions in the hash function using the LLL basis reduction algorithm.

What is the smallest value of n such that the above security specification is satisfied? (Hint: use the average-case LLL Hermite Factor estimate HF 1.02m0 , to estimate the length of the short SIS lattice vector returned by LLL for the SIS lattice L q (A0 ), using the submatrix A0 of A consisting of the first m0 columns. Determine the optimum value the attacker should use for m0 and compare the length of the corresponding short vector the attacker can compute to the length needed to compute a hash function collision as discussed in the lectures).

c (10 Marks) Now consider setting the parameters for security not just against LLL (which runs relatively quickly), but against a state of the art lattice reduction method (BKZ), using the BKZ complexity estimates. Namely, we would like to satisfy the following (more realistic) 128-bit security level specification:

It should not be possible to find collisions in the hash function in time less than 2 128 enumeration operations using the BKZ algorithm.

How large should n be set so that the above more realistic security specification is satisfied?