### RSA

#### [题解分析]

Encode

Attack on r ($e_{i},n_{i},c_{i}$)s with Common d($d<N_{r}^{\delta}$)

https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf

$N_{1}<N_{2}<…<N_{r}<2N_{1}$ with Common $d<N_{r}^{\delta}$. And all each modulus is balanced so that $s=p+q-1<\frac{3\sqrt{2}}{2}N_{r}^{1/2}<3N^{1/2}.$ Then we have r equations: $e_{i}d-N_{i}k_{i}=1-k_{i}s_{i}$.

Let vector A = $[d,k_{1},k_{2}…,k_{r}]$, $M=ceil(N_{r}^{1/2})$, matrix B =

$C=AB=[dM,1-k_{1}s_{1},1-k_{2}s_{2},…,1-k_{r}s_{r}]$.

$|C|<N_{r}^{\frac{1}{2}+\delta}\sqrt{1+9r}$.

$\sqrt{r+1}det(B)^{\frac{1}{r+1}}>\sqrt{r+1}N_{1}^{\frac{r+\frac{1}{2}}{r+1}}>\sqrt{r+1}(\frac{N_{r}}{2})^{\frac{r+\frac{1}{2}}{r+1}}$.

Then we wanna $N_{r}^{\frac{1}{2}+\delta}\sqrt{1+9r}<\sqrt{r+1}(\frac{N_{r}}{2})^{\frac{r+\frac{1}{2}}{r+1}}\Leftrightarrow N_{r}^{\delta-\frac{r}{2r+2}}<\frac{\sqrt{\frac{r+1}{9r+1}}}{2^{\frac{2r+1}{2r+2}}}$.

Cuz $r\geq 1$, the right side $>\frac{1}{6}$. So if

the Minkowski satisfies.

size(d) = 385时，从原理上有一定失败几率，但能很容易交互出size(d)满足Minkowski界的d. (e.g. size(d)=380)

### Lattice

#### [题解分析]

NTRU - Nth Degree Truncated Polynomial Ring Units

$R=Z[x]/(x^{n}-1)$: quotient

• $0^{th}$ step. Variable and Func prepared

• $1^{st}$ step. Key Generation

Select a prime p and genkey with the func below,

• $2^{nd}$ step. Encryption

• $3^{rd}$ step. Decryption

Explain why it works,

On Zmod(q), $c=hr+m=pgfqr+m$.

$a=cf=pg(ffq)r+fm=pgr+f*m$.

$afp=pgrfp+(ffp)m$, and it equals to m on Zmod(p).

当$pgr+fm$在Zmod(q)上和ZZ上完全等价，或是说该多项式系数均落在$(-q/2,q/2)$时，解密可行性成立，个人做粗略参数估计后发现应满足$2d(p+1)<q$（有paper上给出*p(6d+1)<q，但证明暂时没时间看ojz）

On Zmod(q), $h=pgfq=p*g/f$.

Let $hp=pp^{-1}g/f$, so we have $g=f*hp$.

f’s coef $\in \{-1,0,1\}$, this means g is obtained as a combination of the polys $q,qx,qx^{2},…,qx^{n-1},hp,hpx,hpx^{2},…,hp*x^{n-1}$.

Assume $hp=\sum a_{i}x^{i}$,