Short integer solutions (SIS)

Introduction

In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm.

Short integer solution problem

Definition

Let SISn,m,q,βSIS_{n, m, q, \beta} be a Short Integer Solution problem. We define it as such:

Given mm uniformly random vectors ai(Z/qZ)na_i∈(\mathbb{Z}/q\mathbb Z)^n, forming the columns of a matrix A(Z/qZ)n×mA∈(\mathbb{Z}/q\mathbb Z)^{n×m}, find a nonzero integer vector zZmz∈\mathbb{Z}^m of norm zβ‖z‖ ≤β (short) such that

fA(z)=Az=iaizi=0(Z/qZ)nz1a1+z2a2+...+zmam=0f_A(z) = Az = \sum_i a_i \cdot z_i = 0 \in (\mathbb{Z}/q\mathbb Z)^n \\ z_1\vec{a_1} + z_2\vec{a_2} +...+ z_m\vec{a_m} = 0

Without the constraint β\beta the solution would be as simple as Gaussian elimination. Also we want β<q\beta < q otherwise z=(q,0,...,0)Zmz = (q,0, ..., 0) \in \mathbb{Z}^m would be a fine solution.

Notice that a solution zz for AA can be converted to a solution for the extension [AA][A| A'] by appending 00s to zz \Rightarrow

  • big mm \Rightarrow easy (the more vectors we are given, the easier the problem becomes)

  • big nn \Rightarrow hard (the more dimension we work in the harder the problem becomes)

Solution existence is based on parameters set. One should think about them as follows:

  • nn is the security parameter. The bigger it is the harder the problem becomes

  • mm is set depending from application to application. Usually mnm \gg n

  • q=poly(n)q = \text{poly}(n), think of it as q=O(n2)q = \mathcal{O}(n^2)

  • β=\beta = the bound is set depending on application and βq\beta \ll q

SIS as a SVP problem

// TODO

Ajtai's hashing function

  • Parameters: m,n,qZm, n, q \in \mathbb{Z}, m>nlog2qm > n \log_2 q

  • Key: A(Z/qZ)n×mA \in (\mathbb{Z}/q\mathbb Z)^{n \times m}

  • Input: x{0,1}mx \in \{0, 1\}^m \Rightarrow Short vector

  • Output: fA(x)=Axmodq\boxed {f_A(x) = Ax \bmod q} where fA:{0,1}m(Z/qZ)nf_A : \{0, 1\}^m \to (\mathbb{Z}/q\mathbb Z)^n

Hash function properties:

Compression

We know x{0,1}mX=2nx \in \{0, 1\}^m \Rightarrow |\mathcal{X}| = 2^n and AxY=(Z/qZ)n(Z/qZ)n=qn=(2logq)nAx \in \mathcal Y = (\mathbb{Z}/q\mathbb Z)^n \Rightarrow |(\mathbb{Z}/q\mathbb Z)^n| = q^n = (2^{\log q})^n. Since we chose m>nlogqX>Ym > n \log q \Rightarrow |\mathcal{X}| > |\mathcal{Y}| .

Collision resistance:

halp here

Sage example:

from Crypto.Util.number import long_to_bytes, bytes_to_long
n, m, q = 20, 40, 1009
set_random_seed(1337)
A = random_matrix(Zmod(q),n, m)
print(A.parent())
# Full MatrixSpace of 20 by 40 dense matrices over Ring of integers modulo 1009
print(A.lift().parent())
# Full MatrixSpace of 20 by 40 dense matrices over Integer Ring
msg = b'msg'
x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad message
print(len(x)
# 40
print(x.parent())
# Vector space of dimension 40 over Ring of integers modulo 1009
print(len(A * x))
# 20

Cryptanalysis

Inverting the function:

Given AA and yy find x{0,1}mx \in \{0, 1\}^m such that Ax=ymodqAx = y \bmod q

Formulating as a lattice problem:

Find arbitrary tt such that At=ymodqAt = y \bmod q

  • All solutions to Ax=yAx = y are of the form t+Lt + L^{\perp} where L(A)={xZm:Ax=0(Z/qZ)n}{L}^\perp(A) = \{x \in \mathbb{Z}^m : Ax = 0 \in (\mathbb{Z}/q\mathbb Z)^n \}

  • So we need to find a short vector in t+L(A)t + {L}^{\perp}(A)

  • Equivalent, find vL(A)v \in {L}^{\perp}(A) closest to tt (CVP)

Hermite normal form

// TODO

Security Reduction

If somebody can explain the security bounds and reduction better, please do.

Resources