Tham gia Đăng nhập
Điểm:3
Leafar avatar Crypto

Làm cách nào để quyết định xem một phần tử có phải là khóa chung trong sơ đồ mã hóa NTRU không?

lá cờ ng
Leafar

Đầu tiên, tôi đang sử dụng cài đặt của https://en.wikipedia.org/wiki/NTRUEncrypt, với $L_f$ tập hợp các đa thức với $d_f+1$ hệ số bằng 1, $d_f$ tương đương với $-1$ và phần còn lại $N-2d_f-1$ bằng 0; và $L_g$ tập hợp các đa thức với $d_g$ hệ số bằng 1, $d_g$ tương đương với $-1$ và phần còn lại $N-2d_g$ bằng 0. Các số tự nhiên $d_f$ và $d_g$ chỉ là các tham số cố định của sơ đồ.

Giả sử một người nhận được một đa thức $h$ trong chiếc nhẫn $R_{N,q}=\mathbb{Z}_q[X]/\langle X^N-1 \rangle$.

Câu hỏi: Có thể xác định nếu $h$ là khóa công khai, nghĩa là có thể xác định xem $h$ có dạng $pf_q \cdot g \pmod{q}$?

Nỗ lực của tôi: Giả định về độ cứng của NTRU nói rằng từ $h$ người ta không thể xác định $f$ hoặc $g$, nếu không lược đồ sẽ vô dụng. Mặc dù tôi không thể trả lời câu hỏi của mình, tôi đã nghĩ ra một bài kiểm tra. Từ $g(1)=0$, chúng ta phải có $h(1)=0$. Do đó nếu $h(1) \neq 0$ sau đó $h$ không phải là khóa công khai. Chúng ta có thể kiểm tra thêm những gì?

Tái bút: Không có bằng chứng về kiến ​​thức không hoặc những thứ tương tự từ nguồn của $h$ được tặng.

304
0 + 0
Điểm:5
Mark avatar Crypto
lá cờ ng
Mark

Bạn không thể theo một giả định tiêu chuẩn được gọi là "Giả định NTRU quyết định". Đây thực chất là tuyên bố rằng các khóa công khai NTRU là giả ngẫu nhiên. Sau đây là định nghĩa 4.4.4 của Một thập kỷ của mật mã lưới.

Vấn đề học tập NTRU: Đối với một nghịch đảo $s\in R_q^*$, và phân phối $\chi$ trên $R$, định nghĩa $N_{s, \chi}$ là phân phối đầu ra $e/s\in R_q$ ở đâu $e\gets\chi$. Các Vấn đề học tập NTRU là: Cho các mẫu độc lập $a_i\in R_q$, trong đó mỗi mẫu được phân phối theo một trong hai

  1. $N_{s,\chi}$, đối với một số được chọn ngẫu nhiên $s\in R_q^*$ (cố định cho tất cả các mẫu), hoặc
  2. phân phối đồng đều, phân biệt đó là trường hợp (với lợi thế không đáng kể).

Lưu ý rằng vấn đề này về cơ bản nói rằng bạn không thể làm những gì bạn đang yêu cầu, tức là nói rằng các khóa NTRU không thể phân biệt được về mặt tính toán với ngẫu nhiên.

0 + 0
Leafar avatar
lá cờ ng
Leafar
Cảm ơn rất nhiều! Bây giờ tôi đã hiểu hơn, nhưng ở đây trong định nghĩa này, phân phối đồng đều được xác định trên tất cả $R_{N,q}$, điều này trái ngược với thử nghiệm mà tôi đã cung cấp. Hơn nữa, $\chi$ là một phân phối trên $L(d_g,d_g)$. Tôi có thể xác định điểm 2 là phân phối đồng đều trên $R_{N,q}$ ngoại trừ tất cả các đa thức được đánh giá ở mức 1 cho 0 không? Định nghĩa/giả định độ cứng này có đủ không?
0
Hồi đáp
Mark avatar
lá cờ ng
Mark
Bạn có thể chỉ cần xác định vành $R$ để có các đa thức đánh giá bằng 0 tại 1, ví dụ: đặt $R = \mathbb{Z}[x] / (x^n-1)$. Tuy nhiên, bạn không thể đơn phương thay đổi điểm 2, vì khi đó vấn đề phân biệt trở thành một vấn đề phân biệt khác.
0
Hồi đáp
Leafar avatar
lá cờ ng
Leafar
Tôi không thể vì các đa thức như vậy không bao giờ khả nghịch và điều này sẽ gây rối với $f$, trong câu trả lời của bạn là $s$, cần phải khả nghịch.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.