"The Tuyen Optimization" notes

Hôm rồi mình đọc được trên facebook của người bạn về thuật toán này. Đây là một thuật mang tên người Việt Nam (theo như chia sẻ của Facebook ấy). Thật đáng tự hào! Trong note này mình cố gắng giải thích một số điểm mấu chốt của thuật toán, hy vọng có thể giúp các bạn dễ dàng hơn khi tìm hiểu nó.

Note này đa số dựa trên bài viết gốc này.

Scenario

Giả sử chúng ta có một thông điệp được xác thực bởi chữ ký điện tử của nhiều người trên blockchain, như vậy để xác thực, chúng ta phải xác thực chữ ký của từng người. Tuy nhiên việc này tốn kém vì mọi tính toán trên sẽ tốn chi phí gas, do đó, thay vì check từng chữ ký, ta sẽ “gộp” tất cả các chữ ký và validate 1 lần cho đỡ tốn (Batch verification).

Review về bilinear mapping / pairing

Lược đồ chữ ký kết hợp trên được thiết lập dựa trên nền tảng chữ ký BLS (Boneh–Lynn–Shacham) mà trung tâm của nó là ánh xạ song tuyến tính / cặp ghép.

Một cặp ghép \(e: \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T\) là một ánh xạ song tuyến tính giữa các nhóm \(\mathbb G_1, \mathbb G_2, \mathbb G_T\) với \(g_1, g_2,g_T\) lần lượt là các phần tử sinh của \(\mathbb G_1, \mathbb G_2, \mathbb G_T\). Một cặp ghép song tuyến tính thỏa mãn các điều kiện sau:

• Song tuyến tính: Với mọi \(u \in \mathbb G_1\) và \(v \in \mathbb G_2\), luôn có: \(e(u^a,v^b) = e(u,v)^{ab}\)

• Không suy biến: \(e(g_1,g_2) \ne 1_{\mathbb G_T}\)

• \(\mathbb G_1, \mathbb G_2, \mathbb G_T \) có cùng bậc $p$ nguyên tố.

Chữ ký BLS

• Message $m$

• Cho \(H:\{0,1\}^* \to \mathbb G_1\) là hàm hash biến một giá trị bất kỳ thành một phần tử của nhóm \(\mathbb G_1\).

• Secret key \(sk \in \mathbb Z_p\), public key \(pk = g_2^{sk} \in \mathbb G_2\)

• Để tạo chữ ký cho $m$, ta tính \(\sigma = H(m)^{sk} \in \mathbb G_1\)

• Để verify chữ ký, kiểm tra: \(e(\sigma,g_2) \stackrel{?}{=} e(H(m),pk)\). Lý do là vì:

$$\begin{align*} e(\sigma, g_2) &\stackrel{?}{=} e(H(m), pk) \Leftrightarrow\\ e(H(m)^{sk}, g_2) &\stackrel{?}{=} e(H(m), g_2^{sk}) \Leftrightarrow\\ e(H(m), g_2)^{sk} &\stackrel{?}{=} e(H(m), g_2)^{sk} \Leftrightarrow\\ e(H(m), g_2) &= e(H(m), g_2) \end{align*}$$

Chữ ký kết hợp

Giả sử có $n$ chữ ký \(\sigma_1,\sigma_2, \dots, \sigma_n \in \mathbb G_2\) trên message \(H(m) \in \mathbb G_1\) với các secret key \(sk_1,sk_2,\dots,sk_n \in \mathbb Z_p\) và public key tương ứng \(pk_1,pk_2,\dots,pk_n \in \mathbb G_2\). Ta có thể kết hợp toàn bộ các chữ ký này lại thành một chữ ký tổng hợp \(\sigma_{agg}\) và nhờ đó chỉ cần verify chữ ký này một lần duy nhất.

Bước 1: Tạo chữ ký tổng hợp

$$\sigma_{agg} = \sum_{i=1}^{n} \sigma_i = \sum_{i=1}^{n} (sk_i \cdot H(m)) = \left(\sum_{i=1}^{n} sk_i\right) \cdot H(m)$$

Bước 2: Tạo public key tổng hợp

$$pk_{agg} = \sum_{i=1}^{n} pk_i = \sum_{i=1}^{n} (sk_i \cdot g)= \left( \sum_{i=1}^{n} sk_i\right) \cdot g$$

Bước 3: Verification

$$e(g, \sigma_{agg}) = e\left(g, \left(\sum_{i=1}^{n} sk_i\right) \cdot H(m) \right) = e\left(\left( \sum_{i=1}^{n} sk_i\right) \cdot g, H(m) \right) = e\left(pk_{agg}, H(m)\right)$$

Tấn công Rogue Public Key

Việc kết hợp các chữ ký như trên tuy có lợi ích về mặt tính toán nhưng lại không an toàn vì có thể bị tấn công như sau:

• Giả sử một user là Bob, có public key là \(pk_1\)

• Kẻ tấn công sẽ tính \(pk_1^{-1} \in \mathbb G_2\), sau đó chọn một public key \(pk_2 = g_1^{\beta}\cdot(pk_1)^{-1} \in \mathbb G_1\), với \(\beta\) được chọn ngẫu nhiên trong \(\mathbb Z_p\).

Lúc này attacker có thể tuyên bố chữ ký của hắn cũng là một thành phần trong chữ ký kết hợp trên $m$ bằng cách đưa ra chữ ký kết hợp của hắn và Bob \(\sigma = H(m)^{\beta}\). Chữ ký \(\sigma\) này hợp lệ vì vẫn đảm bảo bước kiểm tra:

$$e(g_1,\sigma) = e\big(g_1,\ H(m)^\beta \big) = e\big(g_1^\beta,\ H(m)\big) = e\big(pk_1 \cdot pk_2,\ H(m)\big).$$

Điều này dẫn đến việc attacker có thể ngụy tạo việc Bob và hắn đã ký lên $m$, mặc dù Bob chưa hề ký.

Khắc phục bằng Tuyen Optimization

Để khắc phục tấn công như trên, Tuyen Optimization đề nghị phương pháp che giấu cặp chữ ký và public key bằng cách nhân scalar thêm một giá trị ngẫu nhiên \(r_i \in \mathbb Z\) cho mỗi public key \(pk_i\). Lúc này, chữ ký đã được che giấu sẽ được verfier kiểm tra phương trình:

$$e\left(g, \sum_{i=1}^{n} (r_i \cdot \sigma_i)\right) \stackrel{?}{=} e\left(\sum_{i=1}^{n} (r_i \cdot pk_i), H(m) \right)$$

Nếu chữ ký hợp lệ, phương trình trên sẽ thỏa vì:

$$\begin{aligned} e\left(g, \sum_{i=1}^{n} (r_i \cdot \sigma_i)\right) &= e\left(g, \sum_{i=1}^{n} (r_i sk_i \cdot H(m)) \right) & \\ &\stackrel{}{=} e\left(g, \left(\sum_{i=1}^{n} r_i sk_i\right) \cdot H(m) \right) &\\ &= e\left(\left( \sum_{i=1}^{n} r_i sk_i\right) \cdot g, H(m) \right) &\\ &\stackrel{}{=} e\left(\sum_{i=1}^{n} (r_i sk_i \cdot g), H(m) \right) & &= e\left(\sum_{i=1}^{n} (r_i \cdot pk_i), H(m)\right) \end{aligned}$$