Tham gia Đăng nhập
Điểm:3
einsteinwein avatar Crypto

Yêu cầu hàm băm cho Chữ ký Schnorr ngắn

lá cờ st
einsteinwein

Neven et al. nêu trong bài báo của họ Yêu cầu hàm băm đối với chữ ký Schnorr định lý sau (sử dụng bổ đề forking): $\mathbb{G}$ là nhóm chung (phần 2), $s \approx \log_2q$, hàm băm $H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$.

Định lý 1 Nếu bài toán logarit rời rạc trong $\mathbb{G}$ Là $(t_\text{dlog}, \epsilon_\text{dlog}$-hard, thì Chữ ký Schnorr là $(t_\text{uf-cma}, q_S,q_H, \epsilon_\text{uf-cma})$-an toàn cho $ \epsilon_\text{uf-cma} = \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}} + \frac{q_H+q_S+1}{2^n} + \frac{q_S( q_H+q_S+1)}{q}$ và $t_\text{uf-cma}= t_\text{tdlog}/2 â q_S t_\text{exp} + \mathcal{O}(q_H + q_S + 1)$, ở đâu $t_\text{exp}$ là chi phí của một lũy thừa trong nhóm $\mathbb{G}$.

Họ kết luận rằng giới hạn này chỉ ra rõ ràng rằng một hàm băm với $n = s/2$ bit đầu ra phải đủ để có được mức độ bảo mật của $s/2$ chút ít. Một thuật ngữ của hình thức $q_H^2/2^n$ sẽ khuyên dùng hàm băm s-bit.

Ai đó có thể giải thích điều này chi tiết hơn một chút cho tôi?

169
0 + 0
Điểm:2
Ievgeni avatar Crypto
lá cờ cn
Ievgeni

Đây, $k$ bit bảo mật có nghĩa là lợi thế là nhiều nhất $O\left(\frac{T^\alpha}{2^{\alpha k}}\right)$, sau khi làm $T$ hoạt động (của tất cả các loại) được thực hiện bởi đối thủ. Với chủ nghĩa hình thức này, nó cho phép chúng ta kết luận rằng đối thủ cần phải làm $O(2^k)$ "hoạt động" để phá vỡ hệ thống ($T^\alpha \approx2^{\alpha k}\implies T \approx 2^k$).

Sau đó, chúng tôi đã xem xét chi tiết tất cả các điều khoản trong tổng.

Khi chúng ta nhìn vào thuật ngữ thứ ba: $\frac{q_S(q_H+q_S+1)}{q}\leq\frac{T}{q}$, không sao đâu.

nhiệm kỳ thứ hai $\frac{q_H+q_S+1}{2^n}=O(T2^{-n})$: Và nếu chúng ta muốn có thuật ngữ này trong $O(T2^{-s/2})$, chúng ta cần phải có $n\geq s/2$, (Gợi lại $n$ là kích thước đầu ra của hàm băm).

Về thuật ngữ đầu tiên, nó phức tạp hơn một chút: $\sqrt{(q_H+q_S+1)\epsilon_\text{dlog}}\leq\sqrt{T2^{-s/2}}$, nhưng cũng không sao (với $\alpha=\frac{1}{2}$).

0 + 0
einsteinwein avatar
lá cờ st
einsteinwein
Và có lẽ bạn biết tôi có thể tìm chứng minh của định lý này ở đâu? Bài báo chỉ nói rằng đó không phải là một kết quả mới, nhưng không đưa ra nguồn.
0
Hồi đáp
Ievgeni avatar
lá cờ cn
Ievgeni
Họ nói rằng đó là hệ quả của Đa chữ ký trong khóa công khai đơn giản mô hình và một bổ đề forking tổng quát.
1
Hồi đáp
einsteinwein avatar
lá cờ st
einsteinwein
Ổn thỏa. Cảm ơn bạn rất nhiều vì câu trả lời của bạn!
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.