gần đây tôi đã đọc báo Phương pháp tiếp cận không phải PCP đối với Kiến thức không an toàn lượng tử ngắn gọn.
Trong số những thứ khác, nó thảo luận về sự thích ứng của kỹ thuật "gấp" (từ Bulletproofs) sang bằng chứng dựa trên SIS.
Bài báo đo khoảng cách trong $\ell_\infty$ chuẩn mực (chứ không phải là $\ell_2$) và không rõ ràng về việc sử dụng lựa chọn nhúng nào (mặc dù tôi tưởng tượng đó là nhúng hệ số).
Những lựa chọn này có nghĩa là họ nhận thêm các yếu tố của $n$ khi đặt giới hạn chuẩn của phép nhân nói riêng.
Ví dụ, tại một thời điểm (ở trang 20) họ muốn thiết lập một giới hạn
$$\lVert 8\lambda_i\rVert_\infty \leq 2n^2$$
ở đâu $\lambda_i$ có dạng
$$\lambda_i = \pm\frac{f}{(X^u-X^v)(X^v-X^w)(X^w-X^u)},$$
$\lVert f\rVert_1 \leq 2$, và được biết rằng $2/(X^i-X^j)$ có hệ số trong $\{-1,0,1\}$ vì $i\neq j$.
tôi có thể thiết lập các ràng buộc mong muốn như sau
Viết $$8\lambda_i = \pm f \frac{2}{X^u-X^v}\frac{2}{X^v-X^w}\frac{2}{X^w-X^u}$$
Đối với mỗi phép nhân, hãy sử dụng kết quả có dạng $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty\lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$. Đặc biệt, đối với sản phẩm và $r, s$ không thưa thớt, chúng tôi có điều đó $\min(\lVert r\rVert_0,\lVert s\rVert_0) \leq n$, mất chúng tôi một yếu tố của $n$ trên mỗi phép nhân (không liên quan đến $f$) và hệ số 2 đối với phép nhân liên quan đến $f$.
sự bất bình đẳng $\lVert rs\rVert_\infty \leq \lVert r\rVert_\infty \lVert s\rVert_\infty \min(\lVert r\rVert_0,\lVert s\rVert_0)$ (hoặc một cái gì đó rất gần với nó --- có lẽ thiếu hệ số không đổi là 2) nên giữ nguyên như mỗi hệ số trong tích $rs$ là tích chập của các hệ số của $r$ và $s$.
tích chập này có $\min(\lVert r\rVert_0, \lVert s\rVert_0)$ nhiều số hạng khác 0 và mỗi số hạng khác 0 này có kích thước tối đa $\lVert r\rVert_\infty \lVert s\rVert_\infty$.
Đặc biệt, điều này có nghĩa là khi phân tích $\lVert rs\rVert_\infty$, họ thường (ngầm) ràng buộc điều này như $\lVert rs\rVert_\infty \leq n\lVert r\rVert_\infty\lVert s\rVert_\infty$, chọn một yếu tố bổ sung của $n$ cho mỗi phép nhân (ngoại trừ phép nhân với $f$, đó là thưa thớt).
Điều này trái ngược với phân tích trong nhúng chính tắc (và $\ell_2$-norm), trong đó phép nhân phụ sẽ nhận được một
$$\lVert 8\lambda_i\rVert_2^{can} \leq \lVert f\rVert_2^{can}(\lVert 2/(X^i-X^j)\rVert_2^{can})^3$$
chọn không có yếu tố phụ của $n$ trên đường đi (mặc dù tôi tin rằng $\lVert r\rVert_2^{can} = \sqrt{n}\lVert r\rVert_2$, vì vậy có thể có một số yếu tố tiềm ẩn của $n$ nhặt được).
Tôi đoán câu hỏi tổng thể của tôi là
Có một số lý do khái niệm tại sao nhúng chính tắc dường như ít phổ biến hơn trong công việc trên các hệ thống bằng chứng dựa trên mạng?
Tôi đã có ấn tượng rằng khi một người muốn tối ưu hóa các giới hạn (đặc biệt là các giới hạn liên quan đến phép nhân!) thì cách nhúng chính tắc nói chung là thích hợp hơn do phép nhân phụ.
Nhưng trong bài đọc lướt qua của tôi, việc nhúng hệ số có vẻ phổ biến hơn trong các công trình về các hệ thống chứng minh và tôi muốn biết tại sao.
