An Efficient Rational Secret Sharing Scheme Based on the Chinese Remainder Theorem

Yun Zhang, Christophe Tartary, Huaxiong WangAcisp 2011 · DOI

TL;DR

This paper introduces a new, efficient protocol for "rational" secret sharing, where participants are self-interested and might deviate from the protocol if it benefits them. Their scheme, based on the Chinese Remainder Theorem, achieves a strong security guarantee (computational strict Nash equilibrium stable to trembles) with significantly smaller share sizes compared to prior work, making it more practical for real-world applications.

What Problem Does This Paper Address?

Traditional cryptographic models assume participants are either honest or malicious. However, in many real-world scenarios, participants are "rational" – they act in their own self-interest and will deviate from a protocol if doing so provides them with an advantage. This is particularly relevant in distributed systems where participants might have incentives to cheat or gain unauthorized information.

Secret Sharing Schemes (SSS) are designed to distribute a secret among multiple parties such that only authorized subsets can reconstruct it. The challenge is to design SSS that remain secure even when participants are rational and might try to exploit the protocol for personal gain. Previous work introduced notions like Nash Equilibrium (NE) and Strict NE to model this, but achieving these with practical efficiency, especially regarding share size, remained an open problem. Specifically, a prior efficient scheme [FKN10] had prohibitively large share sizes, limiting its applicability.

This paper aims to bridge this gap by proposing a rational secret sharing scheme that is both computationally secure and efficient, particularly in terms of share size, while maintaining strong equilibrium properties.

Methods

The core of this paper is a novel t-out-of-n rational secret sharing scheme built upon the Chinese Remainder Theorem (CRT). The protocol operates in two phases:

  1. Initial Share Phase: The dealer, assumed to be honest, distributes shares to all n participants. This phase uses a modified version of the Asmuth-Bloom SSS, incorporating necessary modifications for rational security. Key elements include setting up prime moduli, generating group elements, and using RSA for commitments. The dealer broadcasts an encrypted version of the secret (E(y)) which serves as a commitment.
  2. Secret Reconstruction Phase: This phase involves m (where m >= t) active participants and proceeds in a series of iterations.
  3. Share Update Phase: Each active participant P_i generates a random secret component d(i) and computes a "one-time" share for (s + d) mod m_0. This phase uses a range-proof technique (Cao-Liu's non-interactive range proof) to ensure participants cannot distribute inconsistent shares without being detected. Participants broadcast their shares and commitments.
  4. Combiner Phase: Participants use a reconstruction algorithm (similar to Asmuth-Bloom) to recover (s + d) mod m_0 from a subset of t shares.
  5. Iteration Control: The protocol uses a clever mechanism to identify "valid" and "invalid" iterations. An iteration is valid if d mod m_0 = 0, meaning the recovered secret is the original secret s. Otherwise, it's invalid. This invalidity is crucial for detecting cheaters. Participants check a specific value (h^y mod Q) against a published list to determine validity.

The scheme relies on the computational hardness of the discrete logarithm problem and RSA factorization. It achieves a (t-1)-resilient computational strict Nash equilibrium that is stable with respect to trembles. This means that no coalition of up to t-1 players can gain by deviating, and even if players make small, random "trembles" in their strategies, the equilibrium holds.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • CRT for Rationality: The paper ingeniously applies the Chinese Remainder Theorem to construct a rational secret sharing scheme. This allows for efficient computation and, crucially, a significantly reduced share size.
  • Iterative Invalidity for Detection: The use of multiple iterations, where most are intentionally "invalid" (i.e., d != 0 mod m_0), is a key mechanism for detecting cheaters. Only the single valid iteration reveals the secret. This iterative structure, combined with range proofs, makes it very difficult for a participant to cheat without being caught.
  • Small Share Size Advantage: The most significant practical contribution is the drastically reduced share size (O(k)) compared to previous schemes (O(n*|s|)), making it feasible for large numbers of participants or high security parameters.
  • Synchronous but Non-Simultaneous Channels: The protocol requires synchronous communication but does not need simultaneous message delivery, which is a more relaxed requirement than some other cryptographic protocols.

Key Results

The paper proves that their proposed protocol achieves:

  • A (t-1)-resilient computational strict Nash equilibrium. This means no coalition of up to t-1 players can improve their outcome by deviating, and each player's strategy is their unique best response.
  • The equilibrium is stable with respect to trembles. This means the equilibrium remains robust even if players deviate slightly from their prescribed strategies.
  • The share size is O(k), where k is the security parameter. This is a substantial improvement over the (n-t+1)*(2n|s| + O(k)) share size of prior work [FKN10].
  • The protocol is efficient, with expected round and computation complexity being polynomial in k.

Limitations and Future Work

  • Assumption on Auxiliary Information: The protocol, like many in this area, assumes that no player knows any auxiliary information about the secret s. This is stated as being inherent to non-simultaneous channels.
  • Dealer Honesty in Initial Phase: The initial share distribution phase assumes an honest dealer.
  • Future Work: The paper mentions that their protocol is more practical for use as a subroutine in rational Multi-Party Computation (MPC) protocols due to its efficiency and smaller share size, suggesting future research in this direction. The authors also note that their protocol relies on the assumption that players have enough motivation to execute the reconstruction phase rather than just guessing the secret locally, which is a standard assumption in rational cryptography.

Summary updated

BibTeX
@inproceedings{zhang2011efficient,
  author = {Yun Zhang and Christophe Tartary and Huaxiong Wang},
  title = {{An Efficient Rational Secret Sharing Scheme Based on the Chinese Remainder Theorem}},
  booktitle = {Acisp},
  year = {2011},
  doi = {10.1007/978-3-642-22497-3\_17},
}
Figure