Điểm:2

Có gì sai với Quảng trường Trung PRNG?

lá cờ tf
Tom

Theo bài viết:

https://www.pcg-random.org/posts/too-big-to-fail.html

Khi N của Hình vuông ở giữa là $2^{128}$ chúng ta có thể mong đợi để sản xuất $2^{64.3}$ số trước khi chúng tôi bắt đầu thấy lặp lại trong trình tạo. Thế là đủ cho 320 exabyte dữ liệu ngẫu nhiên, nhiều hơn bất kỳ bài kiểm tra PractRand nào từng tiêu thụ.

Đây là kích thước đủ của đường dẫn để đạt đến chu kỳ và tự chu kỳ. Nó vượt qua các bài kiểm tra tính ngẫu nhiên và có lẽ nó khá nhanh. Vì vậy, có điều gì đó không ổn với Middle Square đủ lớn? Đặc biệt là nếu chúng tôi không phàn nàn về tốc độ và yêu cầu của phép toán 256-bit.

Mellisa O'Neil đã viết rằng nếu một trình tạo là một ánh xạ ngẫu nhiên, thì sẽ có một số rủi ro về trạng thái xấu và chu kỳ ngắn. Nhưng xác suất đó trong trường hợp này là bao nhiêu? Có vẻ như nó rất nhỏ, dù sao tôi cũng không thể chứng minh điều đó.

fgrieu avatar
lá cờ ng
Chất lượng của PRNG hình vuông ở giữa với trạng thái bit $n$ sẽ phụ thuộc rất nhiều vào cách đầu ra của nó được định nghĩa là một chức năng của trạng thái của nó và ở mức độ thấp hơn về cách nó được khởi tạo từ khóa của nó.Bạn đã giải quyết về điều đó? Một cách độc lập; kích thước chu kỳ dự kiến ​​$2^{64,3}$ dường như được suy ra bởi _giả định_ rằng hàm được lặp lại hoạt động giống như một hàm ngẫu nhiên giả ngẫu nhiên từ và đến tập hợp các chuỗi bit 128 bit; do đó đưa ra kết luận về chất lượng của PRNG hình vuông ở giữa từ con số đó phần lớn là một đối số vòng tròn. Thức ăn cho suy nghĩ: có bao nhiêu tiền đề của số 0?
Tom avatar
lá cờ tf
Tom
@fgrieu nhưng đối số vòng tròn này xuất hiện trong trường hợp của mọi trình tạo PRNG. Tất nhiên, trong hầu hết các trình tạo, chúng tôi biết khoảng thời gian, nhưng chúng tôi không thể có bằng chứng rằng chúng sẽ hoạt động tốt với nhiều terabyte dữ liệu. Chúng ta cần tin vào hành vi tốt. Và chúng tôi tin. Tương tự, nếu chúng tôi chứng minh hoạt động tốt của Middle Square đối với terabyte dữ liệu đầu tiên, thì không có lý do chính đáng nào để sợ rằng nó sẽ thất bại với lượng dữ liệu lớn hơn và nó sẽ có thời gian ngắn. Vì chúng tôi hợp pháp hóa chất lượng của các trình tạo khác bằng niềm tin đối với lượng dữ liệu lớn, tại sao không làm điều đó cho độ dài chu kỳ Quảng trường Trung bình.
lá cờ cn
@Tom Bạn có khẳng định rằng loại "đối số vòng tròn" này áp dụng cho "mọi trình tạo PRNG" dựa trên sự hiểu biết về toán học hay dựa trên ý kiến ​​​​cá nhân của riêng bạn về những gì có thể xảy ra không? Chắc chắn, có *một số* trình tạo PNRG khủng khiếp ngoài kia, nhưng "một số" không giống với "tất cả".
Điểm:6
lá cờ ru

Tuyên bố "chúng tôi hy vọng sẽ sản xuất $2^{64.3}$ các số trước khi chúng tôi bắt đầu lặp lại" chỉ đúng nếu chúng tôi tin rằng Hình vuông ở giữa 128 bit hoạt động giống như một ánh xạ ngẫu nhiên trên $\{0,1\}^{128}$. Tuy nhiên, chúng tôi có thể chỉ ra rằng nó có các thuộc tính rất khó xảy ra đối với ánh xạ ngẫu nhiên.

Nhớ lại rằng Middle Square 128-bit duy trì trạng thái 128-bit $S_t$. Cập nhật được thực hiện một cách hiệu quả bằng cách bình phương $S_t$và lấy bit 64-191 làm bit mới $S_{t+1}$ I E. $$S_{t+1}=(S_t^2>>64)\%2^{128}.$$

Nhà nước $S_t=0$ đại diện cho một điểm cố định. Mặc dù các ánh xạ ngẫu nhiên có các điểm cố định với xác suất xấp xỉ $(1-1/e)$, đây là một điều không bình thường vì nó có một số lượng lớn tiền ảnh. Bất kỳ số nào $S<2^{32}$ sẽ ánh xạ tới 0 cũng như bất kỳ số nào $S$ chia hết cho $2^{96}$. Tổng cộng những hình ảnh trước này (có thể có những hình ảnh khác) $2^{33}$ khi đối với một bản đồ ngẫu nhiên lớn, chúng tôi mong đợi số lượng tiền ảnh được phân phối Poisson (1). Hơn nữa, nếu chúng ta xem xét những người tiền nhiệm, bất kỳ số nào $S<2^{64}$ sẽ ánh xạ tới một số nhỏ hơn và số nhỏ hơn $2^{63}$ sẽ đạt 0 trong ít hơn 6 bước. Tương tự cho các số chia hết cho $2^{65}$. Điều này mang lại ít nhất $2^{64}$ trạng thái tiền thân cho 0 khi một bản đồ ngẫu nhiên mong đợi $2^{64}\sqrt{\pi/8}$ (với thời gian hợp nhất như nhau). Số lượng các trạng thái tiền nhiệm còn tăng nhiều hơn khi chúng ta xem xét các trạng thái tiền thân có thể có của các trạng thái được bảo đảm của chúng ta. $2^{64}$ các trạng thái tiền nhiệm, nếu mỗi trạng thái này có $2^{64}\sqrt{\pi/8}$ những người tiền nhiệm, chúng ta có thể thấy một tỷ lệ dương không gian của chúng ta suy biến về trạng thái 0.

Cũng tồn tại một không gian con được bảo toàn của số chia hết cho $2^{64}$ (không gian này có kích thước $2^{63}$) mà chúng tôi có thể mong đợi để hiển thị số liệu thống kê ánh xạ ngẫu nhiên cho không gian nhỏ hơn (ví dụ:chiều dài chu kỳ của $2^{31.5}\sqrt{\pi/8}$). Sau đó, chúng tôi xem xét các tiền thân cho không gian con này và tạo ra các kỳ vọng khác biệt đáng kể so với ánh xạ ngẫu nhiên đầy đủ.

Nhìn chung, các cấu trúc này rất không điển hình của ánh xạ ngẫu nhiên và chúng ta nên kết luận rằng ánh xạ ngẫu nhiên không phải là một mô hình tốt trong trường hợp này.

Tom avatar
lá cờ tf
Tom
Ok, hầu hết các nghi ngờ của tôi là - nếu điều này quá gần với ánh xạ ngẫu nhiên, thì có gì sai. Bây giờ tôi hiểu rõ hơn rằng chúng ta có những sai lệch so với ánh xạ ngẫu nhiên và ngay cả khi nó hoạt động giống như ánh xạ ngẫu nhiên, chúng ta vẫn có một loại đối số vòng tròn ở đây.
fgrieu avatar
lá cờ ng
Ngay từ [ENIAC](https://en.wikipedia.org/wiki/ENIAC), người ta đã biết rằng các thuộc tính của phương pháp bình phương trung bình của Von Neumann được phân tích trong câu trả lời này dẫn đến các chu kỳ ngắn khi được lặp lại. Tập 2 TAOCP của Knuth tuyên bố _"dãy có xu hướng đi vào lối mòn, một chu kỳ ngắn của các phần tử lặp lại. (â¦) N. Metropolis đã thực hiện nhiều thử nghiệm sâu rộng hơn, chủ yếu là trong hệ thống số nhị phân. Ông đã chỉ ra điều đó khi Các số 20 bit đang được sử dụng, có 13 chu kỳ khác nhau trong đó chuỗi hình vuông ở giữa có thể suy biến, chu kỳ dài nhất có chu kỳ dài 142"_.
Điểm:4
lá cờ ng

Đọc trang được liên kết trong câu hỏi: nó thừa nhận rằng phương pháp hình vuông ở giữa cơ bản dẫn đến các chu kỳ ngắn, giải thích lý do tại sao (cũng như điều này câu trả lời khác) và đề xuất một biến thể "Meddle square" để lặp lại $x\mapsto g(x):=2^n-1-\left\lfloor x^2/2^{\left\lfloor n/2\right\rfloor}\right\rfloor\bmod 2^n$ thay vì $x\mapsto f(x):=\left\lfloor x^2/2^{\left\lfloor n/2\right\rfloor}\right\rfloor\bmod 2^n$.

Biến thể này loại bỏ bất kỳ điểm cố định rõ ràng nào và quan trọng hơn là bất kỳ loại điểm lớn rõ ràng nào bị ràng buộc sẽ nhanh chóng rơi vào một chu kỳ ngắn. Đây là một cải tiến. Tuy nhiên:

  • Nếu chúng ta xuất trạng thái đầy đủ của trình tạo ở mỗi bước, thì nó khá hiệu quả (để triển khai thành thạo trên máy có hệ số nhân nhanh), nhưng có thể dự đoán được một cách tầm thường từ đầu ra trong quá khứ, do đó không an toàn về mặt mật mã. Tôi thấy tuyên bố của bài báo rất đáng tin cậy rằng (đối với $n=128$) Meddle square vượt qua tất cả các bài kiểm tra thống kê tiêu chuẩn. Đây là một minh họa rằng các thử nghiệm thống kê tiêu chuẩn đối với đầu ra của PRNG là vô nghĩa khi lập luận rằng đó là CSPRNG. Và thực sự, bài báo dường như giới thiệu hình vuông Meddle một cách chính xác để minh họa rằng việc có một trạng thái lớn không có điểm cố định hoặc chu kỳ hấp thụ rõ ràng và vượt qua các bài kiểm tra không phải là tiêu chí bảo mật hợp lệ cho CSPRNG.
  • Nếu chúng ta xuất một bit, Hình vuông giữa và các biến thể là $n$ kém hiệu quả hơn nhiều lần và chúng tôi vẫn chưa có lập luận chắc chắn rằng đó là CSPRNG. Thực tế là, chúng ta có thể dễ dàng tạo một PRNG lặp lại một hàm thay đổi trạng thái lớn của nó, tạo ra một bit duy nhất của trạng thái đó ở mỗi bước, vượt qua tất cả các bài kiểm tra tiêu chuẩn, nhưng cuối cùng lại rò rỉ trạng thái đầy đủ của chúng và do đó không an toàn về mặt mật mã.
  • Chúng ta có thể giải quyết một nền tảng trung bình, chẳng hạn như trạng thái 256 bit trong đó 64 bit được xuất ra ở mỗi giai đoạn. Điều đó có thể lấy lại nhiều hiệu quả, nhưng nếu không thử, tôi không chắc chắn về mức độ so sánh thông lượng với ví dụ:. Chacha; và tôi muốn nói rằng việc triển khai hiệu quả đúng là khó hơn nhiều.
  • Vì bất kỳ trình tạo nào dựa trên việc lặp lại hàm giả ngẫu nhiên, nên không thể tua nhanh trình tạo, điều này khiến nó không phù hợp với nhiều ứng dụng (như mật mã luồng cho lượng lớn dữ liệu hỗ trợ truy cập đọc ngẫu nhiên*).

Tóm lại: Middle Square PRNG, và thậm chí biến thể cải tiến của nó là Meddle Square, đều sai vì:

  1. Họ thiếu một đối số bảo mật hợp lý, trong bất kỳ biến thể nào. Thế là đủ.
  2. Chúng không an toàn một cách tầm thường khi chúng tôi đưa ra trạng thái đầy đủ của chúng ở mỗi bước.
  3. Khi chúng ta tạo ra ít trạng thái hơn, chúng sẽ trở nên kém hiệu quả hơn.
  4. Không có quyền truy cập trực tiếp* đến luồng được tạo, một thuộc tính hữu ích của nhiều CSPRNG.

* Đó là, khả năng tính toán hiệu quả các $j^\text{th}$ đầu ra của máy phát điện lớn $j$, với nỗ lực về cơ bản không phụ thuộc vào mức độ lớn $j$ Là. Điều này có ích khi $j$ là một chỉ mục trong một bộ phim khổng lồ được mã hóa bằng XOR với đầu ra của trình tạo và chúng tôi muốn bắt đầu xem phần ba cuối cùng của bộ phim.

Tom avatar
lá cờ tf
Tom
Truy cập trực tiếp vào luồng được tạo là gì?
fgrieu avatar
lá cờ ng
@Tom: xem * trong câu trả lời được cập nhật.

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