solution

Tiếp nối ý tưởng chữ ký Lamport: để ký thông điệp có bản băm là chuỗi bit $m_1 m_2 \dots m_n$ ($m_i \in \{0,1\}$), người ký tiết lộ $sk_{i,m_i}$ cho mỗi vị trí $i$ (tức lộ nửa khoá bí mật tương ứng với giá trị bit thực tế của thông điệp, giữ bí mật nửa còn lại). Chữ ký là dãy $n$ chuỗi $\sigma_1, \dots, \sigma_n$.

Người xác thực có khoá công khai $(pk_{i,0}, pk_{i,1})_{i=1}^n$ (với $pk_{i,b} = \text{SHA256}(sk_{i,b})$) và biết trước chuỗi bit thông điệp. Chữ ký hợp lệ khi và chỉ khi với mọi $i$: $\text{SHA256}(\sigma_i) = pk_{i, m_i}$.

Cho khoá công khai, chuỗi bit thông điệp và chữ ký, hãy xác định chữ ký có hợp lệ hay không.

Ví dụ

Input:

1
0
65ed28e30a4315cf7a4c2ed441fbce32dd375844660572eb06725d2d1dfa4c89 f8ddd97541a41777b2561694bf24c1ce374e6ed9a195e0003b0a2121dca1c3e7
only0

Output:

VALID

(Vì SHA256(only0) trùng với $pk_{1,0}$, đúng với bit thông điệp là 0.)