Mài trong Fiat-Shamir heuristic

Điều gì tránh cho người châm ngôn nghiền ngẫm các thông điệp của mình để có thể giả mạo bằng chứng giả mạo?

Chúng ta cũng có thể hỏi chính xác câu hỏi tương tự đối với một lời tiên tri ngẫu nhiên! Điều gì ngăn cản người châm ngôn nghiền ngẫm thông điệp của anh ta cho đến khi anh ta có thể giả mạo bằng chứng giả mạo? Những gì bạn đề xuất hoàn toàn có thể được thực hiện với RO.

Và câu trả lời là: nên có một số lượng tin nhắn rất nhỏ $\alpha_1$ như vậy mà $\beta_1 = H(\alpha_1)$ cho phép người chứng minh có một lợi thế. trong một điển hình $\Sigma$-giao thức, ví dụ, khi tuyên bố không có trong ngôn ngữ (do đó người tục ngữ gian lận), trung bình có một $\alpha_1$ điều đó cho phép người chứng minh gian lận. (Bài tập: chứng minh rằng đây là trường hợp của $\Sigma$-protocol cho bộ dữ liệu DDH, trong đó có từ $(X,Y)$ và nhân chứng là $x\in\mathbb{Z}_p$ như vậy mà $X = g^x$ và $Y = h^x$). Do đó, nếu có $2^c$ những giá trị khả thi $\beta_1$ (đó là không gian thử thách), người châm ngôn độc hại sẽ phải tính toán $O(2^c)$ băm để giả mạo một bằng chứng giả mạo. bây giờ làm cho $c$ đủ lớn, và bạn có được bảo mật máy tính.

Lưu ý rằng cuộc tấn công mài vẫn là một cân nhắc quan trọng: $\Sigma$-các giao thức có bảo mật vô điều kiện, nhưng ngay sau khi bạn biên dịch chúng trong ROM bằng Fiat-Shamir, chúng chỉ có tính toán sự lành mạnh. Điều này có nghĩa là tham số bảo mật cho tính hợp lý (không gian thử thách) phải được điều chỉnh tương ứng: không gian thử thách 40 bit phù hợp với một $\Sigma$-giao thức (vì nó mang lại cho một câu tục ngữ ác ý một $2^{-40}$ xác suất thống kê của việc phá vỡ thành công âm thanh, có thể chấp nhận được trong thực tế), nhưng bị phá vỡ đối với Fiat-Shamir (vì việc phá vỡ giao thức được biên dịch yêu cầu $2^{40}$ hoạt động, đó là tầm thường để thực hiện). Thông thường, chúng tôi sẽ sử dụng một không gian thách thức về $2^{128}$ khi sử dụng Fiat-Shamir.