Điểm:0

Cộng số EC $P^3+c$ với 3 thế hệ $G$, $F = P\cdot G,H=P^2\cdot G$ và 2 thành viên ngẫu nhiên $M_1+iG+jF+kH=M_2$. Sẽ mất bao lâu để tìm $i,j,k$?

lá cờ at

Đưa ra một EC với cardinality $C=P^3+c$ với $P$ một số nguyên tố $P \approx \sqrt[3]{C}$$c>0$. Trong số một máy phát điện nhất định $G$ chúng tôi tạo ra hai máy phát điện bổ sung $F,H$ với $$F = P \cdot G$$ $$H = P^2 \cdot G$$

(tất cả vẫn sẽ tạo ra một chuỗi độ dài $P^3+c$)
Cho bây giờ một thành viên ngẫu nhiên $M_1$ của EC đó, chúng ta có thể tạo ra một $P\times P \times P$ khối lập phương của các thành viên khác nhau với $$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$ $$ i,j,k \in [0,P-1]$$ $$|\{V_{M_1ijk}\}| = P^3$$

Mọi thành viên ngẫu nhiên khác $M_2$ có thể được sản xuất ra khỏi $M_1$ với: $$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$ $$ i,j,k \in [0,P]$$


Câu hỏi:
Hiện có hai thành viên ngẫu nhiên $M_1,M_2 $ có bao nhiêu bước là cần thiết để tìm các liên quan $i,j,k$ (về thời gian trung bình)? Làm thế nào mà làm việc đó?
Sẽ (nhiều) an toàn hơn nếu chúng ta chọn $P = 2\cdot p+1$ với $p$ một số nguyên tố?
Sẽ (nhiều) an toàn hơn nếu chúng ta chọn ba thừa số nguyên tố (bí mật) $P_1,P_2,P_3$ thay thế? với $P_1 \cdot P_2 \cdot P_3 \approx C$

(Tôi đang tìm kiếm các ước tính sơ bộ liên quan đến $C,P$ Trong ($O$-ký hiệu). Chúng ta có thể ví dụ bỏ qua tác động khác nhau liên quan đến độ dài bit khi nhân 2 số)


kẻ thù không biết về EC đã sử dụng, máy phát điện $G,F,H$ và nghịch đảo của họ $G^{-1},F^{-1},H^{-1}$, các thành viên ngẫu nhiên $M_1,M_2$ và cấu trúc bên trong. Anh ấy không biết về $P,d$ nhưng vì không có quá nhiều lựa chọn nên chúng tôi cho rằng anh ấy cũng biết điều này.
Anh muốn tìm ẩn số $i,j,k$ để biết ngẫu nhiên $M_1,M_2$.


Câu hỏi phụ: Có bất kỳ hạn chế nào của EC an toàn có thể được sử dụng cho việc này không? Ví dụ. sẽ M-221 với $y^2 = x^3+117050x^2+x$ $\bmod p = 2^{221} - 3$ làm việc cho điều này?


Sự thử nghiệm:
Nếu chúng ta chỉ có một máy phát điện duy nhất $G$ nó nên mất $O(\sqrt{C})$ sử dụng baby-step-giant-step. Nếu $P$ đã được biết đến $i,j,k$ có thể được xây dựng từ điều này.
Với $F,H$ chúng ta có thể làm một bề mặt xung quanh $M_1$ và một đường thẳng với $G$ tại $M_2$ cho đến khi một giao điểm của những người. Điều này sẽ mất $O(P^2+P)\rightarrow O(P^2)$ cái nào sẽ lớn hơn $O(\sqrt{C})=O(P\sqrt{P})$. Cho nên $F,H$ không có sự giúp đỡ ở đây.
Có thể những máy phát điện $F,H$ giúp làm cho nó nhanh hơn bằng cách nào đó?

Điểm:1
lá cờ my

Hiện có hai thành viên ngẫu nhiên $M_1, M_2$ có bao nhiêu bước là cần thiết để tìm các liên quan $i,j,k$ (về thời gian trung bình)?

Vấn đề tìm $i, j, k$ tương đương với bài toán log rời rạc:

  • Nếu bạn có thể giải quyết vấn đề nhật ký rời rạc, bạn có thể tính toán $i, j, k$ (bằng cách tính log rời rạc của $M_2 - M_1$, sau đó thể hiện nhật ký rời rạc đó trong cơ sở $P$)

  • Nếu bạn có thể tính toán $i, j, k$, bạn có thể giải bài toán log rời rạc (để tính log rời rạc của một điểm M, bạn sẽ chọn một điểm tùy ý $M_1$, bộ $M_2 = M + M_1$, tính toán $i, j, k$; sau đó, nhật ký rời rạc của $M$$i + jP + kP^2$

Đối với một đường cong không có điểm yếu đã biết, việc tính toán nhật ký rời rạc được cho là mất $O(\sqrt{C})$ thời gian; nếu bạn chọn một đường cong có điểm yếu đã biết (ví dụ: đường cong thân thiện ghép nối có thao tác ghép nối vào trường hữu hạn nơi nhật ký rời rạc dễ dàng hơn), thì thời gian giải quyết vấn đề của bạn cũng giảm theo.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.