hbACSS: Robust Asynchronous Complete Secret Sharing for Practical MPC

1. Introduction
2. Technical Framework
- 2.1 hbPolyCommit Protocol
- 2.2 hbACSS Architecture
3. Experimental Results
4. Code Implementation
5. Future Applications
6. References
7. Critical Analysis

1. Introduction

Multiparty Computation (MPC) enables confidential distributed computations but faces robustness challenges in asynchronous networks. This paper introduces hbACSS, a suite of asynchronous complete secret sharing protocols that achieve optimal resilience with quasi-linear computation and communication overhead.

2. Technical Framework

2.1 hbPolyCommit Protocol

The hbPolyCommit polynomial commitment scheme forms the foundation of hbACSS, providing efficient verification without trusted setup. The commitment for polynomial $P(x)$ of degree $t$ is computed as $C = g^{P(\tau)}$ where $\tau$ is a random challenge.

2.2 hbACSS Architecture

hbACSS operates in three phases: sharing, verification, and reconstruction. It guarantees output delivery even with $t$ malicious parties among $N = 3t+1$ total parties. The protocol achieves $O(N\log N)$ communication complexity compared to $O(N^2)$ in prior work.

3. Experimental Results

Experimental evaluation shows hbACSS scales efficiently with increasing party count. With 64 parties, hbACSS achieves 3.2x faster sharing and 4.1x faster reconstruction compared to VSS-R. Throughput scales linearly up to 128 parties with sub-second latency for typical parameter sizes.

4. Code Implementation

The hbACSS implementation includes core functions for secret sharing and reconstruction. Below is a simplified pseudocode structure:

class hbACSS:
    def share_secret(secret, parties, t):
        # Generate polynomial of degree t
        poly = generate_polynomial(secret, t)
        # Compute commitments using hbPolyCommit
        commitments = hbPolyCommit.commit(poly)
        # Distribute shares to N-t parties
        return distribute_shares(poly, commitments)
    
    def reconstruct(shares, commitments):
        # Verify shares against commitments
        if verify_shares(shares, commitments):
            # Reconstruct using Lagrange interpolation
            return lagrange_interpolation(shares)
        else:
            raise VerificationError

5. Future Applications

hbACSS enables robust MPC preprocessing for applications including privacy-preserving machine learning, decentralized finance, and secure voting systems. Future work includes integration with blockchain systems and optimization for mobile environments.

6. References

Yurek, T., Luo, L., Fairoze, J., Kate, A., & Miller, A. (2022). hbACSS: How to Robustly Share Many Secrets.
Ben-Or, M., Goldwasser, S., & Wigderson, A. (1988). Completeness theorems for non-cryptographic fault-tolerant distributed computation.
Cramer, R., Damgård, I., & Maurer, U. (2000). General secure multi-party computation from any linear secret-sharing scheme.

7. Critical Analysis

一针见血：hbACSS不是渐进式改良，而是异步MPC预处理领域的范式转移——它首次在理论和工程层面同时解决了可扩展性与鲁棒性的矛盾。

逻辑链条：传统ACSS的$O(N^2)$复杂度源于每个节点需验证所有其他节点的承诺→hbPolyCommit通过线性复杂度的多项式承诺将验证开销降至$O(N\log N)$→结合异步网络下的$N=3t+1$最优容错→实现从理论构造到工程可用的关键突破。这个技术路径与零知识证明领域从Pinocchio到Groth16的演进异曲同工，都是通过基础密码学原语的优化带来数量级提升。

亮点与槽点：最大亮点是首次在异步设置下实现准线性复杂度的完整秘密共享，比肩同步网络的效率——这如同在分布式系统中实现了"量子跃迁"。但槽点同样明显：论文对具体实现中的网络假设过于理想化，实际部署时可能面临部分同步网络的适配挑战；且与现有MPC框架（如MP-SPDZ）的集成度尚未验证，存在"最后一公里"问题。

行动启示：对MPC开发者而言，应立即评估将hbACSS集成至现有系统的可行性，特别是在金融和医疗等对鲁棒性要求极高的场景。对学术研究者，应关注其多项式承诺技术向其他密码学协议的泛化可能——正如CycleGAN的无监督图像转换启发了多个计算机视觉领域，hbPolyCommit有望成为异步密码学的新基础模块。

Table of Contents