7.1. Giới thiệu

Zero Knowledge Proof (ZKP) là một protocol mật mã cho phép một bên thuyết phục bên còn lại rằng họ sở hữu những thông tin quan trọng mà không để lộ bất cứ gì về chính thông tin quan trọng đó.

Khi đó, bên thuyết phục được gọi là prover, bên đưa ra thử thách để prover chứng minh bản thân gọi là challenger hoặc verifier.

Tính chất của zero knowledge proof

Mỗi protocol zero-knowledge phải đảm bảo ba tính chất sau:

  1. Completeness (tính đầy đủ): nếu mệnh đề đúng thì verifier có thể xác nhận và bị thuyết phục bởi prover.

  2. Soundness: nếu mệnh đề sai thì prover không thể thuyết phục verifier rằng nó đúng.

  3. Zero-knowlegde: verifier không biết gì về tính đúng sai của mệnh đề.

Lấy một ví dụ đơn giản để xem cách hoạt động của ZKP là protocol QR [1].

7.1.1. Protocol PQ

Mệnh đề cần kiểm tra: \(x\) là một thặng dư chính phương modulo \(n\). Prover muốn chứng minh với verifier rằng mình biết căn bậc hai của \(x\) trong modulo \(n\).

7.1.1.1. Public input

Số \(x\) và modulo \(n\), với \(0 \leqslant x < n\).

7.1.1.2. Quá trình tạo proof

Quá trình tạo proof (thuyết phục) diễn ra như sau:

Prover (Alice)

Verifier (Bob)

Public input: \(x \pmod n\)

Private input: \(w \pmod n\) thỏa \(x = w^2 \pmod n\)

Chọn ngẫu nhiên số \(u\) từ \(\mathbb{Z}_n^*\)

Gửi Bob \(y = u^2 \pmod n\)

Chọn ngẫu nhiên \(b \in \{ 0, 1 \}\)

Gửi \(b\) cho Alice

Gửi \(z = w^b \cdot u\) cho Bob

7.1.1.3. Quá trình verification

Gọi \(z\) là số được gửi bởi Alice. Bob kiểm tra

\[z^2 \stackrel{?}{=} x^b \cdot y.\]

Như vậy:

  1. Nếu \(b = 0\) thì \(z^2 = y = u^2\pmod n\).

  2. Nếu \(b = 1\) thì \(z^2 = xy = (wu)^2 \pmod n\).

7.1.1.4. Nguyên lí hoạt động

Bob chỉ biết \(x\) và \(n\) trong khi Alice biết căn bậc hai của \(x\) modulo \(n\).

Ở đây Alice muốn thuyết phục Bob rằng mình biết căn bậc hai của \(x\) trong modulo \(n\).

Nếu Alice thật sự biết căn bậc hai của \(x\) là \(w\), hay \(x = w^2 \pmod n\), thì Alice cần chứng minh cho Bob thấy.

  1. Alice chọn số random \(u \in \mathbb{Z}_n^*\) và gửi \(y = u^2 \pmod n\) cho Bob.

  2. Bob chọn ngẫu nhiên \(b \in \{ 0, 1 \}\) và gửi cho Alice.

Với mỗi trường hợp của \(b\):

  • nếu \(b = 0\) thì Alice cần tính căn bậc hai của \(y\) modulo \(n\) và gửi cho Bob. Đó chính là \(u\);

  • nếu \(b = 1\) thì Alice cần tính căn bậc hai của \(xy\) (\(x\) public và \(y\) được gửi trước đó). Ta có \(xy = w^2 u^2 \pmod n\) nên Alice cần gửi \(wu\). Nếu Alice thật sự biết căn bậc hai của \(x\) thì có thể tính được \(wu\);

Bob có thể kiểm tra số \(z\) được gửi tới có thỏa mãn \(z^2 = y \pmod n\) (nếu \(b = 0\)) hoặc thỏa mãn \(z^2 = xy \pmod n\) (nếu \(b = 1\)) hay không.

Trong ví dụ trên, ta thấy các tính chất của ZKP:

  1. Completeness: khi \(x\) thực sự là số chính phương modulo \(n\) và Alice có thể đưa số \(w\) sao cho \(x = w^2 \pmod n\) thì Bob sẽ chấp nhận với xác suất bằng \(1\). Điều này khá dễ thấy;

  2. Soundness: nếu \(x\) không là số chính phương modulo \(n\) thì Bob có thể bác bỏ chứng minh của Alice với xác suất ít nhất \(1/2\) (trong trường hợp \(b=1\)). Trong khi đó \(b = 0\) thì vẫn có "cơ may" đúng;

  3. Zero knowledge: Bob không biết bất cứ thông tin nào liên quan đến Alice nhưng Alice có thể thuyết phục Bob tin rằng mình biết căn bậc hai của \(x\). Zero knowledge có nghĩa là trong suốt quá trình Bob không biết thêm thông tin gì hơn từ Alice.

7.1.2. Mô hình Zero Knowledge Proof

Phần tiếp theo được tổng hợp từ một số nguồn dành cho newbie [2].

ZKP bao gồm ba bước là: key generation, proof generation và verification.

7.1.2.1. 1. Key generation

Bước này tạo các tham số để một bên proof và để bên còn lại verification.

Thông thường, ở bước này có một hàm \(C(x, w)\) nhận hai tham số là \(x\) (public input) và \(w\) (private input, witness).

Một tham số private là \(\lambda\) giúp việc sinh ra các tham số gồm public key \(pk\) và private key \(vk\).

Ký hiệu: \(\text{Setup}(C, \lambda) \rightarrow (pk, vk)\).

Trong đó \(pk\) được gửi cho prover để họ chứng minh bản thân (thuyết phục verifier rằng họ sở hữu thông tin).

Ngược lại, \(vk\) được gửi cho verifier để họ kiểm tra mệnh đề từ prover.

7.1.2.2. 2. Proof generation

Bước này thực hiện bởi prover để sinh ra giá trị gửi cho bên verifier kiểm tra.

Với đầu vào gồm private input là \(w\), public input là \(x\) và public key là \(pk\), prover sẽ tính toán prf rồi gửi cho verifier.

Ký hiệu: \(\text{Prove}(w, x, pk) \rightarrow \text{prf}\).

7.1.2.3. 3. Verification

Bước này thực hiện bởi verifier để kiểm tra mệnh đề prf được gửi từ prover.

Với đầu vào gồm public input \(x\), proof là prf và private key là \(vk\), verifier kiểm tra tính đúng đắn của prf.

Ký hiệu: \(\text{Verify}(x, \text{prf}, vk) \rightarrow\) đúng (nếu hợp lệ) hoặc sai (ngược lại).