Lợi thế của đối thủ chống lại một chức năng đơn giản?

Kẻ tấn công phải giành chiến thắng trong trò chơi sau bằng cách phân biệt đầu ra đó đã được cập nhật bởi một chức năng nào đó hay chưa?

1. Kẻ tấn công truy vấn một lời tiên tri cho đầu ra.

2. Oracle tạo 4 byte ngẫu nhiên mới $a$, $b$, $c$, và $d$ và một bit ngẫu nhiên $x$.

3. nếu $x=0$, Oracle xuất ra các giá trị của $a$, $b$, $c$, và $d$.

4. nếu $x=1$, trước tiên, nó cập nhật các giá trị bằng cách sử dụng các phương trình sau (được áp dụng tuần tự) và sau đó xuất các giá trị đã cập nhật của $a$, $b$, $c$, và $d$. $$\begin{align} a &= (a + dc) \bmod 256;\ b &= (b + quảng cáo) \bmod 256;\ c &= (c + ba) \bmod 256;\ d &= (d + cb) \bmod 256;\ \end{align}$$

5. Mục tiêu của kẻ tấn công là tìm ra đầu ra đó là kết quả của bước 3 hay 4?

*Kẻ tấn công có thể thực hiện vô số truy vấn.

Ví dụ: nếu a=0, b=0, c=1, d=1 và x=1 ở bước 2, thì Oracle xuất ra 1,1,2,3.

• Xác suất thắng từ lần thử đầu tiên =0,5 (đoán thuần túy giả sử các giá trị X ngẫu nhiên thống nhất 0 hoặc 1)

• Xác suất thắng ở lần thử thứ 2 nếu anh ta biết kết quả của lần thử thứ nhất = 1 - vấn đề[((a=a+dc)mod256) AND ((b=b+ad) mod256) AND ((c=c+ba) mod256) AND ((d=d+cb) mod256)]

Để bắt đầu, các công thức này phải là â¥256 (đạt được cùng một giá trị thông qua thao tác mod) ít nhất 3 trong số 4 giá trị phải là ¥128

Trên thực tế, chúng phải chứa (không chỉ lớn hơn hoặc bằng) đủ lũy thừa của 2 (dc=nâ¢256, ad=mâ¢256, ab=kâ¢256, cb=lâ¢256)

.... và cứ thế, tuy nhiên tôi nghĩ nên kiểm tra thêm xem các giá trị có phải được lưu trữ trong một byte hay không; tức là theo mặc định a, b, c, d < 256?

»»» Trong trường hợp bước 2 được lặp lại sau mỗi lần thử, thì tôi đoán cách duy nhất mà đối thủ thu được từ việc biết chức năng ( thay đổi xác suất chiến thắng của anh ta thành hơn 0,5 lần đoán thuần túy) là nếu các công thức đã cho r không đồng nhất ngẫu nhiên , tức là nếu bạn có thể chứng minh a, b, c, d đã sửa đổi nghiêng về nhiều hơn 1 giây hoặc nhiều hơn 9, thì có thể xác suất chiến thắng sẽ tăng lên khi giảm mức độ ngẫu nhiên.