Publications

---

Linearly Homomorphic Secret Sharing and Multi-Party Computation with Unanimously Verifiable Deletion

 By Yilei Chen, Liheng Ji, Han Luo
 In submission | Back | PDF | Eprint

Abstract

Certified deletion enables a party to prove that it has erased the sensitive information contained in a quantum state. Bartusek and Raizes (CRYPTO 2024) gave the first secret-sharing scheme with privately verifiable deletion. Subsequently, Katz and Sela (EUROCRYPT 2025) constructed secret-sharing schemes with publicly verifiable deletion under computational assumptions. Constructing such a publicly verifiable scheme without cryptographic assumptions remains open.

In this work, we introduce an intermediate notion called . While private verification relies on the dealer and public verification allows any third party to verify deletion, unanimous verification assigns the verification responsibility to the parties in the secret-sharing scheme themselves. We construct an information-theoretically secure . In particular, to obtain its linear-homomorphic property, we exploit a that enables linear transformations on encoded values while preserving certified deletion. More generally, this structure can be used to upgrade certain primitives with certified deletion to their linearly homomorphic counterparts.

As another major contribution, we demonstrate an application of this batch scheme by constructing (MPC) protocols for arbitrary arithmetic circuits. Our outsourced MPC has and , achieves in the and setting against a adversary, and supports . The adversary may adaptively corrupt up to \(n-1\) clients. For the servers, during the online execution, at most \(t\) corrupted servers may remain undeleted and at least \(t+1\) honest servers must remain undeleted, for any \(t<n/2\). After successful finalization, all servers may be corrupted without revealing additional information about the remaining clients’ inputs beyond the public output and the corrupted clients’ inputs.