Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

1. Problem Statement

Secret Sharing (SS) schemes allow a secret to be distributed among participants such that only authorized subsets can reconstruct it. While standard $(t, n)$-threshold schemes treat all participants equally, real-world scenarios often require Hierarchical Secret Sharing (HSS), where participants are divided into levels with different authority thresholds.

Existing HSS schemes face significant trade-offs:

• Ideal Schemes (Information Rate $\rho=1$): Schemes based on Birkhoff interpolation or polymatroids are ideal but often require exponential computational time for the dealer or complex matrix verification.
• CRT-Based Schemes: Schemes using the Chinese Remainder Theorem (CRT) offer flexible share sizes and polynomial complexity. However, previous CRT-based HSS schemes suffer from one of two flaws:
  • Security Flaws: Some proposed schemes (e.g., by Harn et al., Tiplea et al.) were proven insecure.
  • Low Information Rate: Secure CRT-based schemes (e.g., by Ersoy et al.) have an information rate significantly less than $1/2$.
  • Lack of Flexibility: Some ideal schemes cannot accommodate flexible share sizes.

The Core Challenge: Construct HSS schemes (both Disjunctive and Conjunctive) that are secure, asymptotically ideal (information rate $\to 1$), support flexible share sizes, and maintain polynomial-time complexity for the dealer.

2. Methodology

The authors propose two new schemes: a Disjunctive Hierarchical Secret Sharing (DHSS) scheme and a Conjunctive Hierarchical Secret Sharing (CHSS) scheme.

Core Mathematical Tools

1. Chinese Remainder Theorem (CRT) over Integer Rings: Used to reconstruct secrets from modular shares.
2. $k$-Compact Sequences of Co-primes: A specific sequence of integers $L = \{m_0, m_1, \dots, m_n\}$ where $m_0$ is a large prime, and subsequent primes satisfy $km_0 < m_i < km_0 + m_0^\theta$ (where $k \ge 1, \theta \in (0,1)$). This structure ensures the Asmuth-Bloom constraint is met asymptotically, allowing for high information rates.
3. One-Way Functions: Used to mask intermediate values and ensure that unauthorized subsets cannot derive the secret even if they possess partial information.

Scheme Construction

Both schemes follow a similar framework but differ in their access structures:

A. Disjunctive HSS (DHSS)

• Access Structure: A subset is authorized if it meets the threshold $t_\ell$ for any level $\ell$ (i.e., $\exists \ell$ such that $|A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$).
• Share Generation:
  • The dealer generates a secret $s \in \mathbb{Z}_{m_0}$.
  • Random integers $c_i$ are assigned to lower-level participants.
  • For each level $\ell$, a value $y_\ell = s + \alpha_\ell m_0$ is computed.
  • Shares for higher levels are derived from $y_\ell \pmod{m_i}$.
  • Crucial Step: The dealer publishes $w_i^{(\ell)} = (y_\ell - h_\ell(s_i, \ell)) \pmod{m_i}$, where $h_\ell$ is a public one-way function. This binds the shares to the specific level's threshold without revealing $y_\ell$ directly.
• Reconstruction: Authorized participants compute $s_i^{(\ell)}$ using the one-way function and public values, then use CRT to recover $y_\ell$ and finally $s = y_\ell \pmod{m_0}$.

B. Conjunctive HSS (CHSS)

• Access Structure: A subset is authorized only if it meets the threshold $t_\ell$ for all levels $\ell$ (i.e., $\forall \ell, |A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$).
• Share Generation:
  • The secret $s$ is split into $m$ random shares $\delta_1, \dots, \delta_m$ such that $\sum \delta_i \equiv s \pmod{m_0}$.
  • Each $\delta_\ell$ is treated similarly to the secret in the DHSS scheme, generating values $y_\ell = \delta_\ell + \alpha_\ell m_0$.
  • Shares are distributed and masked using one-way functions similar to the DHSS scheme.
• Reconstruction: Participants reconstruct each $\delta_\ell$ independently using CRT and then sum them modulo $m_0$ to recover $s$.

3. Key Contributions

1. First Secure CRT-Based Ideal HSS: The paper constructs the first DHSS and CHSS schemes based on the integer ring CRT that are both secure and asymptotically ideal.
2. Flexible Share Sizes: Unlike previous ideal schemes (e.g., Tassa, Cheng) which require fixed share sizes, the proposed schemes allow participants to hold shares of varying sizes, a feature inherent to CRT-based approaches.
3. Asymptotic Perfectness: The schemes are proven to be asymptotically perfect. As the secret size ($m_0$) increases, the information leakage to unauthorized subsets approaches zero.
4. Asymptotic Information Rate: The information rate $\rho$ approaches 1 as $m_0 \to \infty$. This is achieved by utilizing $k$-compact sequences of co-primes, which satisfy the Asmuth-Bloom constraint while minimizing the gap between the secret space and share space.
5. Polynomial Complexity: The dealer's computational complexity remains polynomial, avoiding the exponential time requirements of previous ideal schemes based on polymatroids.

4. Results and Analysis

• Security Proof: The authors prove Theorem 2 (Asymptotic Perfectness) and Theorem 4 (Correctness). They demonstrate that for any unauthorized set $B$, the conditional entropy $H(S|V_B)$ approaches the entropy of the secret $H(S)$ as $m_0 \to \infty$.
  • The proof relies on analyzing the cardinality of the set of candidate secrets ($G$) consistent with an unauthorized set's shares. Using the properties of $k$-compact sequences, they show that the ratio of valid candidates converges to a constant, causing the information loss $\Delta$ to vanish.
• Information Rate:
  • For a secret space $S = \mathbb{Z}_{m_0}$ and maximum share space $S_{max} = \mathbb{Z}_{m_n}$, the rate is $\rho = \frac{\log_2 m_0}{\log_2 m_n}$.
  • Since $m_n < m_0 + m_0^\theta$ (for 1-compact sequences), as $m_0 \to \infty$, $\rho \to 1$.
• Comparison:
  • Compared to Harn et al. [7] and Tiplea et al. [9], the proposed scheme is secure (those were shown to be insecure).
  • Compared to Ersoy et al. [8], the proposed scheme has a higher information rate (approaching 1 vs. $< 1/2$).
  • Compared to Tassa [4] and Chen et al. [5], the proposed scheme supports flexible share sizes and has lower computational complexity.

5. Significance

This work resolves a long-standing gap in cryptographic literature regarding Hierarchical Secret Sharing. Prior to this, researchers had to choose between:

1. Security/Idealness (but high complexity or no flexibility).
2. Flexibility/Speed (but insecurity or low information rate).

By successfully integrating $k$-compact sequences with one-way functions in a CRT framework, the authors provide a practical, efficient, and theoretically sound solution. This enables the deployment of hierarchical access control in large-scale systems (e.g., distributed storage, blockchain governance, or corporate security) where participants have different privilege levels, share sizes must be optimized, and information leakage must be minimized.