# Lattice learning 2

## Chapher 5 Encryption mode in Lattice

### Coppersmith

Coppersmith是啥？ $f(x_0)=0\pmod{b},x_0\leq cN^{\frac{\beta^2}{d}}$

$$Basis~functions{=\begin{bmatrix} 1\\x\\x^2\\x^3\\\vdots \end{bmatrix}} ~~ \frac{d}{dx}= {\begin{bmatrix} 0&1&0&0&\cdots\\ 0&0&2&0&\cdots\\ 0&0&0&3&\cdots\\ 0&0&0&0&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}}$$

#### 已知部分明文攻击

$b=N,d=e,\beta=1$ 则 $|x|\leq cN^{\frac{\beta^2}{d}}=cN^{\frac{1}{e}}$ ，因此为了求解，我们至少需要知道关于m至少 $(1-\frac{1}{e})\cdot N.bit_length()$ bit的信息

#### 已知部分因子攻击

$b=p$ ，且RSA中 $p$ 和 $q$ 通常是满足 $p<q<2p$ 所以 $p\approx N^{0.4}$ ，也就是说 $\beta=0.4$ 附近较为适合，另外 $|x|<N^{\frac{1}{3}}$ ，我们只要知道 $p$ 一半bit就可以求出这样的 $x$ 。

### 多消息攻击

#### 多消息相关攻击

Waiting for undate……

Waiting for undate……

#### SMUPE攻击

Waiting for undate……

### Boneh and Durfee attack

Waiting for undate……

### HNP (Hidden number problem)

$MSB_{l,p}(x)$ 表示的是任意一个满足 $|(x\ mod\ p)-u|\leq\frac{p}{2^{l+1}}$ 的 $u$ 。

$${\begin{cases} A_1\times x+B_1=y_1 \\ A_2\times y_1+B_2=y_2 \\ \cdots \\ A_n\times y_{n-1}+B_x=y_n \end{cases}} \pmod{m}$$

$$y_2=A_2\times y_1+B_2 \\ =A_2\times(A_1\times x+B_1)+B_2 \\ =A_1A_2\times x+A_2B_1+B_2 \\ =A_2’\times x+B_2’$$

$$M={\begin{bmatrix} m\\ &m\\ &&\ddots\\ &&&m\\ A_1&A_2’&\cdots&A_n’&1\\ B_1&B_2’&\cdots&B_n’&&base\\ \end{bmatrix}}$$

$$\vec{v}\cdot M ={\begin{bmatrix}k_1,k_2,\cdots,k_{n},x,1\end{bmatrix}}\cdot {\begin{bmatrix} m\\ &m\\ &&\ddots\\ &&&m\\ A_1&A_2’&\cdots&A_n’&1\\ B_1&B_2’&\cdots&B_n’&&base\\ \end{bmatrix}} ={\begin{bmatrix}y_1,y_2,\cdots,y_n,x,base\end{bmatrix}} =\vec{x}$$

### Knapsack (Lattice 0&1knapsack problem)

$$C = \sum_{i=1}^{n}{mbin_i(0\ or\ 1)\times M_i}$$

《An Introduction to Mathematical Cryptography-Springer-Verlag》一书中提到LLL方式在背包问题中的应用中构造的格子如下
$$B^{knapsack} = {\begin{bmatrix} 2&0&0&\cdots&0&m_1 \\ 0&2&0&\cdots&0&m_2 \\ 0&0&2&\cdots&0&m_3 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&\cdots&2&m_n \\ 1&1&1&\cdots&1&C \end{bmatrix}}$$
LLL后得到的第一个向量取反加一再除2后得到的就是合法的 $\vec{m}$

$$B^{knapsack’} = {\begin{bmatrix} 1&0&0&\cdots&0&m_1 \\ 0&1&0&\cdots&0&m_2 \\ 0&0&1&\cdots&0&m_3 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&\cdots&1&m_n \\ 0&0&0&\cdots&0&-C \end{bmatrix}}$$

### NTRU

Zx.<x>表示以 $x$ 为自变量的多项式，比如 $Zx([1,1,4,5,1,4])=1\cdot x^5+1\cdot x^4+5\cdot x^3+4\cdot x^2+1\cdot x+1$

NTRU中的乘法运算

（补上）非质数的倒数

NTRU密码系统的加密

#### Decrypt

NTRU密码系统的解密 #### Attack

$$B^{NTRU} = {\begin{bmatrix} \pmb{1}&\pmb{h(x)} \\ \pmb{0}&\pmb{q} \end{bmatrix}} = \begin{bmatrix} \begin{array}{lllll|lllll} 1&0&0&\cdots&0&h_0&h_1&h_2&\cdots&h_{n-1} \\ 0&1&0&\cdots&0&h_{n-1}&h_0&h_1&\cdots&h_{n-2} \\ 0&0&1&\cdots&0&h_{n-2}&h_{n-1}&h_0&\cdots&h_{n-3} \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots \\ 0&0&0&\cdots&1&h_1&h_2&h_3&\cdots&h_0 \\ \hline 0&0&0&\cdots&0&q&0&\cdots&0 \\ 0&0&0&\cdots&0&0&q&0&\cdots&0 \\ 0&0&0&\cdots&0&0&0&q&\cdots&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots \\ 0&0&0&\cdots&0&0&0&0&\cdots&q \\ \end{array} \end{bmatrix}$$

$$B^{NTRU}_{\theta} = {\begin{bmatrix} \pmb{1}&\pmb{\theta h(x)} \\ \pmb{0}&\pmb{q\theta} \end{bmatrix}}$$

### LWE (learning with error)

Waiting for undate……