Tôi đang tìm kiếm một bằng chứng định lượng nhưng đơn giản về EUF-CMA tính bảo mật của sơ đồ chữ ký thu được từ phép biến đổi Fiat-Shamir.
Nhớ lại phép biến đổi Fiat-Shamir bắt đầu từ giao thức nhận dạng 3 bước với các thông báo $(I, r, s)$, ở đâu $I$ là lời cam kết, thử thách của người chứng minh $r$ được chọn ngẫu nhiên đều trong tập hợp $\Omega$ bởi người xác minh, $s$ là bằng chứng. Nó sử dụng hàm băm $H$ vào trong $\Omega$.
Tạo cặp khóa $(\mathrm{pk},\mathrm{sk})$ trong lược đồ chữ ký giống như trong giao thức nhận dạng. Để ký tin nhắn $M$, tục ngữ tạo ra $I$ như trong giao thức nhận dạng, tính toán $r:=H(I,M)$, sau đó $s$ như trong giao thức nhận dạng, sau đó là chữ ký¹ $\sigma:=(I,s)$. Thuật toán xác minh tính toán $r:=H(I,M)$ sau đó áp dụng quy trình xác minh tương tự như giao thức nhận dạng, đó là kiểm tra $\mathcal V(\mathrm{pk},r,s)=I$.
Qua định lượng, ý tôi là chúng ta cho rằng một đối thủ có thể phá vỡ sơ đồ chữ ký với xác suất ít nhất $\epsilon$ với thời gian / nỗ lực $t$, $Q_S$ truy vấn đến lời tiên tri chữ ký, $Q_H$ các truy vấn tới nhà tiên tri hàm băm và đạt được một số giới hạn trên về xác suất so với việc kẻ thù có thể phá vỡ sơ đồ nhận dạng với một chút thời gian/nỗ lực.
Tôi ổn với một giới hạn nằm trong hệ số không đổi từ tối ưu; yêu cầu bất kỳ thuộc tính hợp lý nào trong sơ đồ nhận dạng 3 bước, chẳng hạn như $I$ là ngẫu nhiên thống nhất trong một số tập hợp đủ lớn; $H$ được mô hình hóa như một nhà tiên tri ngẫu nhiên; bất kỳ thuật toán nào là thời gian đa thức ngẫu nhiên hoặc thậm chí được xác định (bao gồm cả việc sử dụng PRG được gieo bằng $\mathrm{sk}$ và $M$ cho băng ngẫu nhiên của thuật toán tạo $I$, do đó làm cho chữ ký xác định).
Tôi biết một tài liệu tham khảo tiêu chuẩn là của David Pointcheval và Jacques Stern Đối số bảo mật cho chữ ký số và chữ ký mù, Trong Tạp chí Mật mã học, 2000, nhưng tôi muốn thứ gì đó đơn giản và tập trung hơn.
¹ Chữ ký cũng có thể là $\sigma:=(r,s)$ hoặc $\sigma:=(I,r,s)$và có một sự giảm bớt bảo mật chặt chẽ, tương đối đơn giản giữa ba loại.
