Logarit rời rạc trong mô hình nhóm chung là khó - Định lý của Shoup

einsteinwein

06:32, 20/02/2023

Trong bài báo nổi tiếng của Shoups Giới hạn dưới cho logarit rời rạc và các vấn đề liên quan ông chứng minh rằng Bài toán logarit rời rạc là khó trong mô hình nhóm chung (nếu phép toán nhóm và phép toán nghịch đảo là phép tính duy nhất có thể được thực hiện trên các phần tử nhóm). Định lý 1 trong bài báo nói rằng xác suất mà một thuật toán tổng quát $A$ giải quyết vấn đề này được giới hạn bởi $\mathcal{O}(m^2/p)$ (m là số truy vấn tiên tri, p là thứ tự nhóm nguyên tố). Phần mà tôi không hiểu là như sau:

Nếu chúng ta nhấn mạnh rằng $A$ thành công với xác suất bị giới hạn bởi một hằng số dương (ví dụ: 1/2) đến giá trị bên dưới, định lý này chuyển thành giới hạn dưới $\Omega(\sqrt{p})$ về số lượng hoạt động nhóm được truy vấn bởi $A$.

Ai đó có thể giải thích kết luận này cho tôi?

132

0 + 0

logarit rời rạc

ggm

Điểm:5

Crypto

Ievgeni

06:42, 20/02/2023

Để cho $K$ là hằng số (không phụ thuộc vào $p$) sao cho xác suất bị giới hạn bởi $K\frac{m^2}{p}$. (một ví dụ $K$ tồn tại theo định nghĩa của $\mathcal{O}$).

Điều đó có nghĩa là nếu một đối thủ giải bài toán logarit rời rạc với xác suất lớn hơn $\frac{1}{2}$, chúng tôi đạt được.

$$K\frac{m^2}{p}\geq \frac{1}{2}$$.

Nó ngụ ý rằng

$$m\geq \sqrt{\frac{p}{2K}} $$

Như vậy ta suy ra rằng $m$ -Đó thực sự là một chức năng của $p$, bị chặn dưới bởi $K'\sqrt{p}$, với $K':=\sqrt{\frac{1}{2K}}$ một hằng số không phụ thuộc vào $p$.

Nó tương đương với viết $m\in \Omega(\sqrt{p})$ (theo ký hiệu Knuth).

Bây giờ chú ý rằng $\sqrt{p}$ là cấp số nhân theo kích thước của đầu vào và bạn sẽ suy luận rằng bất kỳ đối thủ chung nào đều không hiệu quả đối với DLog.

0 + 0

einsteinwein

14:05, 20/02/2023

Cám ơn rất nhiều! :-)

Hồi đáp

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: Discrete Logarithm in the generic group model is hard - Theorem by Shoup

TH: ลอการิทึมแบบไม่ต่อเนื่องในแบบจำลองกลุ่มทั่วไปนั้นยาก - ทฤษฎีบทโดย Shoup

RO: Logaritmul discret în modelul de grup generic este greu - Teorema lui Shoup

RU: Дискретный логарифм в общей групповой модели сложен - Теорема Шоупа

VI: Logarit rời rạc trong mô hình nhóm chung là khó - Định lý của Shoup

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