问题简述
\(\text{ECHNP}\)
给定质数\(p\)、一正整数\(m\)、一\(\mathbb{F}_{p^m}\)上的椭圆曲线\(E\)，点\(Q\in{E}\)，以及由\(Q\)生成的点\(R\in{\langle Q\rangle}\)，设\(f\)为一个\(E\)上的函数，\(P\)为\(E\)上一未知点，并设一预言机\(\mathcal{O}_{P,R}(t)\)，其输入为\(t\)，输出为：
$$
\mathcal{O}_{P,R}(t)=f(P+tR)
$$
那么椭圆曲线隐藏数问题（\(\text{ECHNP}\)）则是通过预言机\(\mathcal{O}_{P,R}(t)\)的若干个输出来恢复点\(P\).
而对于\(m=1\)，且函数\(f(X)=\text{MSB}_k(X_{\psi})\)（即取点\(X\)的\(\psi\)-坐标的高\(k\)位，其中\(\psi\in{x,y}\)），则有\(\text{ECHNP}_{\psi}\)：
\(\text{ECHNP}_{\psi}\)
给定质数\(p\)、正整数\(k\)、一\(\mathbb{F}_{p}\)上的椭圆曲线\(E\)，点\(Q\in{E}\)，以及由\(Q\)生成的点\(R\in{\langle Q\rangle}\)，设\(P\)为\(E\)上一未知点，并设一预言机\(\mathcal{O}_{P,R}(t)\)，其输入为\(t\)，输出为：
$$
\mathcal{O}_{P,R}(t)=\text{MSB}_k((P+tR)_{\psi})
$$
那么\(\text{ECHNP}_{\psi}\)则是通过预言机\(\mathcal{O}_{P,R}(t)\)的若干个输出来恢复点\(P\).
求解\(\text{ECHNP}_{x}\)
存在一种多项式时间的算法来求解\(k>\frac{5}{6}\log{p}\)情况下的\(\text{ECHNP}_{x}\).
以下讨论均建立在Weierstrass方程定义的椭圆曲线上.
根据椭圆曲线相异点的加法可以知道，对于曲线上两相异点\(P(x_P,y_P),Q(x_Q,y_Q)\)，其和\(P+Q\)的横坐标计算如下：
$$
x_{P+Q}=\left(\frac{y_Q-y_P}{x_Q-x_P}\right)^2-x_P-x_Q
$$
所以可以知道：
$$
\mathcal{O}_{P,R}(t)=\text{MSB}_k((P+tR)_{x})=\text{MSB}_k\left(\left(\frac{y_{tR}-y_P}{x_{tR}-x_P}\right)^2-x_P-x_{tR}\mod{p}\right)
$$
而MSB也可以等价于减去一个较小量\(e\)，那么可以得到：
$$
\mathcal{O}_{P,R}(t)=\text{MSB}_k\left(\left(\frac{y_{tR}-y_P}{x_{tR}-x_P}\right)^2-x_P-x_{tR}\mod{p}\right)=\left(\frac{y_{tR}-y_P}{x_{tR}-x_P}\right)^2-x_P-x_{tR}-e\mod{p}
$$
其中\(|e|\le p/2^{k+1}\)，我们令\(h=\mathcal{O}_{P,R}(t)\)，则可以得到：
$$
h\equiv\left(\frac{y_{tR}-y_P}{x_{tR}-x_P}\right)^2-x_P-x_{tR}-e\pmod{p}
$$
可将\(x\)坐标与\(y\)坐标分别移到等号两边：
$$
(h+x_P+x_{tR}+e)(x_{tR}-x_P)^2\equiv(y_{tR}-y_P)^2\equiv y_{tR}^2-2y_{tR}y_{P}+y_{P}^2\pmod{p}
$$
而因为\(y_P^2\equiv x_P^3+ax_P+b\pmod{p}\)，则有：
$$
(h+x_P+x_{tR}+e)(x_{tR}-x_P)^2\equiv(y_{tR}-y_P)^2\equiv y_{tR}^2-2y_{tR}y_{P}+x_P^3+ax_P+b\pmod{p}
$$
然而上面有我们并不期望出现的\(y_P\)，故我们需要进行消元，对于任一正整数\(t\)，令\(Q=tR\)，我们可以通过预言机得到\((P+Q)_x\)以及\((P-Q)_x\)的MSB，而在\(\mathbb{F}_p\)上有：
$$
\begin{aligned}
(P+Q)_x+(P-Q)_x&=\left(\frac{y_P-y_Q}{x_P-x_Q}\right)^2-x_P-x_Q+\left(\frac{y_P+y_Q}{x_P-x_Q}\right)^2-x_P-x_Q\\
&=\frac{2(y_P^2+y_Q^2)}{(x_P-x_Q)^2}-2x_P-2x_Q\\
&=2\left(\frac{x_Qx_P^2+(a+x_Q^2)x_P+ax_Q+2b}{(x_P-x_Q)^2}\right)
\end{aligned}
$$
我们令\(h=\mathcal{O}_{P,R}(t)=(P+Q)_x-e,h’=\mathcal{O}_{P,R}(-t)=(P-Q)_x-e’\)，并令\(\widetilde{h}=h+h’,\widetilde{e}=e+e’\)，由上面的推导可以得到：\(\widetilde{h}+\widetilde{e}=(P+Q)_x+(P-Q)_x\)，又因为当\(t=0\)的时候，有\(\mathcal{O}_{P,R}(0)=x_P-e_0\)（其中\(e_0\)为一整数），那么我们记\(h_0=\mathcal{O}_{P,R}(0)\)，则有\(x_P=h_0+e_0\)，综合上述推导就可以得到：
$$
\begin{aligned}
\widetilde{h}+\widetilde{e}&=(P+Q)_x+(P-Q)_x\\
&=2\left(\frac{x_Qx_P^2+(a+x_Q^2)x_P+ax_Q+2b}{(x_P-x_Q)^2}\right)\\
&=2\left(\frac{x_Q(h_0+e_0)^2+(a+x_Q^2)(h_0+e_0)+ax_Q+2b}{(h_0+e_0-x_Q)^2}\right)
\end{aligned}
$$
显然的，上式中只有\(e_0,\widetilde{e}\)是未知的，我们令两边乘上\((h_0+e_0-x_Q)^2\)可以得到：
$$
(\widetilde{h}+\widetilde{e})(h_0+e_0-x_Q)^2=2(x_Q(h_0+e_0)^2+(a+x_Q^2)(h_0+e_0)+ax_Q+2b)
$$
从而可以从中得到一个多项式：
$$
F(X,Y)=(\widetilde{h}+Y)(h_0-x_Q+X)^2-2(x_Q(h_0+X)^2+(a+x_Q^2)(h_0+X)+ax_Q+2b)
$$
展开整理则有：
$$
\begin{aligned}
F(X,Y)=&X^2Y+(\widetilde{h}-2x_Q)X^2+2(h_0-x_Q)XY+2[\widetilde{h}(h_0-x_Q)-2h_0x_Q-a-x_Q^2]X\\
&+(h_0-x_Q)^2Y+[\widetilde{h}(h_0-x_Q)^2-2h_0^2x_Q-2(a+x_Q)h_0-2ax_Q-4b]
\end{aligned}
$$
很显然，该多项式满足\(F(e_0,\widetilde{e})\equiv0\pmod{p}\)，根据上述方法，我们取\(n\)组\((\mathcal{O}_{P,R}(t_i),\mathcal{O}_{P,R}(-t_i))=(h_i,h_i’)\)进行上述操作就可以得到\(n\)个多项式：
$$
F_i(X,Y)=X^2Y+A_iX^2+A_{0,i}XY+B_iX+B_{0,i}Y+C_i
$$
满足\(F_i(e_0,\widetilde{e}_i)\equiv0\pmod{p}\)，其中：
$$
\begin{aligned}
A_i&=\widetilde{h}_i-2x_{Q_i}\\
A_{0,i}&=2(h_0-x_{Q_i})\\
B_i&=2[\widetilde{h}_i(h_0-x_{Q_i})-2h_0x_{Q_i}-a-x_{Q_i}^2]\\
B_{0,i}&=(h_0-x_{Q_i})^2\\
C_i&=\widetilde{h}_i(h_0-x_{Q_i})^2-2h_0^2x_{Q_i}-2(a+x_{Q_i}^2)h_0-2ax_{Q_i}-4b
\end{aligned}
$$
此时可以构造矩阵：
$$
M=\left(\begin{matrix}
\Delta_1&0&M_1\\
0&\Delta_2&M_2\\
0&0&pI
\end{matrix}\right)
$$
其中\(\Delta_1,\Delta_2\)的定义如下：
$$
\Delta_1=diag(
2^{3k},\underbrace{2^{2k},\cdots,2^{2k}}_{n+1个}), \Delta_2=2^kI_{n+1}
$$
而\(M_1,M_2\)定义如下：
$$
M_1=\left(\begin{matrix}
-C_1&-C_2&\cdots&-C_n\\
-B_1&-B_2&\cdots&-B_n\\
-B_{0,1}&&\\
&-B_{0,2}&\\
&&\ddots&\\
&&&-B_{0,n}
\end{matrix}\right),
M_2=\left(\begin{matrix}
-A_1&-A_2&\cdots&-A_n\\
-A_{0,1}&&\\
&-A_{0,2}&\\
&&\ddots&\\
&&&-A_{0,n}
\end{matrix}\right)
$$
则存在向量\(v=(1,e_0,\widetilde{e}_1,\cdots,\widetilde{e}_n,e_0^2,e_0\widetilde{e}_1,\cdots,e_0\widetilde{e}_n,k_1,\cdots,k_n)\)使得：
$$
vM=(2^{3k},2^{2k}e_0,2^{2k}\widetilde{e}_1,\cdots,2^{2k}\widetilde{e}_n,2^ke_0^2,2^ke_0\widetilde{e}_1,\cdots,2^ke_0\widetilde{e}_n,e_0^2\widetilde{e}_1,\cdots,e_0^2\widetilde{e}_n)
$$
很容易可以证明上述向量可以通过规约得出，求解代码模板如下：
from Crypto.Util.number import *
from tqdm import *
from sage.all import *
p = ...
a = ...
b = ...
x, y = (..., ...)
E = EllipticCurve(GF(p), [a, b])
R = E(x, y)
h0 = ...
A = []
A0 = []
B = []
B0 = []
C = []
n = ...
k = ...
K = 2**k
for i in trange(n):
t = i + 1
xQ = ZZ((t*R)[0])
# 从预言机中获得P + tR的x坐标高位
h1 = ...
# 从预言机中获得P - tR的x坐标高位
h2 = ...
H = (h1 + h2) % p
Ai = (H - 2*xQ)
A0i = 2*(h0 - xQ)
Bi = 2*(H*(h0 - xQ) - 2*h0*xQ - a - xQ**2)
B0i = (h0 - xQ)**2
Ci = (H*(h0 - xQ)**2 - 2*h0**2*xQ - 2*(a + xQ**2)*h0 - 2*a*xQ - 4*b)
A.append(Ai)
A0.append(A0i)
B.append(Bi)
B0.append(B0i)
C.append(Ci)
Delta1 = matrix(ZZ, n+2, n+2)
Delta1[0, 0] = K**3
for i in range(1, n+2):
Delta1[i, i] = K**2
Delta2 = matrix(ZZ, n+1, n+1)
for i in range(n+1):
Delta2[i, i] = K
M1 = matrix(ZZ, n+2, n)
for i in range(n):
M1[0, i] = -C[i]
M1[1, i] = -B[i]
M1[i+2, i] = -B0[i]
M2 = matrix(ZZ, n+1, n)
for i in range(n):
M2[0, i] = -A[i]
M2[i+1, i] = -A0[i]
L = block_matrix([[Delta1, 0, M1], [0, Delta2, M2], [0, 0, p]])
res = L.LLL()[0]
x0 = h0 + res[1] // (K**2)