Tôi đang cố gắng phân tích trò chơi "tính độc đáo" xung quanh chữ ký của Schnorr. Trò chơi được mô tả trong $\textbf{B.}$ và tôi cố gắng cung cấp trong $\textbf{1.}$ và $\textbf{2.}$ một số câu trả lời không đầy đủ để giải quyết nó. Có thể giải quyết triệt để không? Tôi đã không sử dụng trong phân tích của mình một sự rút gọn đối với vấn đề DL; có lẽ có cách nào để giảm trò chơi xuống nó? Xin lỗi vì sự thiếu chặt chẽ về mật mã và cảm ơn rất nhiều vì đã đọc
$ \textbf{A. Giả thuyết mật mã:}$
Chúng tôi sẽ sử dụng hàm băm mật mã an toàn $H$ đầu ra trong $\mathbb Z_n$, ở đâu $n$ là bậc của đường cong, giả sử là số nguyên tố. Ta giả sử thứ tự nguyên tố là một số nguyên tố của $256$ chữ số khi viết trong cơ số $2$.
$\textbf{B. Trò chơi mật mã:}$
Giả sử một điểm đường cong elip $S$ đã được tính toán sau khi đã chọn một tuple $\{R,X,m\}$, ở đâu $S := R + H(X,R,m).X$ như trong chữ ký Schnorr, thực tế chúng ta có thể tìm thấy một bộ $\{R',X',m'\}$ Như là $\{R',X',m'\} \neq \{R,X,m\}$ (ít nhất một trong các phần tử khác nhau trong hai tập hợp) xác minh $R' + H(X',R',m').X' = S = R + H(X,R,m).X$ ?
Chúng tôi đưa ra giả định bổ sung rằng bộ dữ liệu $\{X,R,m\}$ có thể được chọn bởi đối thủ trước trận đấu, tức là bộ $\{X,R,m\}$ không được cung cấp cho anh ta bởi người xác minh.
$\textbf{1. Giả sử kiến thức về logarit rời rạc của $S$:} $
Nếu trò chơi trên cũng yêu cầu cung cấp bằng chứng về kiến thức logarit rời rạc của S cho người xác minh (nghĩa là kiến thức về $s$ như vậy mà $s.G = S$, hay nói cách khác, đã bắt đầu bằng một chữ ký Schnorr hợp lệ), có vẻ như câu trả lời là phủ định.
Tạm thời cho rằng $\{X,R, m\}$ và tương ứng $s$ được người xác minh cung cấp trực tiếp cho đối thủ, sử dụng các ký hiệu tự nhiên, đối thủ cần tìm $r', x'$ và $m'$ như vậy mà $r' + H(X',R',m').x' = s$. Có vẻ như cách duy nhất để làm điều này, với điều kiện là cộng hai số nguyên ngẫu nhiên modulo $n$ cùng nhau (ở đây $r'$, được chọn ngẫu nhiên và $H(X',R',m').x'$, một modulo số nguyên ngẫu nhiên $n$ do hàm băm là một giả định được bảo mật bằng mật mã) dẫn đến một modulo số nguyên ngẫu nhiên $n$, là kết quả của tổng 2 số nguyên ngẫu nhiên phân phối đều theo modulo $n$ là một modulo số nguyên ngẫu nhiên phân phối đều $n$. Chúng ta có thể bỏ qua tin nhắn $m$ cho trò chơi này và cưỡng bức đầu vào $r'$, $x'$ (hoặc tương đương chỉ là cưỡng bức vũ phu trên $r'$) dường như là giải pháp duy nhất để giành chiến thắng trong trò chơi, khiến trò chơi trở nên thú vị $256$bảo mật -bit và do đó không thể kiểm soát được. Tôi tự hỏi nếu lý do là chính xác hoặc nếu điều này là sai?
Quay trở lại giả thuyết ban đầu của $\textbf{B.}$, có vẻ như điều này trên thực tế có thể giới hạn trên trò chơi $128$bảo mật -bit (cũng là một khó khăn không thể giải quyết được, nhưng nó chỉ là giới hạn trên ở đây) thay vì $256$ khi nào $\{X, R, m\}$ có thể được chọn bởi đối thủ (và không được cung cấp cho anh ta). sửa chữa $x'=x$ và $r$ và $r'$, đối thủ có thể giải bài toán Sinh nhật và tìm một số $m$ và $m'$ (bằng cách áp dụng thuật toán Sinh nhật) xác minh mối quan hệ dưới đây, đây là một giải pháp cho trò chơi:
$H(X,R,m) - H(X,R',m') = (r' - r).x^{-1}$.
$\textbf{2. Không giả định kiến thức về logarit rời rạc của $S$:} $
Tôi không chắc chắn rằng các đối số trên trong $\textbf{1.}$ gần đúng, nhưng tình huống này có vẻ khó nghiên cứu hơn một chút.
$\textit{2. a) Giả sử biết logarit rời rạc của nonce:}$
Để thắng trò chơi này, người ta cũng phải cung cấp bằng chứng về kiến thức logarit rời rạc cho cả hai $R$ và $R'$ (một bằng chứng về kiến thức như vậy là đủ nếu $R' = R$). Để cố gắng giải quyết câu hỏi, chúng tôi giả sử rằng ai đó đã thắng trò chơi, nghĩa là bằng cách trừ đi hai mối quan hệ mà người chiến thắng trò chơi phải biết $u$ như vậy mà:
$$u.G = H(X, R, m).X - H(X',R', m').X'.$$
Giả sử rằng trò chơi thắng với $X = X'$, sau đó, nó có nghĩa là logairthm rời rạc của $X$ phải được biết vì nó phải đúng là $u.G = (H(X, R, m) - H(X,R', m')).X$, và do đó chúng ta ở trong trường hợp của $\textbf{1.}$.
Nếu $R = R'$ ($X'$ có thể bằng hoặc không bằng $X$), sau đó chúng tôi quay trở lại trong trường hợp cụ thể khi $u=0$, và chúng ta có cái đó $X' = H(X, R, m).H(X',R, m')^{-1}.X$, tức là logarit rời rạc $a$ của $X'$ đối với $X$ phải xác minh $a = H(X, R, m).H(X',R, m')^{-1}$. sửa chữa $X$ và $X'$ như vậy mà $X' = a.X$ cho một số $a$, thuật toán tốt nhất để giải quyết vấn đề này dường như lại là thuật toán Sinh nhật với đầu vào xung quanh $2^{128}$ các thông điệp khác nhau trong các thử thách để cuối cùng tìm thấy một số $m$ và $m'$ xác minh đó $a.H(X',R, m') - H(X, R, m) = 0$.
Nếu cả hai $X \neq X'$, và $R \neq R'$, tôi không quản lý để tìm thấy bất kỳ kết luận tiềm năng. Có ai biết câu trả lời hoặc tài liệu tham khảo cho trường hợp này không?
$\textit{2. b) Giả sử biết logarit rời rạc của khóa công khai:}$
Chúng tôi dường như rơi trở lại trường hợp $R = R'$ của $\textit{2. a)}$ nếu $R = R'$, nhưng tôi không quản lý để kết luận nếu $R \neq R'$.
$\textit{2. c) Giả sử không biết logarit rời rạc đối với nonce và khóa:}$
Một lần nữa chúng ta có thể kết luận nếu $R = R'$ bằng cách sử dụng cùng một lập luận như trường hợp trong $\textit{2. a)}$ cho trường hợp $R = R'$, nhưng lại có vẻ khó kết luận khác hơn (tức là nếu $R \neq R'$).
