Điểm:3

PPT đồng nhất và không đồng nhất

lá cờ in

Trong khi đọc báo

Tôi tình cờ phát hiện ra trường hợp cần phải nêu rõ liệu các tác giả có giả định là những kẻ tấn công đồng nhất hay không đồng nhất hay không. Theo những gì tôi biết, PPT không đồng nhất về cơ bản là một chuỗi các PPT, vì vậy $\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_n\}$và trên đầu vào $x$ kích thước $|x| = \lambda$, $\mathcal{A}_\lambda$ được gọi là. Vì sao mẫu này “mạnh” hơn mẫu đồng phục? Không thể tấn công quảng cáo $\mathcal{A}$ chỉ cần nhúng tất cả những kẻ tấn công khác vào mô tả của chính nó và gọi cái phù hợp? Có vấn đề nào chúng ta biết cách giải quyết trong mô hình đồng nhất nhưng không (nếu không phải với sự đảm bảo yếu hơn) trong mô hình không đồng nhất?

Điểm:1
lá cờ ng

Hãy xem xét một phép liệt kê đơn nhất của tất cả các máy Turing, ví dụ: một cái máy $M$ được đại diện bởi $1^{\lambda_M}$ cho một số nguyên duy nhất $\lambda_M$. Vấn đề tạm dừng là không thể tính toán được, ngay cả trong biểu diễn "thưa thớt" này. Nhưng nó không thể tính toán một cách thống nhất, vì mỗi máy Turing $M$ tạm dừng hoặc không, và chúng tôi có thể "mã hóa cứng" quyết định điều này vào từng máy xử lý $A_{\lambda_M}$.

Nếu chúng ta có thể "tạo ra một cách thống nhất" $A_i$'s, có nghĩa là tạo chúng một cách hiệu quả từ mô tả duy nhất của $i$, bạn sẽ đúng. Trong ví dụ trên, bạn không thể, vì bạn không biết liệu mỗi máy Turing $M$ dừng lại.

lá cờ us
Một cách khác để thấy rằng các thuật toán không đồng nhất có thể làm những việc mà các thuật toán đồng nhất không thể: có vô số thuật toán không đồng nhất nhưng cũng có nhiều thuật toán đồng nhất.
jacobi_matrix avatar
lá cờ in
Cảm ơn bạn cho câu trả lời của bạn. Tôi đã tự hỏi liệu chúng ta có biết các vấn đề thực tế trở nên dễ dàng hơn trong mô hình không đồng nhất không. Nhắc lại, làm thế nào một lược đồ mã hóa/cam kết/chữ ký... có thể cung cấp một mức độ bảo mật nhất định khi chúng ta giả sử các đối thủ thống nhất nhưng mức độ bảo mật thấp hơn đối với các đối thủ không đồng nhất, nếu chúng ta có thể xây dựng một đối thủ thống nhất mã hóa cứng các đối thủ khác thành của nó mô tả riêng (và vẫn có kích thước mô tả đa thức)
Mark avatar
lá cờ ng
@jacobi_matrix Xem phần 4 của [cái nhìn khác về độ kín 2](https://eprint.iacr.org/2016/360.pdf) để biết một số thảo luận về giả định độ cứng không đồng nhất. Điều đáng nói là một khái niệm hơi liên quan đến các cuộc tấn công "xử lý trước" (trong đó người ta nhận được lời khuyên cụ thể về trường hợp) có một số ví dụ mà chúng giúp ích (và có thể dẫn đến các cuộc tấn công thực tế), ví dụ như [tấn công logjam]( https://en.wikipedia.org/wiki/Logjam_(computer_security)) hoặc nhiều sự cố trong mật mã dựa trên mạng (mặc dù hầu hết các hệ thống mật mã mạng tạo ra các phiên bản mới mỗi lần, hạn chế nguy cơ tiền biên dịch
Mark avatar
lá cờ ng
@jacobi_matrix, vấn đề là bạn không thể xây dựng một đối thủ thống nhất mã hóa cứng những người khác thành mô tả của nó, vì việc tạo $A_i$ tùy ý có thể không thể tính toán được một cách hiệu quả (hoặc thậm chí không thể tính toán được, ví dụ như "Vấn đề tạm dừng thưa thớt" thuật toán không thống nhất được đưa ra trong câu trả lời của tôi). Hơn nữa, bạn không thể chỉ "lưu trữ" tất cả chúng trong đối thủ thống nhất, vì đối thủ thống nhất sẽ có quá nhiều mô tả.
jacobi_matrix avatar
lá cờ in
Hoàn hảo! Phần mà bạn đã liên kết và ví dụ về cuộc tấn công logjam thực sự đã làm được điều đó. Vấn đề là tôi đã nghĩ (rõ ràng là sai) rằng chuỗi lời khuyên phải là chính kích thước đầu vào (ví dụ: được mã hóa ở dạng đơn nguyên). Cảm ơn một lần nữa.

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