Điểm:1

Bảo mật có thể chứng minh: không thể giảm khi tin nhắn được mã hóa/bảo mật ngữ nghĩa với chức năng tùy thuộc vào đầu ra của đối thủ

lá cờ us

Tôi gặp vấn đề với một giao thức mà tôi có thể chứng minh tính bảo mật nếu các tin nhắn do kẻ thù gửi được gửi rõ ràng, nhưng tôi không thể chứng minh tính bảo mật nữa nếu các tin nhắn do kẻ thù gửi được mã hóa... và điều này hơi lạ vì tôi hy vọng giao thức cũng được bảo mật trong trường hợp thứ hai đó.

Chính xác hơn, tôi đang xem xét một giao thức mà máy chủ Bob nhận được tin nhắn $k$ từ Alice (điều này có thể được coi là mã hóa của một chuỗi bit $d_0$ dưới khóa công khai bí mật $t_k$) và gửi lại một tin nhắn $y$ (cũng có thể được coi là mã hóa một số tin nhắn $x$ ở dưới cái cùng khóa công khai $k$ của Alice: không phải do hình dạng của giao thức mà tôi thực sự cần sử dụng chính xác khóa này). Trong bằng chứng bảo mật, tôi muốn chỉ ra rằng không có Bob độc hại nào có thể tìm thấy giá trị bí mật $\theta_\pi=f(x,d_0)$ điều đó sẽ trông ngẫu nhiên nếu không.

Tin tốt là nếu tôi biết $x$, tôi có thể đảo ngược $f$ và tìm $d_0$. Do đó, nếu một Bob độc hại biết $x$, tôi có thể rút gọn để chứng minh rằng nếu Bob có thể tìm thấy $\theta_\pi$ họ Bob cũng biết $d_0 = f^{-1}(x,\theta_\pi)$: đây là một mâu thuẫn vì mã hóa được bảo mật theo IND-CPA.

Thật không may, việc giảm này không hoạt động vì Bob độc hại có thể không "biết" $x$: họ chỉ gửi một phiên bản được mã hóa $y$ của nó: và trong quá trình giảm tôi không thể giải mã được $y$ vì chìa khóa chỉ có Alice biết (điều này là không thể tránh khỏi trong trường hợp của tôi)...

Có một số phương pháp để vẫn chứng minh bảo mật trong trường hợp đó? tôi đoán Tôi cần một cái gì đó như bảo mật ngữ nghĩa nhưng trong đó chức năng được tính toán không thể tính toán hiệu quả (đây đã là trường hợp trong định nghĩa hiện tại) và cũng phụ thuộc vào một số đầu ra của đối thủ.

CHỈNH SỬA

Để trả lời Mikero, tôi nghĩ rằng trong lập luận của bạn, chúng ta cần phải nói điều gì đó như thế này:

nhập mô tả hình ảnh ở đây

Nếu chúng ta xoay sở để lấy đúng hộp, thì tôi đồng ý rằng bằng chứng sẽ dễ dàng theo sau. Nhưng tôi không chắc làm thế nào để chứng minh sự tương đương giữa hai kịch bản này. Tôi không nghĩ đây là sự giảm thiểu trực tiếp đối với bảo mật IND-CPA, bởi vì bộ phân biệt cũng có quyền truy cập vào $\theta_\pi$ được liên kết với một số thông tin về giải mã $y$. Tôi đoán sẽ rất tuyệt nếu chỉ ra rằng sơ đồ đầu tiên tương đương với

nhập mô tả hình ảnh ở đây

nhưng không chắc chắn làm thế nào để chứng minh điều đó (tất nhiên $Func lý tưởng_1$ có thể phân biệt được với $Func lý tưởng_3$, câu hỏi đặt ra là khi nào chúng ta thêm trình giả lập lên trên).

lá cờ us
Có vẻ như Alice trung thực trong tình huống này, vì vậy trình mô phỏng sẽ tạo khóa công khai của Alice. Sau đó, trình giả lập sẽ có thể giải mã các bản mã được mã hóa theo khóa công khai đó và thực hiện phép giảm thông thường của bạn. Nhân tiện, điều gì sẽ xảy ra nếu Bob chỉ lặp lại cùng một mã hóa của $d_0$?
lá cờ cn
Ngoài ra, cách tiêu chuẩn để đảm bảo rằng kẻ thù biết bản rõ sẽ là thêm bằng chứng biết vào bản mã.
Léo Colisson avatar
lá cờ us
@Maeher Cảm ơn câu trả lời của bạn.Thật không may, điều này không thể hoạt động trong trường hợp của tôi vì tôi đang ở trong môi trường lượng tử: về cơ bản, để đối thủ học được $x$, nó cần phải phá hủy trạng thái của nó (và sau đó, giao thức không còn hữu ích nữa). Tất nhiên, tôi có thể thực hiện phương pháp "cắt và chọn" bằng cách thỉnh thoảng yêu cầu phá hủy trạng thái và thỉnh thoảng tiếp tục, nhưng sau đó tôi chỉ nhận được bảo mật đa thức :-( Tôi cũng không nghĩ rằng cách tiếp cận được đề xuất của Mikero hoạt động, tôi sẽ cố gắng giải thích trong một tin nhắn khác.
Léo Colisson avatar
lá cờ us
@Mikero Cảm ơn câu trả lời của bạn, nhưng tôi không chắc nó có hoạt động không (ít nhất là trong trường hợp của tôi). Nếu trình giả lập chọn khóa công khai của Alice, chúng ta cần lập luận để nói rằng trình giả lập có thể mã hóa $d_0'$ ngẫu nhiên thay cho $d_0$ (vì $d_0$ không được rò rỉ vào trình giả lập) mà không bị phát hiện. Tuy nhiên, tôi không nghĩ rằng điều này được ngụ ý trực tiếp bởi IND-CPA (xem bản chỉnh sửa của tôi). Tui bỏ lỡ điều gì vậy?
Léo Colisson avatar
lá cờ us
@Mikero cũng vậy, nếu Bob lặp lại $y$, thì về cơ bản, nó sẽ đặt $x = 00$ (điều này hoàn toàn ổn).
lá cờ cn
Tôi không chắc mình hiểu cài đặt lượng tử là một vấn đề như thế nào. Bạn đang nói rằng y trên thực tế *không phải* là một bản mã, mà là một sự chồng chất tùy ý của các bản mã? Đầu tiên, tại sao bạn lại cho phép đối thủ làm điều đó? Và thứ hai, theo như tôi thấy thì bạn cũng có thể tính toán chứng minh tri thức trên sự chồng chập đó.
Léo Colisson avatar
lá cờ us
@Maeher Đó là vì mục tiêu của giao thức là tạo ra một trạng thái lượng tử mà Bob không biết. Về cơ bản để có được $y$, Bob phải tạo một chồng chất $\sum_x | x \rangle | g(x) \rangle$. Hàm $g$ là 2 trên 1: vì vậy sau khi đo thanh ghi thứ hai, chúng tôi nhận được $| x \rangle+|x' \rangle$ trên thanh ghi đầu tiên cho 2 tiền tố của $g$. Từ trạng thái này, chúng ta có thể thu được trạng thái lượng tử mới sẽ được sử dụng trong các giao thức khác (đối thủ không thể mô tả đầy đủ trạng thái này vì nó không thể đảo ngược $g$). Nếu Bob muốn tìm hiểu một $x$, anh ấy có thể đo lường nó... nhưng nó sẽ phá hủy nó.
Léo Colisson avatar
lá cờ us
Vì vậy, $y$ là một văn bản mật mã cổ điển, nhưng nó được xác định bằng cách sử dụng phép chồng chất vẫn hữu ích sau khi kết thúc giao thức.

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