International Association
for Cryptologic Research

An $(n, t)$-Verifiable Secret Sharing (VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for constructing computational VSS schemes in the honest-majority setting, based on Shamir secret sharing. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a random oracle and any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or Post-Quantum (PQ) secure. - When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel VSS schemes in the RO model, named $\Pi_P$ and $\Pi_F$. Compared to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ (resp. $O(t)$) exponentiations in the verification (resp. reconstruction) process, as opposed to $O(t)$ (resp. $O(t^2)$), albeit at the expense of a constant factor slower sharing and increased communication. - By instantiating $\Pi$ with a hash-based commitment, we obtain a novel PQ-secure VSS scheme, labeled $\Pi_{LA}$. \Pi_{LA}} outperforms the recent protocol by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be seen as an amplified version of the simple VSS scheme, proposed by Gennaro, Rabin, and Rabin at PODC'98. - Building upon $\Pi_F$, we construct a Publicly VSS (PVSS) scheme, labeled $\Pi_S$, that can be seen as a new variant of Schoenmakers' scheme from Crypto'99. To this end, we first define the Polynomial Discrete Logarithm (PDL) problem, as a generalization of DL and then build a variant of the Schnorr Proof of Knowledge (PoK) scheme based on the new hardness assumption. We think the PDL relation and the associated PoK scheme can be independently interesting for Shamir-based threshold protocols. We believe $\Pi$ is general enough to be employed in various contexts such as lattices, isogenies, and an extensive array of practical use cases.

<p>Fully Homomorphic Encryption (FHE) is a prevalent cryptographic primitive that allows for computation on encrypted data. In various cryptographic protocols, this enables outsourcing computation to a third party while retaining the privacy of the inputs to the computation. However, these schemes make an honest-but-curious assumption about the adversary. Previous work has tried to remove this assumption by combining FHE with Verifiable Computation (VC). Recent work has increased the flexibility of this approach by introducing integrity checks for homomorphic computations over rings. However, efficient FHE for circuits of large multiplicative depth also requires non-ring computations called maintenance operations, i.e. modswitching and keyswitching, which cannot be efficiently verified by existing constructions. We propose the first efficiently verifiable FHE scheme that allows for arbitrary depth homomorphic circuits by utilizing the double-CRT representation in which FHE schemes are typically computed, and using lattice-based SNARKs to prove components of this computation separately, including the maintenance operations. Therefore, our construction can theoretically handle bootstrapping operations. We also present the first implementation of a verifiable computation on encrypted data for a computation that contains multiple ciphertext-ciphertext multiplications. Concretely, we verify the homomorphic computation of an approximate neural network containing three layers and &gt;100 ciphertexts in less than 1 second while maintaining reasonable prover costs. </p>

Non-Interactive Verifiable Secret Sharing (NI-VSS) is a technique for distributing a secret among a group of individuals in a verifiable manner, such that shareholders can verify the validity of their received share and only a specific number of them can access the secret. VSS is a fundamental tool in cryptography and distributed computing. In this paper, we present an extremely efficient NI-VSS scheme using Zero-Knowledge (ZK) proofs on secret shared data. While prior VSS schemes have implicitly used ZK proofs on secret shared data, we specifically use their formal definition recently provided by Boneh et al. in CRYPTO 2019. The proposed NI-VSS scheme uses a quantum random oracle and a quantum computationally hiding commitment scheme in a black-box manner, which ensures its ease of use, especially in post-quantum threshold protocols. Implementation results further solidify its practicality and superiority over current constructions. With the new VSS scheme, for parameter sets $(n, t)=(128, 63)$ and $(2048, 1023)$, a dealer can share a secret in less than $0.02$ and $2.0$ seconds, respectively, and shareholders can verify their shares in less than $0.4$ and $5.0$ milliseconds. Compared to the well-established Pedersen VSS scheme, for the same parameter sets, at the cost of $2.5\times$ higher communication, the new scheme is respectively $22.5\times$ and $3.25\times$ faster in the sharing phase, and notably needs $271\times$ and $479\times$ less time in the verification. Leveraging the new NI-VSS scheme, we revisit several classic and PQ-secure threshold protocols and improve their efficiency. Our revisions led to more efficient versions of both the Pedersen DKG protocol and the GJKR threshold signature scheme. We show similar efficiency enhancements and improved resilience to malicious parties in isogeny-based DKG and threshold signature schemes. We think, due to its remarkable efficiency and ease of use, the new NI-VSS scheme can be a valuable tool for a wide range of threshold protocols.