Bộ phân biệt và bộ dự đoán bit tiếp theo không có phân phối đồng đều

Xem xét phân phối xác suất $D$ trên $n$ chuỗi bit. Chứng tỏ $U$ là phân phối đồng đều trên $n$ chuỗi bit và $U_{n}$ là phân phối đều trên các số nguyên $\{1, 2, \ldots, n\}$.

Xét hai mệnh đề tương đương sau (chúng tương đương theo định lý Yao):

1. Không có bộ dự đoán bit tiếp theo thời gian đa thức thống nhất $A$ như vậy mà $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq \frac{1} {2} + \frac{1}{\text{poly}(n)}. $$
2. Không có bộ phân biệt thời gian đa thức thống nhất $B$ như vậy mà $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim U}{\text{Pr}}[B(Y)=1]\ giữa \geq \frac{1}{\text{poly}(n)}. $$

Tôi đã suy nghĩ về tính trung tâm của việc phân phối đồng đều trong các khoản cắt giảm. Một số dạng của các câu lệnh này có hoạt động không khi chúng ta thay thế phân phối thống nhất bằng phân phối đã biết và có thể lấy mẫu hiệu quả $D_2$? Giả sử chúng ta cũng có thể lấy mẫu một cách hiệu quả từ mọi biên của $D_2$.

Nói cách khác, hãy xem xét Tuyên bố 3 như sau.

Tuyên bố 3: Không có bộ phân biệt thời gian đa thức thống nhất $B$ như vậy mà $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim D_2}{\text{Pr}}[B(Y)=1]\ giữa \geq \frac{1}{\text{poly}(n)}. $$

Điều này có ngụ ý và/hoặc được ngụ ý bởi Tuyên bố 4 như sau (hoặc một số biến thể của tuyên bố này) không?

Tuyên bố 4: Không có bộ dự đoán bit tiếp theo thời gian đa thức thống nhất $A$ như vậy mà $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq c, $$ ở đâu $c$ phụ thuộc vào sự phân bố $D_2$ và ưu điểm nổi bật của $B$.

Nếu vậy, chúng ta có thể có một hình thức rõ ràng cho $c$?

Câu hỏi hay!

Điều này dường như đã được giải quyết trong một hội nghị giấy cũng có sẵn đây của Schrift và Shamir năm 1991:

A.W. Schrift, A. Shamir, Về tính phổ biến của bài kiểm tra bit tiếp theo, Hội nghị về Lý thuyết và Ứng dụng của Mật mã học, 1990.

Có một phiên bản tạp chí sau này trong Tạp chí Mật mã.

Tóm lại, họ xem xét một nguồn bit thiên vị nhưng độc lập và làm thế nào để nghĩ ra một dấu hiệu phân biệt cho nó. Lưu ý rằng không mất tính tổng quát, chúng giả sử xác suất của một $1$ bit là $b\in (1/2,1)$ nhưng gọi số lượng $b$ sự thiện vị đó là một chút phản trực giác, so với việc sử dụng thiên vị truyền thống cho số lượng $b-\frac{1}{2}$.

Cụ thể, họ xác định tỷ lệ thành công có trọng số của bất kỳ thuật toán PPTA không cố định nào $$A:\{0,1\}^n\rightarrow \{0,1\}$$ trong việc dự đoán $i^{th}$ một chút của một nguồn thiên vị như

Ghi chú: ký hiệu $f<O(\nu(n))$ được sử dụng cho bất kỳ chức năng nào biến mất nhanh hơn bất kỳ đa thức nào sức mạnh đối ứng, tức là, bất kỳ biến mất chức năng.

Có một số thử nghiệm thay thế khác được đề xuất trong bài báo.

Bài báo này được trích dẫn khá nhiều, nhưng chủ yếu là bởi các bài báo áp dụng nó với nhiều nguồn khác nhau. Trên thực tế, có vẻ như chính các tác giả đã sử dụng kỹ thuật này để chứng minh kết quả về độ cứng của từng bit, bao gồm cả bit có ý nghĩa lớn nhất bị sai lệch bằng 0 đối với các bản ghi rời rạc modulo một số tổng hợp.