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 z∈Zmz∈\mathbb{Z}^m of norm ‖z‖≤β‖z‖ ≤β (short) such that

fA(z)=Az=∑iai⋅zi=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 [A∣A′][A| A'] by appending 00s to zz ⇒\Rightarrow

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

  • big n⇒n \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 m≫nm \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,q∈Zm, n, q \in \mathbb{Z}, m>nlog⁡2qm > n \log_2 q

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

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

  • Output: fA(x)=Ax mod q\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}m⇒∣X∣=2nx \in \{0, 1\}^m \Rightarrow |\mathcal{X}| = 2^n and Ax∈Y=(Z/qZ)n⇒∣(Z/qZ)n∣=qn=(2log⁡q)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>nlog⁡q⇒∣X∣>∣Y∣m > 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=y mod qAx = y \bmod q

Formulating as a lattice problem:

Find arbitrary tt such that At=y mod qAt = y \bmod q

  • All solutions to Ax=yAx = y are of the form t+L⊥t + L^{\perp} where L⊥(A)={x∈Zm: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 v∈L⊥(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

PreviousCryptographic lattice problemsNextLearning with errors (LWE)

Last updated

Was this helpful?