CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Introduction
  • Short integer solution problem
  • SIS as a SVP problem
  • Ajtai's hashing function
  • Hash function properties:
  • Cryptanalysis
  • Hermite normal form
  • Security Reduction
  • Resources

Was this helpful?

Export as PDF
  1. Lattices
  2. Cryptographic lattice problems

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}SISn,m,q,β​ be a Short Integer Solution problem. We define it as such:

Given mmm uniformly random vectors ai∈(Z/qZ)na_i∈(\mathbb{Z}/q\mathbb Z)^nai​∈(Z/qZ)n, forming the columns of a matrix A∈(Z/qZ)n×mA∈(\mathbb{Z}/q\mathbb Z)^{n×m}A∈(Z/qZ)n×m, find a nonzero integer vector z∈Zmz∈\mathbb{Z}^mz∈Zm of norm ‖z‖≤β‖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} = 0fA​(z)=Az=i∑​ai​⋅zi​=0∈(Z/qZ)nz1​a1​​+z2​a2​​+...+zm​am​​=0

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

Notice that a solution zzz for AAA can be converted to a solution for the extension [A∣A′][A| A'][A∣A′] by appending 000s to zzz ⇒\Rightarrow⇒

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

  • big n⇒n \Rightarrown⇒ 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:

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

  • mmm is set depending from application to application. Usually m≫nm \gg nm≫n

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

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

SIS as a SVP problem

// TODO

Ajtai's hashing function

  • Parameters: m,n,q∈Zm, n, q \in \mathbb{Z}m,n,q∈Z, m>nlog⁡2qm > n \log_2 qm>nlog2​q

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

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

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

Hash function properties:

Compression

We know x∈{0,1}m⇒∣X∣=2nx \in \{0, 1\}^m \Rightarrow |\mathcal{X}| = 2^nx∈{0,1}m⇒∣X∣=2n 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})^nAx∈Y=(Z/qZ)n⇒∣(Z/qZ)n∣=qn=(2logq)n. Since we chose m>nlog⁡q⇒∣X∣>∣Y∣m > n \log q \Rightarrow |\mathcal{X}| > |\mathcal{Y}| m>nlogq⇒∣X∣>∣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 AAA and yyy find x∈{0,1}mx \in \{0, 1\}^mx∈{0,1}m such that Ax=y mod qAx = y \bmod qAx=ymodq

Formulating as a lattice problem:

Find arbitrary ttt such that At=y mod qAt = y \bmod qAt=ymodq

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

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

  • Equivalent, find v∈L⊥(A)v \in {L}^{\perp}(A)v∈L⊥(A) closest to ttt (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 3 years ago

Was this helpful?

+

- page 18

https://simons.berkeley.edu/sites/default/files/docs/14967/sis.pdf
https://www.youtube.com/watch?v=qZIjVX61NFc&list=PLgKuh-lKre10rqiTYqJi6P4UlBRMQtPn0&index=4
https://crypto.stanford.edu/cs355/18sp/lec9.pdf
https://eprint.iacr.org/2015/939.pdf