Điểm:2

Barak et al. bằng chứng cho thấy việc che giấu hộp đen là không thể

lá cờ br

Tôi đã cố gắng phân tích bằng chứng kinh điển được đưa ra bởi Barak et al. tuyên bố rằng Black-Box Obfuscation không thể thực hiện được đối với (dường như) hầu hết các loại chương trình.

Bằng chứng được trình bày theo cách mà người ta nói rằng nếu tồn tại một chương trình được mã hóa C'(a, b, x) trả về b nếu và chỉ nếu một = x, và một chương trình mã hóa khác D'(a, b, f) trả về 1 nếu một chỉ nếu f(a, b, x) = b, sau đó D'(a, b, C(a, b, x)) = 1 với xác suất là 1. Điều này cũng có nghĩa là kẻ tấn công sẽ có thể phân biệt C'(a, b, x) từ chức năng khác Z() trả về 0 tại mọi điểm như D'(a, b, Z()) = 1 với xác suất nhỏ hơn 1.

Tuy nhiên, bằng chứng không thực sự có ý nghĩa đối với tôi, vì giả sử kẻ tấn công không thể kiểm tra từng giá trị của mộtb dường như không có cách nào để kết luận có bất kỳ sự khác biệt nào giữa C'(a, b, x)Z(). Tuy nhiên, Black-Box Obfuscation sẽ đúng nếu cách duy nhất để phân biệt hai chương trình là kiểm tra từng đầu vào và kiểm tra đầu ra.

Có ai có thể giúp giải thích cho tôi làm thế nào bằng chứng này thực sự thuyết phục để nói rằng Black-Box Obfuscation (đối với hầu hết các phần) là không thể?

kodlu avatar
lá cờ sa
vui lòng cung cấp một liên kết đến bài báo nếu có sẵn trực tuyến
James avatar
lá cờ br
@kodlu Bây giờ tôi đã bao gồm liên kết đến bằng chứng được đề cập (bài báo mô tả nó theo cách toán học hơn nhiều so với tôi đã làm, nhưng vì nó là một bằng chứng khá nổi tiếng nên tôi đã có được một dạng đơn giản hóa để trình bày ở đây).
Điểm:3
lá cờ us

Bài báo định nghĩa hai lớp chức năng:

\begin{align*} C_{\alpha,\beta}(x) &= \begin{cases} \beta & \mbox{ if } x=\alpha \ 0^k & \mbox{ mặt khác} \end{cases} \ D_{\alpha,\beta}(F) &= \begin{cases} 1 & \mbox{ if } F(\alpha)=\beta \ 0 & \mbox{ otherwsie} \end{cases} \end{align*}

Vấn đề là nếu bạn được cung cấp bất kỳ mạch nào $C^*$ (thậm chí là một cái bị xáo trộn) tính toán chức năng tương tự như $C_{\alpha,\beta}$ sau đó $D_{\alpha,\beta}(C^*)=1$.

Mặt khác, nếu bạn chỉ có quyền truy cập hộp đen vào $C_{\alpha,\beta}$, và $\alpha,\beta$ được chọn thống nhất, thì sẽ khó có thể đưa ra một đầu vào gây ra $D_{\alpha,\beta}$ để xuất 1.

Theo trực giác, có quyền truy cập vào một obfuscation của $C_{a,b}$ cung cấp cho bạn nhiều quyền lực hơn là có quyền truy cập hộp đen vào $C_{a,b}$.

Tuy nhiên, bằng chứng không thực sự có ý nghĩa đối với tôi, vì giả sử kẻ tấn công không thể kiểm tra từng giá trị của $\alpha$$\beta$ dường như không có cách nào để kết luận có bất kỳ sự khác biệt nào giữa $C_{\alpha,\beta}$$Z$ (một chức năng xuất ra số 0 trên tất cả các đầu vào).

Kẻ tấn công không phân biệt được obfuscations của $C_{\alpha,\beta}$ từ obfuscations của $Z$ bằng cách thử mọi đầu vào. Kẻ tấn công phân biệt bằng cách chuyển obfuscation làm đầu vào cho $D_{\alpha,\beta}$. $D_{\alpha,\beta}$ có "đúng" $\alpha,\beta$ nung nấu trong đó -- nó biết tìm ở đâu nên có thể dễ dàng phân biệt $C_{\alpha,\beta}$ từ $Z$.

James avatar
lá cờ br
Nhưng làm sao một tin tặc có thể biết rằng `a` và `b` được đưa vào cả hai hàm bị xáo trộn (và do đó `D'(C')` sẽ luôn trả về `1`) trừ khi nó tình cờ là `a` đã được đưa vào bằng `x`? Ngoại trừ trường hợp đó, `C'` dường như vẫn xuất hiện giống với `Z`? Ngoài ra, chẳng phải bằng chứng này chỉ đơn giản gợi ý rằng Black-Box Obfuscation là không thể trong một tình huống rất cụ thể mà một tin tặc tìm thấy, chẳng hạn như hai hàm có các biến tích hợp sẵn chính xác?
lá cờ us
Khi chúng tôi xác định bảo mật cho mã hóa, chúng tôi nói (ví dụ) rằng bản mã trông không thể phân biệt được với ngẫu nhiên, ngay cả khi đối thủ phải chọn bản rõ. Khi chúng tôi xác định bảo mật VBB cho che giấu, chúng tôi nói rằng chương trình bị xáo trộn không rò rỉ nhiều hơn quyền truy cập hộp đen vào chức năng, ngay cả khi đối thủ phải chọn chức năng. Ngoài ra, sau này trong Barak et al. bằng chứng là họ kết hợp cả C và D vào một chương trình duy nhất, điều này đảm bảo rằng cả C và D đều có ý nghĩa $\alpha$ và $\beta$ giống nhau.
James avatar
lá cờ br
Tuy nhiên, ngay cả khi một đối thủ đã chọn `a` và `b` cho cả `C` và `D`, nếu chúng tôi trả lại họ cả `Z'` và `C'` vào một ngày sau đó thì họ sẽ không thể cho biết cái nào là cái nào? Đó là trừ khi họ cũng đưa vào `x`. Tuy nhiên, nếu họ đã đưa vào từng biến đơn lẻ thì bằng chứng có vẻ hơi thừa vì khi đó họ chỉ đang cố tình tạo một hàm `C` luôn trả về `1` và một hàm `Z` luôn trả về `0`. Tuy nhiên, nếu `x` không được đưa vào, thì đối thủ phải kiểm tra từng `x` trên cả `C'` và `Z'` cho đến khi chúng tạo ra các kết quả khác nhau?
Manish Adhikari avatar
lá cờ us
Nếu bạn muốn có câu trả lời trực quan hơn liên quan đến rò rỉ thông tin rõ ràng, hãy cân nhắc một chút rằng chương trình $C^*_{\alpha,\beta} (.)$ tính toán hàm tương tự như $C_{\alpha,\beta} ( .)$ với $\alpha$ và $\beta$ được chọn ngẫu nhiên từ một không gian lớn. Bây giờ hãy thay đổi $D_{\alpha,\beta} (F)$ một chút sao cho nó trả về $\beta$ nếu $F(\alpha)=\beta$ và $0^k$ nếu không. Được cấp quyền truy cập vào $D$, bạn có thể trích xuất $\beta$ từ hộp đen đang chạy $C$. Còn từ $C^*$ thì sao?
James avatar
lá cờ br
Tôi có lẽ sẽ phải xin lỗi vì tôi có thể vẫn còn thiếu điều gì đó ở đây. Mặc dù vậy, tôi sẽ nói @ManishAdhikari rằng tôi sẽ tưởng tượng bạn sẽ trích xuất chính xác nhiều thông tin về $\beta$ từ hộp đen chạy $C$ cũng như từ $C*$, trừ khi bạn đã biết $\alpha$ được đưa vào đó là gì hoặc bạn có thể sử dụng $\alpha$, $\beta$ và $x$ sao cho $C_{\alpha,\beta}(x)$ sẽ luôn trả về $\beta$ và không bao giờ $0^k$ . Trong tất cả các trường hợp khác, bạn sẽ phải kiểm tra từng $x$ đơn lẻ cho đến khi bạn tìm thấy giá trị mà hàm trả về $\beta$?
Manish Adhikari avatar
lá cờ us
Vâng, có vẻ như bạn vẫn đang thiếu điểm. Tôi đã nói rằng $D$ có sẵn cho bạn. Với $C^*$, bất kể $\alpha$ và $\beta$ có thể bị xáo trộn như thế nào trong chương trình, bạn có thể trích xuất $\beta$ bằng cách đơn giản nạp nó vào $D$. Nhưng một hộp đen đang chạy $C$ không thể được cấp cho bất cứ thứ gì và bạn bị mắc kẹt với việc chỉ cho nó đầu vào và nhìn thấy đầu ra. Trích xuất $\beta$ trong trường hợp này sẽ yêu cầu thử rất nhiều $x$ như bạn đã nói đúng.

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