本文提出 Sparrow，一种面向数据并行算术电路的高空间效率零知识简洁非交互式证明（zkSNARK）方案。在部署 SNARK 的实践中，证明者的空间开销是主要障碍之一，往往远超本地计算的资源需求。针对这一问题，Sparrow 实现了两个显著特性：首先，对于给定有限域，随着电路规模增大，证明者的开销仅以亚对数倍数增长；其次，与先前适用于任意算术电路的空间高效 SNARK 方案相比，Sparrow 的证明者空间复杂度渐近地小于电路本身的大小。其关键构建模块是一种新的空间高效 sumcheck 参数，同时改善了证明者时间，这本身可能具有独立研究价值。实验部分覆盖了三种用例：任意数据并行电路、乘法树、批量 SHA256 哈希。结果表明，Sparrow 在证明者总空间上比之前最先进的空间高效 SNARK Gemini（Bootle 等人，EUROCRYPT'22）快 3.2 至 28.7 倍，在证明者时间上快 3.1 至 11.3 倍。此外，作者利用 Sparrow 的空间效率构建了树训练和预测的零知识证明，能够扩展到大型数据集和多棵树的森林。与基于 GKR 协议的非空间高效最优时间 SNARK 相比，在树训练中证明者空间减少 16 至 240 倍，同时保持基本相同的证明者和验证者时间以及证明大小。值得关注的是，Sparrow 的证明者所需空间与本地执行底层计算相当：例如，对于 400MB 的数据集，证明者所需空间仅比本地计算多 1.4 倍。该研究为大数据集上的零知识证明提供了实用的解决方案，适合密码学研究者、区块链隐私计算开发者以及需要验证大规模计算完整性的安全工程师阅读。

该论文提出了一种空间高效的量子算法，用于解决素数域上的椭圆曲线离散对数问题（ECDLP），这是密码学中的基础难题。Shor算法在理论上能高效求解ECDLP，但实际量子实现需要大量量子资源，尤其是逻辑量子比特数。当前最先进的实现需要超过1000个逻辑量子比特（针对256位素数域曲线）。本文的主要贡献是设计了一种新的空间高效可逆模逆电路，解决了仿射坐标点加法中主要的空间瓶颈。该电路基于扩展欧几里得算法，通过引入长度寄存器和位置控制算术，精炼了Proos和Zalka的寄存器共享技术，以紧凑方式存储和更新中间变量。进一步优化了可逆更新过程并构建了相应的受控算术电路。最终，整个ECDLP量子算法实现仅需3n+6⌊log₂n⌋+O(1)个逻辑量子比特和919n³/log₂n+O(n²)个Toffoli门，其中n是素数位数。对于256位素数域曲线，仅需835个逻辑量子比特，低于Chevignard等人（EUROCRYPT 2026）的1098个和Babbush等人（ArXiv Preprint 2026）的1175个。论文还结合了中间测量和经典前馈操作，提供了空间高效的受控仿射点加法电路，完整实现了求解ECDLP的Shor算法。适合量子计算和密码学研究者阅读。