下个月召开的密码学顶会
Crypto22中的零知识证明相关论文简介。看完摘要我直呼牛逼，谁说零知识证明学术理论研究已经结束，现在只剩工程应用的果子了？
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32215
新零知识论证系统Orion，域运算和哈希函数的O(N)的证明时间，O(log^2 N)证明大小。提出了一种基于最密集子图算法的新算法来测试随机二分图是否是无损扩展图。开发了一种有效的证明组合方案，代码转换，以将证明大小从平方根减少到多项式对数。
https://eprint.iacr.org/2022/819
提出恶意安全的VOLE扩展协议，将短的种子VOLE转换为同样环上的伪随机VOLE。新基于VOLE的证明系统QuarkSilver。
https://eprint.iacr.org/2021/370
实现增量可验证计算 (IVC)的新方法，完全避免使用SNARKs，而是使用折叠方案。常数递归开销，每步证明者开销由两个多指数支配，证明本身线性但使用已知zkSNARK可以对有效证证明进行简洁的零知识知识证明，不需要可信设置，不需要FFT。
https://eprint.iacr.org/2022/767
构造对NP语言的高效非延展零知识的新方法，基于新原语：基于实例的非延展承诺。第一个无需公钥假设的非延展承诺方案。
https://eprint.iacr.org/2022/820
假设：1.带错误学习问题的亚指数困难性，2.存在对稍微超多项式时间敌手的无密钥抗多碰撞哈希函数，构造了对NP的公开抛币3轮零知识论证系统。
https://eprint.iacr.org/2021/1259
说明了任何k_1,...,k_mu特殊可靠多轮公开抛币交互式证明系统，t路并发重复最优地降低了知识错误。结果泛化到t中取s门限并发重复，以同时降低知识错误和完备性错误。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32176
假设存在亚指数安全线性可计算抗碰撞哈希函数，对具有重复子结构等一大类布尔电路，构造IOP以及相应的简洁论证系统，证明者开销polylog(k)。
https://eprint.iacr.org/2022/281
简洁IOP，通信复杂度是证据的多项式（甚至线性），介绍其应用和局限。对空间受限NP关系，使用单向函数，展示如何保持证明长度同时编译IOP为零知识证明，通信复杂度几乎和证据长度相等，得到最小假设下最短的零知识证明。对更一般NP关系，证明在一个新复杂度理论猜想下，不存在对CSAT的简洁IOP。
https://eprint.iacr.org/2021/1315
提出对QMA的经认证的永久零知识证明，这是一种计算零知识证明，但验证者发送其已经删除所有的量子信息的经典证书。如果证书有效，达到统计零知识。引入原语：统计绑定和经认证的永久隐藏承诺方案，基于带证书删除的量子加密方案构造。并将其和对QMA的量子Sigma协议组合，在量子随机预言模型下得到对QMA的经认证的永久零知识证明。
https://eprint.iacr.org/2022/284
基于模SIS和模LWE问题困难假设，构造对满足As=t mod q的短向量s的知识证明系统。展示了证明s系数具有小的l2范式的更直接高效的方法。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32191
基于SIS的扩展假设，提出首个格基SNARK，同时满足：1. 后量子安全 2. 公开课验证 3. 对数时间验证者 4. 支持高效递归组合。将配对方案转译成格基方案的技术组件。新格基向量承诺方案，支持对常数阶多边量多项式映射的打开。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32247
提出基于格的对R1CS的亚线性大小零知识证明系统，证明大小是证据的平方根，比Ligero小2-3倍。Schwartz-Zippel引理的交互式变体。
https://eprint.iacr.org/2022/857
假设不可区分混淆和带错误学习的后量子安全，构造了通信复杂度和验证者运行时间是量子计算多项式对数的经典可验证简洁交互式论证系统，是首个平凡模型中对量子计算简洁论证系统。对QMA的简洁论证系统；量子随机预言模型中对QMA的简洁非交互论证系统；假设带错误学习,对QMA的简洁批量论证系统。
https://eprint.iacr.org/2022/336
首个基于双线性群上标准假设的对NP的非交互批量论证系统构造。不使用相关困难哈希函数和概率可检验证明证明的构造批量验证的直接方法。首个亚线性CRS的对P的SNARG，以及首个基于双线性标准假设的聚合签名。
https://eprint.iacr.org/2022/188
对随机线性码上的特征解码问题的零知识证明系统，依赖MPC-in-the-head范式。得到超过Picnic3并和SPHINCS+比较的签名算法。
https://eprint.iacr.org/2022/270
承诺并打开Sigma协议会得到在线可抽取性的非交互方案，在量子随机预言模型中证明了紧致在线可抽取性。对Picnic签名的可证明后量子安全性得到了巨大的提升。
https://eprint.iacr.org/2022/178
基于随机化指数时间假设，证明了随机预言模型中的SNARG的紧致下界，对非可适应性验证者和加盐可靠性的构造都成立。
https://eprint.iacr.org/2021/1516
后量子安全单向函数，后量子常数轮黑盒两方安全计算协议。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32139
可验证关系分享VRS是对秘密分享和零知识证明的泛化概念，每个高效可计算的关系可以通过具有两轮最佳轮复杂度的 VRS 来实现，其中第一轮与输入无关（离线轮），UC安全。产生了多验证者零知识证明 (MVZK) 的 2 轮离线/在线构造。
Kurt PanzkREPL：一个zkSNARKs 在线开发环境
作者：Kevin Kwok 译者：Kurt Pan 原文链接：https://0xparc.org/blog/zkrepl在计算的旧石器时代，计算机曾是机电的巨兽，每秒只可以执行几十次操作，但每年的成本却高达数百万美元。程序是通过细致的思考、在接线板中插入电线以及给卡片打孔来开发的。那个时候，bug就是是字面意义上的虫子，它们会啃咬电线，偶尔会导致短路，这可能会烧毁所有东西。 那时，对计算机进行编程是一项充满仪式感的艰苦的活动。但在 1950 年代后期，一种名为 LISP 的新编程系统被发明出来，它能够对其自己的实现进行推理——通过一个名为eval的结构，程序可以要求它们自己的制造者来产生新的程序。基于此，研究者提出了一个简单的程序，该程序将从键盘读取一些输入，将其发送到eval 结构，打印结果，然后循环回到起点以等待进一步的输入。 这个巧妙的技巧 ，REPL（译者注：读取﹣求值﹣输出循环）， 引发了编程的民主化进程——把编程从一个仅由民族国家用来操控火箭的东西，变成了一个青少年用来制作游戏的东西。零知识近年来，我们见证了一个计算的新时代的兴起。我们有像以太坊和比特币这样的区块链...
Kurt Pan公链隐私探索
原文：https://wdai.us/posts/navigating-privacy/ 作者：Wei Dai 翻译：Kurt Pan此文是对公链（又名去中心化账本、Crypto和 Web3）场景下隐私方面的阐述。第一部分会涉及为什么隐私是大规模采用的关键障碍以及隐私有哪些不同方面。第二部分综述了达成隐私的三种不同方法：通过零知识证明，通过仅以匿名为目标，以及通过一种新的称为 MOCCA 抽象。第一部分：什么是公链隐私以及为什么隐私——大规模采用的最后障碍现代金融系统运行良好，我们不必担心日常交易的安全性或隐私性。当你在杂货店购物、通过支票支付租金或在银行获取短期贷款时，你不必担心你的交易会受到非相关方的公开审查。在现代银行和信用卡网络中，大部分交易细节保留在相关金融中介和机构内部。理想情况下，用户不必担心他们的敏感信息会被泄露给大众，同时当局也几乎可以追踪那些非法活动。 不幸的是，目前在流行的区块链上进行的交易并非可以做到如此程度。尽管区块链技术允诺使当前的金融生态去中心化和民主化，但大多数系统甚至无法达到我们所期望的最基本的隐私级别。你买的披萨🍕会被永久记录，你所有的交易都...
Kurt Pan什么是ZEXE ？
原文：Anthony Matlala 翻译：Kurt Pan自加密货币出现，分布式账本系统变得流行起来。典型的分布式账本方案建立在区块链技术上，其特点是特定的数据结构，以区块的形式保存交易信息的记录。这些数据块通过称为哈希的密码学计算数“链接”或连在一起，并且该哈希值唯一地标识给定块。 尽管越来越受欢迎，分布式账本系统方案通常只提供有限的隐私。此外，确实提供隐私的方案通常在其支持的程序的表达能力方面受到限制。 正是这个问题促使隐私研究人员（包括几位 ZCash 创始科学家）提出了一个他们称为 ZEXE或零知识执行的方案。ZEXE 是第一个基于账本的方案，在该方案中应用程序可以在无信任、私密和可扩展的情况下执行。 虽然 Aleo 是由 ZEXE 的几位作者创立的，并且该研究是其计算模型的关键部分，但 Aleo 不仅仅是 ZEXE，其额外提供了用于编写私有应用程序的完整系列方法。 尽管如此，ZEXE 是 Aleo 中的核心组件。然而在研究圈之外，它仍然相对不为人知。本系列文章的目的是提供 ZEXE 设计策略背后的额外背景、它支持的功能以及可以使用它构建的真实世界应用的描述。预...
下个月召开的密码学顶会
Crypto22中的零知识证明相关论文简介。看完摘要我直呼牛逼，谁说零知识证明学术理论研究已经结束，现在只剩工程应用的果子了？
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32215
新零知识论证系统Orion，域运算和哈希函数的O(N)的证明时间，O(log^2 N)证明大小。提出了一种基于最密集子图算法的新算法来测试随机二分图是否是无损扩展图。开发了一种有效的证明组合方案，代码转换，以将证明大小从平方根减少到多项式对数。
https://eprint.iacr.org/2022/819
提出恶意安全的VOLE扩展协议，将短的种子VOLE转换为同样环上的伪随机VOLE。新基于VOLE的证明系统QuarkSilver。
https://eprint.iacr.org/2021/370
实现增量可验证计算 (IVC)的新方法，完全避免使用SNARKs，而是使用折叠方案。常数递归开销，每步证明者开销由两个多指数支配，证明本身线性但使用已知zkSNARK可以对有效证证明进行简洁的零知识知识证明，不需要可信设置，不需要FFT。
https://eprint.iacr.org/2022/767
构造对NP语言的高效非延展零知识的新方法，基于新原语：基于实例的非延展承诺。第一个无需公钥假设的非延展承诺方案。
https://eprint.iacr.org/2022/820
假设：1.带错误学习问题的亚指数困难性，2.存在对稍微超多项式时间敌手的无密钥抗多碰撞哈希函数，构造了对NP的公开抛币3轮零知识论证系统。
https://eprint.iacr.org/2021/1259
说明了任何k_1,...,k_mu特殊可靠多轮公开抛币交互式证明系统，t路并发重复最优地降低了知识错误。结果泛化到t中取s门限并发重复，以同时降低知识错误和完备性错误。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32176
假设存在亚指数安全线性可计算抗碰撞哈希函数，对具有重复子结构等一大类布尔电路，构造IOP以及相应的简洁论证系统，证明者开销polylog(k)。
https://eprint.iacr.org/2022/281
简洁IOP，通信复杂度是证据的多项式（甚至线性），介绍其应用和局限。对空间受限NP关系，使用单向函数，展示如何保持证明长度同时编译IOP为零知识证明，通信复杂度几乎和证据长度相等，得到最小假设下最短的零知识证明。对更一般NP关系，证明在一个新复杂度理论猜想下，不存在对CSAT的简洁IOP。
https://eprint.iacr.org/2021/1315
提出对QMA的经认证的永久零知识证明，这是一种计算零知识证明，但验证者发送其已经删除所有的量子信息的经典证书。如果证书有效，达到统计零知识。引入原语：统计绑定和经认证的永久隐藏承诺方案，基于带证书删除的量子加密方案构造。并将其和对QMA的量子Sigma协议组合，在量子随机预言模型下得到对QMA的经认证的永久零知识证明。
https://eprint.iacr.org/2022/284
基于模SIS和模LWE问题困难假设，构造对满足As=t mod q的短向量s的知识证明系统。展示了证明s系数具有小的l2范式的更直接高效的方法。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32191
基于SIS的扩展假设，提出首个格基SNARK，同时满足：1. 后量子安全 2. 公开课验证 3. 对数时间验证者 4. 支持高效递归组合。将配对方案转译成格基方案的技术组件。新格基向量承诺方案，支持对常数阶多边量多项式映射的打开。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32247
提出基于格的对R1CS的亚线性大小零知识证明系统，证明大小是证据的平方根，比Ligero小2-3倍。Schwartz-Zippel引理的交互式变体。
https://eprint.iacr.org/2022/857
假设不可区分混淆和带错误学习的后量子安全，构造了通信复杂度和验证者运行时间是量子计算多项式对数的经典可验证简洁交互式论证系统，是首个平凡模型中对量子计算简洁论证系统。对QMA的简洁论证系统；量子随机预言模型中对QMA的简洁非交互论证系统；假设带错误学习,对QMA的简洁批量论证系统。
https://eprint.iacr.org/2022/336
首个基于双线性群上标准假设的对NP的非交互批量论证系统构造。不使用相关困难哈希函数和概率可检验证明证明的构造批量验证的直接方法。首个亚线性CRS的对P的SNARG，以及首个基于双线性标准假设的聚合签名。
https://eprint.iacr.org/2022/188
对随机线性码上的特征解码问题的零知识证明系统，依赖MPC-in-the-head范式。得到超过Picnic3并和SPHINCS+比较的签名算法。
https://eprint.iacr.org/2022/270
承诺并打开Sigma协议会得到在线可抽取性的非交互方案，在量子随机预言模型中证明了紧致在线可抽取性。对Picnic签名的可证明后量子安全性得到了巨大的提升。
https://eprint.iacr.org/2022/178
基于随机化指数时间假设，证明了随机预言模型中的SNARG的紧致下界，对非可适应性验证者和加盐可靠性的构造都成立。
https://eprint.iacr.org/2021/1516
后量子安全单向函数，后量子常数轮黑盒两方安全计算协议。
https://www.iacr.org/cryptodb//data/paper.php?pubkey=32139
可验证关系分享VRS是对秘密分享和零知识证明的泛化概念，每个高效可计算的关系可以通过具有两轮最佳轮复杂度的 VRS 来实现，其中第一轮与输入无关（离线轮），UC安全。产生了多验证者零知识证明 (MVZK) 的 2 轮离线/在线构造。
Kurt PanzkREPL：一个zkSNARKs 在线开发环境
作者：Kevin Kwok 译者：Kurt Pan 原文链接：https://0xparc.org/blog/zkrepl在计算的旧石器时代，计算机曾是机电的巨兽，每秒只可以执行几十次操作，但每年的成本却高达数百万美元。程序是通过细致的思考、在接线板中插入电线以及给卡片打孔来开发的。那个时候，bug就是是字面意义上的虫子，它们会啃咬电线，偶尔会导致短路，这可能会烧毁所有东西。 那时，对计算机进行编程是一项充满仪式感的艰苦的活动。但在 1950 年代后期，一种名为 LISP 的新编程系统被发明出来，它能够对其自己的实现进行推理——通过一个名为eval的结构，程序可以要求它们自己的制造者来产生新的程序。基于此，研究者提出了一个简单的程序，该程序将从键盘读取一些输入，将其发送到eval 结构，打印结果，然后循环回到起点以等待进一步的输入。 这个巧妙的技巧 ，REPL（译者注：读取﹣求值﹣输出循环）， 引发了编程的民主化进程——把编程从一个仅由民族国家用来操控火箭的东西，变成了一个青少年用来制作游戏的东西。零知识近年来，我们见证了一个计算的新时代的兴起。我们有像以太坊和比特币这样的区块链...
Kurt Pan公链隐私探索
原文：https://wdai.us/posts/navigating-privacy/ 作者：Wei Dai 翻译：Kurt Pan此文是对公链（又名去中心化账本、Crypto和 Web3）场景下隐私方面的阐述。第一部分会涉及为什么隐私是大规模采用的关键障碍以及隐私有哪些不同方面。第二部分综述了达成隐私的三种不同方法：通过零知识证明，通过仅以匿名为目标，以及通过一种新的称为 MOCCA 抽象。第一部分：什么是公链隐私以及为什么隐私——大规模采用的最后障碍现代金融系统运行良好，我们不必担心日常交易的安全性或隐私性。当你在杂货店购物、通过支票支付租金或在银行获取短期贷款时，你不必担心你的交易会受到非相关方的公开审查。在现代银行和信用卡网络中，大部分交易细节保留在相关金融中介和机构内部。理想情况下，用户不必担心他们的敏感信息会被泄露给大众，同时当局也几乎可以追踪那些非法活动。 不幸的是，目前在流行的区块链上进行的交易并非可以做到如此程度。尽管区块链技术允诺使当前的金融生态去中心化和民主化，但大多数系统甚至无法达到我们所期望的最基本的隐私级别。你买的披萨🍕会被永久记录，你所有的交易都...
Kurt Pan什么是ZEXE ？
原文：Anthony Matlala 翻译：Kurt Pan自加密货币出现，分布式账本系统变得流行起来。典型的分布式账本方案建立在区块链技术上，其特点是特定的数据结构，以区块的形式保存交易信息的记录。这些数据块通过称为哈希的密码学计算数“链接”或连在一起，并且该哈希值唯一地标识给定块。 尽管越来越受欢迎，分布式账本系统方案通常只提供有限的隐私。此外，确实提供隐私的方案通常在其支持的程序的表达能力方面受到限制。 正是这个问题促使隐私研究人员（包括几位 ZCash 创始科学家）提出了一个他们称为 ZEXE或零知识执行的方案。ZEXE 是第一个基于账本的方案，在该方案中应用程序可以在无信任、私密和可扩展的情况下执行。 虽然 Aleo 是由 ZEXE 的几位作者创立的，并且该研究是其计算模型的关键部分，但 Aleo 不仅仅是 ZEXE，其额外提供了用于编写私有应用程序的完整系列方法。 尽管如此，ZEXE 是 Aleo 中的核心组件。然而在研究圈之外，它仍然相对不为人知。本系列文章的目的是提供 ZEXE 设计策略背后的额外背景、它支持的功能以及可以使用它构建的真实世界应用的描述。预...
Share Dialog
Share Dialog
Subscribe to Kurt Pan
Subscribe to Kurt Pan
<100 subscribers
<100 subscribers
No activity yet