Ý tưởng của bạn về một phương thức mã hóa bao gồm cả nonce và theo cách mà Alice không thể khôi phục nonce là thực tế; tuy nhiên nó không giải quyết được vấn đề của bạn.
Một khả năng sẽ là một biến thể của El Gamal; trong hệ thống này, khóa công khai của Alice là một giá trị $A= G^a \bmod p$, với $a$ là khóa riêng của Alice và $G, p$ là tham số công khai (với $p$ là một số nguyên tố an toàn, và $G$ dư bậc hai).
Để mã hóa một tin nhắn $M < p/2$, Bob sẽ chọn một giá trị ngẫu nhiên $r$, và tạo bản mã $G^r \bmod p, M^2 \cdot A^r \bmod p$.
Để giải mã cặp $X, Y$, Alice sẽ tính toán $M^2 = Y \cdot X^{-a} \bmod p$ (và sau đó lấy căn bậc hai mô-đun của $M^2$ để phục hồi $M$).
Nếu Alice lấy được cặp $X, Y$, cô ấy không biết giá trị $r$, và như vậy, thoạt nhìn, cho thấy rằng $G, A = G^a, X = G^r, Y \cdot M^{-2} = G^{ar}$ là một tập hợp DH là vấn đề Quyết định Diffie-Hellman, nói chung là khó; cô ấy có thể dễ dàng làm như vậy bằng cách phơi bày $a$, tuy nhiên đối với cô ấy, điều đó sẽ đánh bại mục đích.
Tuy nhiên, những gì cô ấy có thể làm là tạo ra một bằng chứng không có kiến thức rằng $G^x = A$ và $X^x = Y \cdot M^{-2}$ có một giải pháp chung $x$ (điều mà cô ấy có thể làm, vì cô ấy biết giải pháp thông thường đó là gì); bằng chứng không kiến thức này sẽ chỉ ra rằng $M$ là giải mã mà không để lộ khóa riêng của cô ấy.
Điều này dẫn đến quan sát tổng quát hơn; Nếu thuật toán giải mã $D$ và tạo khóa công khai $Gen$ cả hai đều chạy trong đa thời gian, sau đó tuyên bố rằng $D(a, C) = M \land (a, A) = Gen(hạt giống)$ (đối với công chúng $C$ và $M$ mà Alice tuyên bố là giải mã là một tuyên bố trong NP (với $a$ và $hạt giống$ là 'nhân chứng') và đối với một tuyên bố như vậy trong NP, người ta có thể xây dựng một bằng chứng không có kiến thức, cho thấy rằng $M$ là một giải mã chính xác.
Vì vậy, trừ khi Bob có thể khẳng định rằng anh ấy đã không thực sự gửi bản mã $C$ (và tôi cho rằng bằng cách nào đó người ta cho rằng bằng cách nào đó mọi người đều biết anh ấy đã làm), nó không giống như một vấn đề có thể giải quyết được.
