Có nhiều tình huống trong đó mã hóa bất đối xứng không thể thay thế bằng mã hóa lai. Ở cấp độ cao, đặc điểm chung của các kịch bản này là chúng khai thác một số thuộc tính đại số của lược đồ mã hóa bất đối xứng, mà một phương pháp mã hóa lai sẽ phá vỡ. Điều này thường xảy ra khi chúng ta không muốn chỉ giao tiếp dữ liệu, nhưng cũng muốn thao túng nó theo cách bảo vệ quyền riêng tư.
Hai cách phổ biến nhất để khai thác các thuộc tính đại số của các lược đồ mã hóa bất đối xứng là:
- Homomorphism: đưa ra hai bản mã $\mathsf{Enc}(m_0)$ và $\mathsf{Enc}(m_1)$, có thể biến chúng thành một bản mã $\mathsf{Enc}(m_0 \boxplus m_1)$, ở đâu $\boxplus$ là một phép toán nào đó (ví dụ: cộng hoặc nhân).
- Tính thân thiện với bằng chứng: tồn tại các bằng chứng không có kiến thức hiệu quả để chứng minh các tuyên bố có dạng "$c$ là một mã hóa của một tin nhắn $m$ ở đâu $m$ thỏa mãn một số tính chất nhất định"
Hãy để tôi minh họa cả hai bằng một tình huống đồ chơi. Giả sử chúng ta muốn bỏ phiếu giữa hai ứng cử viên, $C_0$ và $C_1$, và có $n$ cử tri $V_1, \cdots, V_n$. Chúng tôi muốn khám phá kết quả của cuộc bỏ phiếu mà không tiết lộ các phiếu bầu riêng lẻ. Một giải pháp khả thi (đơn giản hóa) như sau: mỗi cử tri $V_i$ mã hóa phiếu bầu của nó, đó là một trong hai $0$ (nếu $V_i$ bình chọn cho $C_0$) hoặc $1$ (khác). để tôi gọi $(E_1, \cdots, E_n)$ các phiếu bầu được mã hóa. Quan sát rằng những gì chúng tôi muốn biết là như sau: tổng của các giá trị bản rõ là gì? Kết quả chia cho $n$ tương ứng với tỷ lệ phiếu bầu $C_1$ lấy; nếu nó nhiều hơn $50\%$, họ thắng cử.
Tôi cho rằng sơ đồ mã hóa là đồng hình cộng: từ mã hóa của $m_0$ và $m_1$, người ta có thể tính toán đồng cấu một mã hóa của tổng $m_0+m_1$ (chính thức hơn, chúng tôi cũng cần một yêu cầu kỹ thuật gọi là quyền riêng tư chức năng: bản mã kết quả không được rò rỉ nhiều thông tin hơn tổng này).
Chúng ta sẽ có hai thực thể: một tổng hợp và một người giải mã. Bộ tổng hợp lấy các bản mã $E_1, \cdots E_n$, tổng đồng hình chúng, nhận mã hóa $E$ của các kết quả, và gửi nó đến bộ giải mã. Bộ giải mã có khóa bí mật và công bố kết quả của cuộc bầu cử.
Nhưng chờ đã, có vấn đề! Điều gì sẽ xảy ra nếu bộ giải mã nói dối về các giá trị được giải mã? Chuyện gì xảy ra nếu $V_i$ mã hóa, nói, $18$ thay vì $0$ hoặc $1$? Điều này sẽ thêm hiệu quả $18$ bình chọn cho $C_1$. Không đi sâu vào chi tiết, mật mã có các phương pháp để giải quyết vấn đề đó, được gọi là bằng chứng không kiến thức, cho phép nối thêm bằng chứng vào một đối tượng (ví dụ: bản mã) để đảm bảo rằng nó đáp ứng một thuộc tính nhất định mà không ảnh hưởng đến quyền riêng tư của nó. Ở đây, mỗi $V_i$ có thể thêm một bằng chứng rằng $E_i$ thực sự mã hóa một bit (không tiết lộ cái nào) và bộ giải mã cũng có thể gửi bằng chứng rằng $E$ thực sự giải mã cho kết quả đúng (không tiết lộ khóa giải mã bí mật).
Như bạn có thể thấy ở trên, với một sơ đồ mã hóa với (1) tính đồng cấu phụ gia và (2) khả năng thực hiện bằng chứng không kiến thức, chúng ta có thể xây dựng các ứng dụng thú vị - bỏ phiếu là một ví dụ tự nhiên. Bạn có thể dễ dàng thuyết phục bản thân rằng mã hóa kết hợp phá vỡ tính đồng hình nói chung và nếu bạn đã hơi quen thuộc với bằng chứng không kiến thức, bạn cũng sẽ nhận thấy rằng mã hóa kết hợp sẽ khiến chúng cực kỳ kém hiệu quả.
Tôi có thể liệt kê nhiều ví dụ khác dọc theo các dòng trên: tiền điện tử, đấu giá điện tử, thông tin xác thực ẩn danh, v.v. Điểm chung của chúng là chúng tôi muốn làm nhiều việc hơn là truyền dữ liệu: chúng tôi muốn thao tác với nó, điều này đòi hỏi một số tính linh hoạt và chúng tôi muốn thực hiện điều đó một cách an toàn, điều này yêu cầu khả năng kiểm tra xem chỉ các thao tác được ủy quyền đã được thực hiện chưa. Cả hai đều yêu cầu mã hóa bất đối xứng cụ thể với các thuộc tính thích hợp.
