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

Fiat-Shamir heuristic là một kỹ thuật mật mã dùng biến một hệ thống chứng minh tương tác thành một hệ thống chứng minh không tương tác (non-interactive proof system).

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'$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'$ - 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'$?

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$