證明、論證以及零知識

JustinThaler 李星 張守恆 葉經緯

證明、論證以及零知識
  • 出版商: 東南大學
  • 出版日期: 2024-12-01
  • 定價: $768
  • 售價: 8.5 折 $653
  • 語言: 簡體中文
  • 頁數: 352
  • ISBN: 7576617128
  • ISBN-13: 9787576617122
  • 此書翻譯自: Proofs, Arguments, and Zero-Knowledge

    • 下單後立即進貨 (約4週~6週)

商品描述

本書全面系統地闡述了零知識證明算法的理論礎，設計方法以及截止到2022年主流零知識證明法的分類。從最基礎的加密學原理講起，本書闡了不同計算覆雜性模型下的簡潔交互式論證構建並詳細描述了通用程序和可滿足性電路之間的轉，通過多項式承諾方案實現簡潔論證以及多項式諾方案的多種實現。第1章到第3章介紹基礎概念及闡述交互式證明依賴強大的隨機性。第4章、8章、第9章、第10章、第17章，從計算覆雜性模角度（IP／MIP／PCP／IOP），闡述了交互式論系統構建的不同方法和性能。MIP＝PCP，並且多式IOP統一了IP、MIP以及IOP。第5章介紹了iat－Shamir算法，將任意公開擲幣交互式論證轉為非交互式論證。第6章介紹如何將通用的圖靈序轉化為電路，並解釋了算術電路實例轉化為可足性電路實例的原因。第7章引入多項式承諾方以及低次測試，實現簡潔交互式論證的雛形。第1章、第13章介紹零知識的定義以及零知識實現的種方式：承諾－證明以及掩碼多項式。第12章、14章、第15章、第16章介紹承諾方案，並總結了項式承諾方案的三種方式：基於IOP（第10章）基於離散對數難問題以及基於配對。第18章介紹SNARK的組合和遞歸。第19章是對本書中講述的有零知識證明算法的分類總結。

目錄大綱

第1章  介紹
  1.1  數學證明
  1.2  我們將學習哪些非傳統的證明？
第2章  強大的隨機性：指紋法和Freivalds算法
  2.1  Reed-Solomon編碼
  2.2  算法
  2.3  指紋法和Freivalds算法的另外一個角度
  2.4  單變量拉格朗日插值
第3章  定義和預備技術
  3.1  交互式證明
  3.2  論證系統
  3.3  定義的魯棒性和交互的強大
  3.4  Sehwartz-Zippel引理
  3.5  低次和多線性擴展
  3.6  練習
第4章  交互式證明
  4.1  協議
  4.2  sum-check的第一個應用：#SAT∈IP
  4.3  第二個應用：計算圖中三角形個數的簡單交互式證明
  4.4  第三個應用：MATMUT的超高效IP
  4.5  超高效MATMULTIP的一些應用
  4.6  GKR協議及其高效實現
  4.7  練習
第5章  通過Fiat-Shamir獲得公開可驗證的非交互式論證
  5.1  隨機預言機模型
  5.2  Fiat-Shamir變換
  5.3  變換的安全性
  5.4  練習
第6章  前端：將計算機程序轉換為電路
  6.1  簡介
  6.2  機器碼
  6.3  第一種將程序轉換為電路的技術
  6.4  將小空間程序轉換為淺電路
  6.5  將計算機程序轉換為電路可滿足性實例
  6.6  其他的變換方式和優化
  6.7  練習
第7章  第一個簡潔的交互式論證——解決電路可滿足性問題
  7.1  樸素方法：一種針對電路可滿足性問題的交互式證明
  7.2  電路可滿足性問題的簡潔證明
  7.3  第一個電路可滿足性問題的簡潔論證
  7.4  知識可靠性
第8章  MIP以及簡潔論證
  8.1  MIP的定義和基本結論
  8.2  一個電路可滿足性的高效MIP
  8.3  深度電路的簡潔論證
  8.4  從電路-SAT到R1CS-SAT的擴展
  8.5  MIP-NEXP
第9章  PCP與簡潔論證
  9.1  PCP：定義及與MIP的關系
  9.2  將PCP編譯為簡潔論證
  9.3  從MIP到第一個長度為多項式的PCP
  9.4  電路可滿足性問題的準線性長度的PCP
第10章  交互式預言機證明
  10.1  IOP：定義和相關的簡潔論證
  10.2  多項式IOP和相關的簡潔論證
  10.3  R1CS-可滿足性的多項式IOP
  10.4  FRl和相關的多項式承諾
  10.5  Ligero和Brakedown多項式承諾
  10.6  通過多項式IOP統一IP、MIP、IOP
第11章  零知識證明和論證
  11.1  零知識的定義
  11.2  統計零知識（SZK）證明的局限
  11.3  誠實驗證者SZK（HVSZK）協議——解決圖非同構問題
  11.4  誠實驗證者SZK協議——解決碰撞問題
第12章  ∑-協議和基於離散對數困難的承諾
  12.1  密碼學背景
  12.2  離散對數知識的Schnorr∑-協議
  12.3  同態承諾方案
第13章  通過承諾-證明和掩碼多項式實現零知識
  13.1  證明長度等於證據的長度加上乘法覆雜度
  13.2  去除對乘法覆雜性的線性依賴：從1P到零知識論證系統
  13.3  通過掩碼多項式實現零知識
  13.4  討論和對比
第14章  基於離散對數難題的多項式承諾
  14.1  承諾規模為線性大小的零知識方案
  14.2  承諾是固定大小，求值證明是線性大小
  14.3  權衡承諾大小與驗證成本
  14.4  Bulletproofs
第15章  基於配對的多項式承諾
  15.1  密碼學背景
  15.2  KZG：使用配對和可信設置的單變量多項式承諾
  15.3  多線性多項式的KZG擴展
  15.4  Dory：具有對數級別驗證成本的透明方案
第16章  多項式承諾總結
  16.1  同態承諾多項式的批量求值
  16.2  稀疏多項式的承諾方案
  16.3  多項式承諾方案的優缺點
  16.4  其他方法
第17章  線性PCP與簡潔論證
  17.1  概述：來自“長”結構化PCP的交互式論證
  17.2  承諾線性PCP而不實例化
  17.3  算術電路可滿足性問題的第一個線性PCP
  17.4  GGPR：一個大小為O（丨F丨s）的線性PCP，適用於電路可滿足性問題和R1CS
  17.5  非交互性和公開可驗證性
第18章  SNARK組合與遞歸
  18.1  組合兩個不同的SNARK
  18.2  更深層次的SNARK組合
  18.3  SNARK組合的其他應用
  18.4  通過遞歸構建用於疊代計算的SNARK
  18.5  通過同態承諾實現疊代計算的SNARK
第19章  實用論證的鳥瞰視圖
  19.1  SNARK分類
  19.2  論證方法的優缺點
  19.3  影響具體效率的其他問題
致謝
附錄  翻譯詞匯表
參考文獻

類似商品