Trong bài báo Bằng chứng nhận dạng không kiến thức (của Feige, Fiat và Shamir), một giao thức ZK được mô tả là tận dụng dư lượng bậc hai. Phần 3 mô tả "Lược đồ nhận dạng hiệu quả", nhưng (theo hiểu biết của tôi) thuật toán PK dường như bị hỏng (theo nghĩa "không hoạt động", không phải theo nghĩa "bảo mật kém").
Giao thức tạo khóa là (các bước 1-3 được trích dẫn từ bài báo, sử dụng ký hiệu giống như bài báo):
Thiết lập: Hãy để $n$ là một số nguyên Blum (tích của hai số nguyên tố, $p$ và $q$, trong đó cả hai $p$ và $q$ đồng dạng với 3 mod 4). Để cho $Z_n$ biểu thị vòng dư lượng trong hoạt động mod.
- Chọn $k$ Số ngẫu nhiên $S_1, ..., S_k$ Trong $Z_n$.
- Chọn từng $I_j$ (ngẫu nhiên và độc lập) như $\pm 1 / S_j^2$ (chế độ n).
- Công bố $I = I_1, ..., I_k$ và gìn giữ $S = S_1, ..., S_k$ bí mật.
Không có ký hiệu, để lấy khóa công khai, chúng ta cần tính bình phương của từng bí mật $S_j$ và sau đó tìm nghịch đảo mô-đun của hình vuông này hoặc $(n-1)$ lần nghịch đảo này. (I E. $S_j^2 \cdot I_j = 1 (\text{mod}n)$ hoặc $S_j^2 \cdot I_j = -1 (\text{mod}n)$).
Vấn đề là ở Bước 2, $Z_n$ không phải là một lĩnh vực có nghĩa là $I_j$ không đảm bảo tồn tại. Cụ thể, bất kỳ $g \in Z_n$ sẽ không có nghịch đảo nếu một trong hai $p | g$ hoặc $q | g$. cho một rất lớn $n$ điều này khó có thể xảy ra, nhưng thật dễ dàng để chứng minh rằng nó luôn xảy ra.
Chứng minh sự tồn tại: không mất tính tổng quát, giả sử $p < q$. sau đó $p^2 \in Z_n$. Bởi vì $\text{gcd}(p^2, n) = p > 1$, chúng ta thấy rằng $p^2$ không có nghịch đảo trong $Z_n$.
Ví dụ nhỏ: khi $n = 21$, không phần tử nào của tập hợp này có số nghịch đảo trong $Z_n$ $\{0, 3, 6, 7, 9, 12, 14, 15, 18\}$. Một số trong số họ là những ứng cử viên hợp lệ để dẫn đến một điều không thể $I_j$ (như trên là $S_j = 3$ sau đó $S^2_j = 9$).
Bạn phải làm gì nếu bạn nhận được một trong những số "bị hỏng" này? Ve lai? Cho lớn $n$ xác suất nhỏ (rất dễ tính số lượng số bị "hỏng" trong $Z_n$ như $1 + (p-1) + (q-1) = p+q-1$, biến mất trong $pq$ Cho lớn $p$ và $q$) nhưng ít nhất là trong các triển khai thử nghiệm với quy mô nhỏ $n$ (Thích $n = 21$) nó sẽ phá vỡ bất kỳ mã nào đang cố lấy mã nghịch đảo đó.
