---
title: Lattices
description: 各種加解密
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Intro
* 其實 Lattices 不是一種非對稱加解密系統, 但某些非對稱加解密系統可以被轉換成 Lattices 問題, 然後被解開
* 這邊會提出一個簡易的非對稱加解密系統, 然後解釋是怎麼被破解的

## Key Creation
* 選取大正整數 $q$
* 選取另兩個正整數 $f, g$, 並且符合以下式子

$$
f < \sqrt{q/2} \\
\sqrt{q/r} < g < \sqrt{q/2} \\
gcd(f, qg) = 1
$$

* 計算 $h$

$$
h \equiv f^{-1}g \mod q
$$

* public key 為 $q, h$
* private key 為 $f, g$

## Encryption
* 要送 $m$ 也須限制

$$
0 < m < \sqrt{q/4}
$$

* 隨機選擇 $r$, 滿足以下限制

$$
0 < r < \sqrt{q/2}
$$

* 密文產生方式如下

$$
e \equiv rh + m \mod q
$$

* $e$ 就是密文

## Decryption
* 計算以下式子即可得到 $m$

$$
a \equiv fe \mod q
$$

$$
m \equiv f^{-1}a \mod g
$$

## Correctness
$$
\begin{split}
a &\equiv fe \mod q\\
&\equiv f(rh + m) \\
&\equiv frh + fm \\
&\equiv frf^{-1}g + fm \\
&\equiv rg + fm
\end{split}
$$

* $f, g, r, m$ 的 size 根據以上的限制, 會符合以下

$$
rg + fm < \sqrt{\frac{q}{2}}\sqrt{\frac{q}{2}} + \sqrt{\frac{q}{2}}\sqrt{\frac{q}{4}} < q
$$

* 因此 $a = rg + fm$

$$
\begin{split}
f^{-1}a &\equiv f^{-1}(rg + fm) \mod g\\
&\equiv f^{-1}fm \\
&\equiv m
\end{split}
$$

* 因為以上的限制, 符合以下

$$
m < \sqrt{\frac{q}{4}} < g
$$

* 因此求出的 $m$ 不受 $\mod g$ 影響

## Cryptanalysis
* 暴力破解: O(q)
* 把每個 $a$ 都試一遍
* 如果攻擊者取得一組 $F, G$ 滿足以下

$$
\begin{split}
Fh &\equiv G \mod q \\
F, G &= O(\sqrt{q})
\end{split}
$$

* $F, G$ 就有很高的機會是真正的 private key $f, g$
* 第一式很好理解, 若真的是 private key 一定符合
* 第二式意思是 $F, G$ 符合限制

* 將以下式子

$$
Fh \equiv G \mod q
$$

* 改寫成
$$
Fh = G + qR
$$

* 問題轉變成以下向量運算

$$
F(1, h) - R(0, q) = (F, G)
$$

* 解釋一下
* 對於 x 軸: $F*1 - R*0 = F$
* 對於 y 軸: $F*h - Rq = G$
* 可看成
* $F, R$ 是未知的整數
* $(1, h), (0, q)$ 是已知的向量
* $(F, G)$ 是未知的向量
* 問題巧妙地變成 Lattices 的形式
* $w = a_1v_1 + a_2v_2$
* $w$ 長度為 $O(\sqrt{q})$
* $L = \{a_1v_1 + a_2v_2:a_1, a_2 \in Z\}$
* 有速解

## Lattices
* 設 $v_1, v_2, ..., v_n \in R^m$ 是一組線性獨立的向量
* 定義 lattices L 為以下

$$
L = \{a_1v_1 + a_2v_2 + ... + a_nv_n | a1, a2, ..., a_n \in Z\}
$$

* 由於 $a_1, a_2, ..., a_n$ 皆為整數, 所以 L 的圖形為一堆點


## Gaussian Lattice Reduction
* 假設有兩個 2d 向量 $v_1, v_2$
* 假設 $||v_1|| < ||v_2||$
* 目的是在 $L$ 中找到一個更短的向量
* 由 $v_1, v_2$ 當 basis, 要找到更短的向量, 可以怎做呢
* 
* 將 $v2$ 減去對於 $v1$ 方向的投影量

$$
v_2^* = v_2 - \frac{v1 \cdot v2}{||v_1||^2}v_1
$$

* 但 $v_2^*$ 不太可能在 $L$ 中
* 比較好的方式是四捨五入一下, 如下

$$
v_2^* = v_2 - \lfloor \frac{v_1 \cdot v_2}{||v_1||^2} \rceil v_1
$$