This paper presents a variant of Feldman's verifiable secret-sharing (VSS) protocol for the case of a dishonest majority, formally proving its security. The protocol is designed to ensure that all honest parties receive valid and consistent shares, even if some participants are malicious. Key contributions include: 1. **Basic Feldman VSS**: A protocol for sharing a secret among \( n \) parties, where at least \( t \) parties are required to reconstruct the secret. The protocol does not assume an honest majority, allowing parties to abort if necessary. 2. **Online and Offline Parties**: A protocol for distributed key generation where \( t \) parties participate actively, while \( n-t \) parties receive shares passively. The protocol ensures that all honest parties generate output if any online party does not abort. 3. **Adding a Party**: A protocol to add a new party to the sharing without changing the threshold \( t \). This is achieved by subsharing the new share among the existing \( t \) parties and then sending a random sharing of the new share to the new party. 4. **Refresh**: A protocol to refresh an existing secret sharing, ensuring that all parties hold shares on an independent polynomial that defines the same secret. This is useful for proactive security, preventing slow theft of shares. 5. **Removing a Party**: A protocol to revoke a party's share and remove them from the sharing. This is achieved by running the refresh operation without providing the new share to the removed party. The paper also discusses the security of Feldman's VSS in the ideal/real model paradigm of secure multiparty computation, proving that the protocols are UC secure for appropriately defined ideal functionalities. The protocols are designed to work with more general access structures than just a basic threshold, supporting any tree with AND, OR, and threshold nodes. The main differences between the proposed protocol and the standard Feldman VSS for an honest majority include: - The protocol does not require a full-blown secure broadcast of the polynomial coefficients, as only a simple echo-broadcast is needed. - The dealer must prove knowledge of the polynomial with a zero-knowledge proof of knowledge, which is not necessary in the honest majority setting. - The protocol does not have a "complaint" phase, as parties can simply abort if they receive incorrect values. The paper also addresses the use of Feldman VSS for key generation, noting that the public key share is revealed, which is often necessary in applications like elliptic-curve threshold cryptography. The protocols are designed to be efficient, with minimal rounds of interaction, making them suitable for asynchronous environments.This paper presents a variant of Feldman's verifiable secret-sharing (VSS) protocol for the case of a dishonest majority, formally proving its security. The protocol is designed to ensure that all honest parties receive valid and consistent shares, even if some participants are malicious. Key contributions include: 1. **Basic Feldman VSS**: A protocol for sharing a secret among \( n \) parties, where at least \( t \) parties are required to reconstruct the secret. The protocol does not assume an honest majority, allowing parties to abort if necessary. 2. **Online and Offline Parties**: A protocol for distributed key generation where \( t \) parties participate actively, while \( n-t \) parties receive shares passively. The protocol ensures that all honest parties generate output if any online party does not abort. 3. **Adding a Party**: A protocol to add a new party to the sharing without changing the threshold \( t \). This is achieved by subsharing the new share among the existing \( t \) parties and then sending a random sharing of the new share to the new party. 4. **Refresh**: A protocol to refresh an existing secret sharing, ensuring that all parties hold shares on an independent polynomial that defines the same secret. This is useful for proactive security, preventing slow theft of shares. 5. **Removing a Party**: A protocol to revoke a party's share and remove them from the sharing. This is achieved by running the refresh operation without providing the new share to the removed party. The paper also discusses the security of Feldman's VSS in the ideal/real model paradigm of secure multiparty computation, proving that the protocols are UC secure for appropriately defined ideal functionalities. The protocols are designed to work with more general access structures than just a basic threshold, supporting any tree with AND, OR, and threshold nodes. The main differences between the proposed protocol and the standard Feldman VSS for an honest majority include: - The protocol does not require a full-blown secure broadcast of the polynomial coefficients, as only a simple echo-broadcast is needed. - The dealer must prove knowledge of the polynomial with a zero-knowledge proof of knowledge, which is not necessary in the honest majority setting. - The protocol does not have a "complaint" phase, as parties can simply abort if they receive incorrect values. The paper also addresses the use of Feldman VSS for key generation, noting that the public key share is revealed, which is often necessary in applications like elliptic-curve threshold cryptography. The protocols are designed to be efficient, with minimal rounds of interaction, making them suitable for asynchronous environments.