Điểm:2

Với mọi số $a, b$, các toán tử $X, Y$ là gì sao cho $a\ X\ b$ và $a\ Y\ b$ không hiển thị thông tin về $a,b$?

lá cờ in

trước đây Tôi nghĩ về một cặp số ngẫu nhiên phân bố đều 8 bit $(a,b) \in \{0,1\}^8$, và $X$ để được XOR bitwise, $Y$ là phép cộng 8 bit. Nhưng hóa ra tiết lộ $a \text{ XOR } b, a+b \bmod{2^8}$ tiết lộ rất nhiều bit thông tin về $a,b$.

Một anh chàng thông minh ở đây đã đề cập đến "sự phụ thuộc" như một tài sản. Vì vậy, tôi đoán tôi đang tìm kiếm các nhà khai thác độc lập? Hoặc, ít nhất, các toán tử độc lập khi đầu vào của chúng là các số ngẫu nhiên?

Câu hỏi của tôi là:

  • Chúng ta có thể đi bao xa trong việc giảm thiểu lượng thông tin mà $a\ X\ b$$a\ Y\ b$ cho về $a,b$?
  • Chúng ta có thể chứng minh bằng toán học bất kỳ giới hạn nào không? Ví dụ. chứng minh rằng nếu $a,b$ là các số ngẫu nhiên thống nhất, thì nếu $X$ là và $Y$ là ..., thì nó phải là thế $a\ X\ b$$a\ Y\ b$ không thể cho nhiều hơn $x$ bit thông tin về $a,b$?
fgrieu avatar
lá cờ ng
Nếu $X$ (tương ứng $Y$) có thể nhận các giá trị $u$ (tương ứng $v$) trên toàn bộ hai đối số của nó, thì $a\ X\ b$ và $a\ Y\ b$ cùng nhau không thể lấy nhiều hơn giá trị $u\,v$, do đó không thể tiết lộ nhiều hơn $\log_2(u\,v)$ bit thông tin. Có thể có một giới hạn tốt hơn đối với một số lựa chọn $X$ và $Y$ làm cho các giá trị trở thành "phụ thuộc", nhưng tôi không biết cách mô tả điều đó tốt hơn là xác định sự phụ thuộc là sự khác biệt giữa giới hạn đó và lượng thông tin thực tế tiết lộ,
caveman avatar
lá cờ in
@fgrieu - Đang cố gắng hiểu: nếu chúng ta chỉ xử lý các biến 8 bit, thì điều đó có nghĩa là $u=v=8$? Ngoài ra, có ý tưởng nào về cách chứng minh giới hạn $\log_2(uv)$ không? Cảm ơn rất nhiều.
fgrieu avatar
lá cờ ng
$u$ và $v$ phụ thuộc vào $X$ và $Y$. Nếu chúng ta xác định $a\ X\ b $ và $a\ Y\ b $ là 42 bất kể $a$ và $b$, thì $u=v=1$, $\log_2(u\,v)$ là $0$, và do đó giới hạn trên này cho chúng ta biết rằng không có thông tin nào được tiết lộ về $a$ và $b$. Lưu ý rằng khi $a\ X\ b $ và $a\ Y\ b $ không cố định nhưng bằng nhau bất kể $a$ và $b$, chúng ta có $u=v>1$, giới hạn $\log_2( u\,v)$ giữ nhưng bị lỏng. Bằng chứng về giới hạn $\log_2(u\,v)$: một biến nhận các giá trị $w$ không thể tiết lộ nhiều hơn $\log_2(w)$ bit thông tin và đối với $(X,Y)$ chúng ta nhận được nhiều nhất là các giá trị $w=u\,v$.
fgrieu avatar
lá cờ ng
Tôi thắc mắc: có phải bạn đang xem xét "lượng thông tin mà $a\ X\ b$ và $a\ Y\ b$ cung cấp về $a,b$" (có thể luôn lên đến 16 bit, giả sử như $ a\ X\ b$ trả về $a$, và $a\ Y\ b$ trả về $b$), hoặc lượng thông tin mà $a\ X\ b$ và $a\ Y\ b$ cung cấp về một trong số $a$ hoặc $b$, cái còn lại được coi là ngẫu nhiên và không xác định (rõ ràng là không thể vượt quá 8 bit)?
caveman avatar
lá cờ in
@fgrieu Cái trước. Cả $a,b$ đều được coi là bí mật càng nhiều càng tốt. Tôi đang cố gắng tìm hiểu xem một người có thể đi bao xa với các toán tử $X,Y$ trong việc giảm thiểu rò rỉ thông tin khỏi $a,b$. Tôi hiểu tại sao $\log_2(uv)$ là giới hạn tối đa lỏng lẻo (vì đây là thông tin tối đa có thể chứa trong $uv$ nhiều số duy nhất).
Điểm:2
lá cờ sa

Có thể rò rỉ thông tin bằng không. Giả sử phân bố đều $a$$b$ và để cho $a$ khác nhau dọc theo các hàng và $b$ dọc theo các cột của bảng thao tác dưới đây:

$$ \begin{array}{ccc} \begin{array}{c|cccc} X & 0&1&2&3\ \hline 0 & 0&1&2&3 \ 1 & 1&2&3&0 \ 2 & 2&3&0&1 \ 3 & 3&0&1&2 \end{mảng} & \quad & \begin{array}{l|cccc} Y & 0&1&2&3\ \hline 0 & 3&0&1&2 \ 1 & 0&1&2&3 \ 2 & 1&2&3&0 \ 3 & 2&3&0&1 \end{mảng} \end{mảng} $$

Lưu ý rằng đối với mỗi thao tác biết đầu ra ($aXb$ hoặc $aYb$) không cung cấp thông tin gì cả về $a$. Điều này cũng đúng với $b$. Nhưng nếu bạn biết một trong $a$ hoặc $b$ sau đó bạn biết cái kia một cách duy nhất.

Hơn nữa, chúng ta hãy nói $aXb=0.$ Các cặp có thể $(a,b)$ hiện đang ở trong bộ $$ S=\{(0,0),(1,3),(2,2),(3,1)\}. $$

Giả sử không có lỗi trong tính toán hoạt động, khả năng duy nhất cho $aYb$$aYb=3$ và điều này mang lại không có thêm thông tin về các cặp có thể có trong $S$.

Bạn có thể nói đây là một ví dụ kỳ lạ, nhưng nó chứng tỏ rằng giá trị tối thiểu có thể bằng 0 đối với từng biến đầu vào riêng lẻ.

Một điểm cuối cùng, vì tôi không biết chính xác yêu cầu của bạn. Có thể tăng gấp đôi độ dài bit của đầu ra trong khi đảm bảo ngay cả khi biết một trong $a$ hoặc $b$ rò rỉ không có thông tin về khác. Đầu ra $2X3=12$ sẽ tương ứng với mẫu bit đầu ra $0110$ với $01=1,$$10=2.$ Dưới đây là một ví dụ dưới đây:

$$ \begin{array}{c|cccc} X & 0&1&2&3\ \hline 0 & 00&11&22&33 \ 1 & 13&02&31&20 \ 2 & 21&30&03&12 \ 3 & 32&23&10&01 \end{mảng} $$ Bây giờ hãy để chúng tôi nói rằng bạn biết điều đó $a=1.$ Điều này giới hạn bạn ở hàng thứ hai của bàn mổ nhưng $b$ vẫn hoàn toàn chưa được xác định, bạn biết đấy không có gì về giá trị của $b.$

Ví dụ này sử dụng hai MOLS (Hình vuông Latinh trực giao lẫn nhau).

caveman avatar
lá cờ in
_Astounding-total-amaze-stupendousness_. Đây là vinh quang thuần túy. Cảm ơn rất nhiều. Tuy nhiên, tôi không nhận được độ dài bit gấp đôi: nếu $aXb = 12$, chẳng phải là tra cứu tầm thường để thấy rằng nó phải là $a=2, b=3$ sao? I E. cả $a,b$ đều bị lộ? Có lẽ tôi đang thiếu một cái gì đó cơ bản?
kodlu avatar
lá cờ sa
Trong mô hình lý thuyết thông tin về rò rỉ thông tin, chúng ta quan sát một số biến nhất định và đặt câu hỏi về độ không đảm bảo liên quan đến các biến khác khi giá trị đó được biết. Vì vậy, chúng tôi quan sát, ví dụ: $aXb$ và hỏi về $a$ hoặc $b$ hoặc $a,b$ cả hai. Ngoài ra, chúng tôi quan sát $a$ và $aXb$ và hỏi về $b$. Ngoài ra, nếu chúng ta áp dụng mô hình cho một tập hợp lớn hơn trong bối cảnh mật mã, thì việc sử dụng vũ phu là không khả thi.
caveman avatar
lá cờ in
Tôi chỉ không thể đọc bảng cuối cùng. $2X3 = 12$, phải không? Nhưng văn bản của bạn nói $1X2=12$?
kodlu avatar
lá cờ sa
xem chỉnh sửa để làm rõ

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