Novel CRT-based Asymptotically Ideal Disjunctive Hierarchical Secret Sharing Scheme

Hongju Li, Jian M. Ding, Fuyou Miao, Cheng Wang, Cheng Shu

TL;DR

This paper identifies critical security flaws in recent "ideal" hierarchical secret sharing schemes and proposes a novel solution using the Chinese Remainder Theorem (CRT) for polynomial rings. Their new scheme is the first of its kind to be both secure and "asymptotically ideal," achieving maximum efficiency (an information rate of 1) while supporting flexible share sizes for participants with different levels of trust.

What Problem Does This Paper Address?

In traditional secret sharing, a dealer distributes a secret among $n$ participants such that only a specific number (a threshold) can work together to reconstruct it. However, real-world organizations are hierarchical. Disjunctive Hierarchical Secret Sharing (DHSS) handles this by grouping participants into levels; for example, a secret might require either 2 executives OR 5 managers to unlock.

The "holy grail" in this field is a scheme that is ideal (the shares are the same size as the secret) and supports flexible share sizes (allowing different levels to hold different amounts of data). Researchers have turned to the Chinese Remainder Theorem (CRT) to achieve this flexibility.

However, the authors of this paper discovered a major problem: two recently proposed "ideal" CRT-based schemes (by Yang et al., 2024, and Tiplea et al., 2021) are actually insecure. They show that in these schemes, unauthorized groups can exploit public information to bypass the hierarchy and steal the secret. This left a gap: no existing CRT-based scheme was both secure and highly efficient.

Methods

The authors take a two-pronged approach:

  1. Cryptanalysis: They provide a formal three-step attack method against the Yang et al. scheme. They demonstrate how an unauthorized subset of participants can use "public polynomials" (intended to help authorized groups) to solve for the secret using standard CRT math.
  2. The New Scheme: To fix these flaws, they build a new DHSS scheme using:
  3. CRT for Polynomial Rings: Instead of using integers, they perform calculations over polynomials in a finite field. This provides a more robust mathematical structure for hiding information.
  4. One-Way Hash Functions: This is the "secret sauce." By incorporating hash functions into the public values, they ensure that authorized participants can "unlock" the necessary components for reconstruction, while unauthorized participants find the public data computationally impossible to use.
  5. Asymptotic Analysis: They use Shannon entropy and probability theory to prove that as the secret space grows, the information leaked to unauthorized parties becomes mathematically negligible.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, the work relies on mathematical proofs and complexity analysis rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The Vulnerability of Public Values: Previous schemes failed because their "bridge" values (used to allow higher-level participants to help lower-level thresholds) were too transparent. The authors realized these values must be protected by a computational "one-way" barrier.
  • Polynomials over Integers: Using polynomial rings ($\mathbb{F}_p[x]$) instead of integer rings allows for more precise control over the "degree" of the shares, which directly relates to the security and the information rate.
  • Asymptotic Perfection: The paper introduces the concept of being "asymptotically ideal." While it might not be perfectly ideal for tiny secrets, as the secret size increases (which is the case in almost all modern applications), the efficiency loss drops to zero.

Key Results

  • Security Break: The authors successfully demonstrated that the "ideal" scheme from ISIT 2024 is not actually a DHSS scheme because it fails the basic privacy requirements.
  • Information Rate of 1: The proposed scheme achieves an information rate ($\rho$) of 1 when all shares are equal in size. This means there is zero "wasted" space; the shares are as compact as the secret itself.
  • Computational Security: Unlike older, inefficient schemes that required "unconditional" security (which limits efficiency), this scheme uses one-way hashes to provide "computational" security, making it practical for modern digital systems.
  • Flexibility: The scheme remains one of the few that allows a dealer to assign different share sizes to different participants without breaking the underlying security model.

Limitations and Future Work

The primary limitation acknowledged by the authors is the number of public values. To maintain the hierarchy and security, the dealer must publish several auxiliary polynomials. While this doesn't affect the size of the private shares held by participants, it does add overhead to the system's public bulletin board.

The authors conclude by stating that their future work will focus on reducing the number of these public values to make the scheme even more lightweight for resource-constrained environments.

Summary updated

Abstract

Disjunctive Hierarchical Secret Sharing (DHSS)} scheme is a type of secret sharing scheme in which the set of all participants is partitioned into disjoint subsets, and each subset is said to be a level with different degrees of trust and different thresholds. In this work, we focus on the Chinese Remainder Theorem (CRT)-based DHSS schemes due to their ability to accommodate flexible share sizes. We point out that the ideal DHSS scheme of Yang et al. (ISIT, 2024) and the asymptotically ideal DHSS scheme of Tiplea et al. (IET Information Security, 2021) are insecure. Consequently, existing CRT-based DHSS schemes either exhibit security flaws or have an information rate less than $\frac{1}{2}$. To address these limitations, we propose a CRT-based asymptotically perfect DHSS scheme that supports flexible share sizes. Notably, our scheme is asymptotically ideal when all shares are equal in size. Its information rate achieves one and it has computational security.
BibTeX
@misc{li2026novel,
  author = {Hongju Li and Jian M. Ding and Fuyou Miao and Cheng Wang and Cheng Shu},
  title = {{Novel CRT-based Asymptotically Ideal Disjunctive Hierarchical Secret Sharing Scheme}},
  year = {2026},
  eprint = {2603.16267},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.16267},
}

Loading related content...

Figure