Fiat-Shamir Heuristic - Mô hình Non Interactive ZK đơn giản

Vấn đề

Alice (Prover) muốn thuyết phục Bob (Verifier) là cô ta biết một giá trị \(s\) mà lại không muốn để lộ giá trị này.

Các bước thực hiện

Public parameters - là những giá trị cả Alice và Bob đều biết, bao gồm:

• Số nguyên tố \(p\)

• Generator \(g\) của \(\mathbb F_p\)

• Giá trị \(g^s\), với giả định độ khó của log rời rạc (discrete logarithm problem): biết \(g^s\) nhưng không thể suy ra \(s\)

• Một hàm Hash mật mã (Cryptographic Hash) \(H\), như SHA256 chẳng hạn.

Bước 1 - Tạo Commitment

• Alice chọn một số ngẫu nhiên \(r\)

• Tính giá trị commitment \(C=g^r \mod p\)

• Alice gửi \(C\) cho Bob

Bước 2 - Tạo Challenge

• Alice tự sinh ra một challenge bằng cách tính \(c = H(C, \text{[public parameters]})\)

• Hàm \(H\) có thể dùng hàm \(SHA256\) hoặc động như một random oracle - bảo đảm tính không thể đoán trước

• Các public parameters có thể đưa thêm vào tùy ý, bao gồm \(p,g,g^s\)

Bước 3 - Tạo Response

• Alice tính response \(r^{\prime} = r + c.s \mod (p-1)\)

• Alice gửi \(r^{\prime}\) cho Bob

Bước 4 - Verify

Lúc này Bob có các thông tin:

• \(p,g,g^s\) - public parameters

• \(C, r^{\prime}\) - nhận từ Alice

• \(c\) - Bob có thể tự tính được từ \(C\)

Và sẽ cần verify: \(g^{r^{\prime}} = C.(g^s)^c \mod p\)

Tại sao \(\mod (p-1)\) khi tính \(r^{\prime}\)?

Theo định lý Fermat Nhỏ: Nếu \(p\) là số nguyên tố thì \(g^{p-1} \equiv 1 (\mod p)\).

Giả sử \(s = (p-1).k + m\), ta có: \(g^x = g^{(p-1).k + m} = g^{k(p-1)}g^m = g^m (\mod p)\)

Như vậy: \(g^{r+c.s \mod (p-1)} = g^{r+c.s} (\mod p)\)

Sự hợp lý của bước Verify

Ta có \(g^{r^{\prime}} = g^{c.s+r \mod (p-1)} = g^{c.s+r} = (g^s)^c.g^r = C.(g^s)^c \mod p\)