Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

Cheng Shu; Cheng Wang; Haifeng Yu; Hongju Li; Jian Ding

arxiv: 2603.22011 · v2 · submitted 2026-03-23 · 💻 cs.CR · cs.IT· math.IT

Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

Jian Ding , Cheng Wang , Hongju Li , Cheng Shu , Haifeng Yu This is my paper

Pith reviewed 2026-05-15 00:47 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT

keywords hierarchical secret sharingChinese Remainder Theoremasymptotically idealdisjunctiveconjunctiveone-way functionsinformation rate

0 comments

The pith

Two CRT-based schemes for hierarchical secret sharing become asymptotically ideal in information rate.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a disjunctive hierarchical secret sharing scheme and a conjunctive hierarchical secret sharing scheme by combining the Chinese Remainder Theorem over the integer ring with one-way functions. These constructions partition participants into levels of authority and ensure that only authorized groups meeting the level condition can recover the secret while unauthorized groups learn nothing. Earlier CRT-based hierarchical schemes either had security gaps or kept the information rate below one half; the new schemes make the ratio of secret length to share length approach one as the total number of participants grows. The security argument reduces to the one-way property of the functions employed. Readers interested in graded-access systems would notice that near-optimal share sizes reduce storage overhead in large deployments without sacrificing the flexibility of CRT decompositions.

Core claim

The authors construct disjunctive and conjunctive hierarchical secret sharing schemes via the CRT for the integer ring and one-way functions; both schemes are asymptotically ideal, with information rate approaching 1, and are proven secure under standard assumptions on the one-way functions.

What carries the argument

Chinese Remainder Theorem decomposition over integer moduli chosen to encode the hierarchical access structure, combined with one-way functions that mask the shares so that the total share size stays close to the secret size.

If this is right

Authorized sets at or above the required level reconstruct the secret exactly.
Any set that fails the hierarchical condition obtains zero information about the secret.
Share sizes increase only by a multiplicative factor that can be made arbitrarily close to 1.
The schemes inherit the flexible share-size property of CRT methods while removing the previous rate limitation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

In large-scale distributed storage the storage cost per secret would approach the information-theoretic minimum even when participants have graded privileges.
An efficient, explicit algorithm for selecting the CRT moduli would turn the asymptotic result into a practical construction for concrete sizes.
The same masking technique with one-way functions might be reusable for realizing other monotone access structures beyond the hierarchical case.

Load-bearing premise

There exist sequences of CRT moduli that simultaneously realize the required hierarchical access structure and drive the information rate arbitrarily close to one.

What would settle it

A concrete counterexample would be any hierarchical access structure for which every choice of moduli forces the sum of share lengths to remain at least twice the secret length for arbitrarily large participant counts, or an efficient algorithm that recovers the secret from the shares held by any unauthorized set.

read the original abstract

In Shamir's secret sharing scheme, all participants possess equal privileges. However, in many practical scenarios, it is often necessary to assign different levels of authority to different participants. To address this requirement, Hierarchical Secret Sharing (HSS) schemes were developed, which partitioned all participants into multiple subsets and assigned a distinct privilege level to each. Existing Chinese Remainder Theorem (CRT)-based HSS schemes benefit from flexible share sizes, but either exhibit security flaws or have an information rate less than $\frac{1}{2}$. In this work, we propose a disjunctive HSS scheme and a conjunctive HSS scheme by using the CRT for integer ring and one-way functions. Both schemes are asymptotically ideal and are proven to be secure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives two new CRT-based HSS schemes for disjunctive and conjunctive hierarchies that claim asymptotic ideality via one-way functions, but the modulus selection needed to enforce the access structure while driving the rate to 1 is not shown constructively.

read the letter

The main takeaway is that Ding et al. present a disjunctive HSS construction and a conjunctive one that combine the CRT over integer rings with one-way functions to reach asymptotic ideality, meaning share size approaches secret size for large secrets. This specific pairing appears new relative to the prior CRT-HSS work they cite, which either had security problems or stayed below rate 1/2. The motivation is clear: hierarchies need graded access, and CRT already gives flexible share lengths that could help in practice. Using one-way functions to obscure the moduli is a direct attempt to improve the rate without breaking reconstruction. That part of the approach is reasonable and worth checking. The soft spot is the modulus selection. To make CRT enforce exactly the stated hierarchy and still let the information rate approach 1, the authors need tuples M1 < … < Mn that satisfy both conditions at once. The paper asserts such tuples exist but supplies no explicit polynomial-time algorithm that takes an arbitrary hierarchy and outputs a suitable M vector, nor a density argument showing that the required primes can be found without exponential search. If the only solutions force the moduli to scale linearly with the number of participants, the asymptotic claim does not hold. The security arguments are stated at a high level without visible reduction steps in the abstract, so the full text has to carry that load. This paper is aimed at people working on secret sharing for access control systems who want better rates in hierarchical settings. A reader who needs concrete rate improvements might extract useful ideas, but they would have to fill in or verify the modulus construction themselves. It deserves a serious referee because the claims are specific enough to test and the prior literature is engaged, even if the central construction detail needs strengthening.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a disjunctive hierarchical secret sharing (HSS) scheme and a conjunctive HSS scheme constructed via the Chinese Remainder Theorem over the integer ring combined with one-way functions. It asserts that both schemes are asymptotically ideal (information rate approaching 1) and supplies security proofs, improving on prior CRT-based HSS schemes that either had security flaws or information rates below 1/2.

Significance. If the constructions and proofs are valid, the work would provide a meaningful advance in HSS by delivering asymptotically ideal rates with the flexibility of CRT-based share sizes, while using one-way functions to enforce hierarchy. This could be useful for applications needing graded access privileges, provided the modulus selection is efficient and the security reductions are tight.

major comments (2)

[Abstract] Abstract: the central claims of asymptotic ideality and security are asserted without any derivation steps, explicit modulus conditions, or reduction details; this is load-bearing because the abstract supplies no concrete algorithm or existence argument for the required CRT moduli.
[Construction] Construction section: no explicit (poly-time) algorithm is given for producing a modulus tuple M_1 < … < M_n that simultaneously enforces the stated disjunctive or conjunctive hierarchy via CRT reconstruction and guarantees max |share_i| / |secret| → 1; without a density proof for suitable primes, the rate claim risks collapse if |M_i| must grow linearly with the number of participants.

minor comments (2)

[Preliminaries] Notation for the hierarchical access structures should be introduced with a small example table showing how the disjunctive versus conjunctive conditions translate into the CRT conditions.
[Security Analysis] Ensure that all references to one-way functions include the precise hardness assumption used in the security reduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to incorporate clarifications and an explicit algorithm.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims of asymptotic ideality and security are asserted without any derivation steps, explicit modulus conditions, or reduction details; this is load-bearing because the abstract supplies no concrete algorithm or existence argument for the required CRT moduli.

Authors: We agree the abstract is concise and will revise it to include a brief statement of the key modulus conditions (strictly increasing primes M_i of bit length approximately equal to the secret) and note that security follows from the one-wayness of the functions used to enforce hierarchy levels. Full derivation steps and reductions remain in the body, but the abstract will now reference the existence argument based on prime density in short intervals. revision: yes
Referee: [Construction] Construction section: no explicit (poly-time) algorithm is given for producing a modulus tuple M_1 < … < M_n that simultaneously enforces the stated disjunctive or conjunctive hierarchy via CRT reconstruction and guarantees max |share_i| / |secret| → 1; without a density proof for suitable primes, the rate claim risks collapse if |M_i| must grow linearly with the number of participants.

Authors: The one-way functions in our construction enforce the hierarchy, permitting moduli to be chosen without exponential growth. We will add an explicit probabilistic polynomial-time algorithm: given security parameter l (secret bit length) and n, iteratively select the next prime in [2^l, 2^{l+1}] satisfying the (loose) CRT conditions for the hierarchy. Prime gaps of size O(l^2) ensure efficiency. By the prime number theorem, sufficiently many such primes exist for polynomial n in l, and |M_i| = l + o(l), so the information rate approaches 1 as l → ∞. A short density argument and reference will be included. revision: yes

Circularity Check

0 steps flagged

No circularity: construction and proofs rely on external CRT and OWF properties

full rationale

The paper defines two HSS schemes via explicit CRT-based share generation over integer rings combined with one-way functions to enforce hierarchy. Security reductions are stated to rest on the one-wayness of the hiding function and on the standard uniqueness of CRT solutions for the chosen moduli. Asymptotic ideality is obtained by letting the secret size grow while keeping the relative size of the largest modulus bounded; this bound is asserted to be achievable by standard prime-density arguments rather than by any quantity defined in terms of the final rate. No equation equates a derived quantity to a fitted parameter or to a self-cited uniqueness theorem; the derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract only; full construction details unavailable. The schemes rest on standard cryptographic primitives whose concrete instantiation parameters are not supplied.

axioms (2)

domain assumption Secure one-way functions exist
Invoked to enforce binding and security of shares.
domain assumption Suitable CRT moduli can be chosen to realize the hierarchical access structure while preserving asymptotic ideality
Required for both the access condition and the information-rate claim.

pith-pipeline@v0.9.0 · 5427 in / 1185 out tokens · 53758 ms · 2026-05-15T00:47:10.678569+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 1 internal anchor

[1]

Shamir, How to share a secret, Communications of the ACM, vol.22, no.11, pp.612- 613, 1979

A. Shamir, How to share a secret, Communications of the ACM, vol.22, no.11, pp.612- 613, 1979

work page 1979
[2]

G. R. Blakley, Safeguarding cryptographic keys, in: 1979 International Workshop on Managing Requirements Knowledge, MARK, New York, NY, USA, pp. 313-318. IEEE, 1979

work page 1979
[3]

G. J. Simmons, How to (really) share a secret, in: Advances in Cryptology-Crypto’88, Santa Barbara, California, USA. Lecture Notes in Computer Science, vol.403, pp.390-

work page
[4]

Tassa, Hierarchical threshold secret sharing, Journal of Cryptology, vol.20, no.2, pp.237-264, 2007

T. Tassa, Hierarchical threshold secret sharing, Journal of Cryptology, vol.20, no.2, pp.237-264, 2007

work page 2007
[5]

Q. Chen, C. Tang, and Z. Lin, Eﬀicient explicit constructions of multipartite secret sharing schemes, IEEE Transactions on Information Theory, vol.68, no.1, pp.601-631, 2022

work page 2022
[6]

J. Yuan, J. Yang, C. Wang, X. Jia, F. Fu, G. Xu, A new eﬀicient hierarchical multi- secret sharing scheme based on linear homogeneous recurrence relations, Information Sciences, vol. 592, pp.36-49,2022. 25

work page 2022
[7]

Harn, and F

L. Harn, and F. MIAO, Multilevel threshold secret sharing based on the Chinese remainder theorem, Information Processing Letters, vol.114, no.9, 2014. 504-509

work page 2014
[8]

Multilevel Threshold Secret and Function Sharing based on the Chinese Remainder Theorem

O. Ersoy, K. Kaya, and K. Kaskaloglu, Multilevel Threshold Secret and Func- tion Sharing based on the Chinese Remainder Theorem, arXiv: 1605.07988, https://arxiv.org/abs/1605.07988

work page internal anchor Pith review Pith/arXiv arXiv
[9]

F. L. Tiplea, and C. C. Dr ˘ agan, Asymptotically ideal Chinese remainder theorem- based secret sharing schemes for multilevel and compartmented access structures, IET Information Security, vol. 15, no. 4, pp. 282-296, 2021

work page 2021
[10]

Yang, S.-T

J. Yang, S.-T. Xia, X. Wang, J. Yuan, and F.-W. Fu, A perfect ideal hierarchical secret sharing scheme based on the CRT for Polynomial Rings, in: 2024 IEEE In- ternational Symposium on Information Theory (ISIT), Athens, Greece, pp.321-326. IEEE, 2024

work page 2024
[11]

H. Li, J. Ding, F. Miao, C.Wang, C. Shu, Novel CRT-based Asymptotically Ideal Disjunctive Hierarchical Secret Sharing Scheme, 2026, arXiv:2603.16267

work page arXiv 2026
[12]

Cohen, A Course in Computational Algebraic Number Theory, 4thed., Grad

H. Cohen, A Course in Computational Algebraic Number Theory, 4thed., Grad. Texts Math, Springer-Verlag, 2000

work page 2000
[13]

C. C. Dr ˘ agan, and F. L. Tiplea, On the asymptotic idealness of the Asmuth-Bloom threshold secret sharing scheme, Information Sciences, Volumes 463¨C464, pp. 75-85, 2018

work page 2018
[14]

Y. Ning, F. Miao, W. Huang, K. Meng, Y. Xiong, and X. Wang, Constructing ideal secret sharing schemes based on Chinese Remainder Theorem, in: Advances in Cryptology - ASIACRYPT 2018, Brisbane, QLD, Australia. Lecture Notes in Computer Science, vol. 11274, pp. 310-331. Springer, 2018

work page 2018
[15]

Quisquater, B

M. Quisquater, B. Preneel, and J. Vandewalle, On the security of the threshold scheme based on the Chinese remainder theorem, in: Public Key Cryptography, PKC 2002. Lecture Notes in Computer Science, vol. 2274, pp.199-210. Springer, Berlin, Heidelberg, 2002

work page 2002
[16]

E. F. Brickell, Some ideal secret sharing schemes, in: Advances in Cryptology- Eurocrypt’89, Houthalen, Belgium. Lecture Notes in Computer Science, vol.434, pp.468-475. Springer, 1989

work page 1989
[17]

Asmuth and J

C. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE Transac- tions on Information Theory, vol. 30, no. 2, pp. 208-210, 1983. 26

work page 1983
[18]

Mo, Ideal hierarchical secret sharing and lattice path matroids, Designs, Codes and Cryptography, vol.91, no.4, pp

S. Mo, Ideal hierarchical secret sharing and lattice path matroids, Designs, Codes and Cryptography, vol.91, no.4, pp. 1335-1349, 2023. 27

work page 2023

[1] [1]

Shamir, How to share a secret, Communications of the ACM, vol.22, no.11, pp.612- 613, 1979

A. Shamir, How to share a secret, Communications of the ACM, vol.22, no.11, pp.612- 613, 1979

work page 1979

[2] [2]

G. R. Blakley, Safeguarding cryptographic keys, in: 1979 International Workshop on Managing Requirements Knowledge, MARK, New York, NY, USA, pp. 313-318. IEEE, 1979

work page 1979

[3] [3]

G. J. Simmons, How to (really) share a secret, in: Advances in Cryptology-Crypto’88, Santa Barbara, California, USA. Lecture Notes in Computer Science, vol.403, pp.390-

work page

[4] [4]

Tassa, Hierarchical threshold secret sharing, Journal of Cryptology, vol.20, no.2, pp.237-264, 2007

T. Tassa, Hierarchical threshold secret sharing, Journal of Cryptology, vol.20, no.2, pp.237-264, 2007

work page 2007

[5] [5]

Q. Chen, C. Tang, and Z. Lin, Eﬀicient explicit constructions of multipartite secret sharing schemes, IEEE Transactions on Information Theory, vol.68, no.1, pp.601-631, 2022

work page 2022

[6] [6]

J. Yuan, J. Yang, C. Wang, X. Jia, F. Fu, G. Xu, A new eﬀicient hierarchical multi- secret sharing scheme based on linear homogeneous recurrence relations, Information Sciences, vol. 592, pp.36-49,2022. 25

work page 2022

[7] [7]

Harn, and F

L. Harn, and F. MIAO, Multilevel threshold secret sharing based on the Chinese remainder theorem, Information Processing Letters, vol.114, no.9, 2014. 504-509

work page 2014

[8] [8]

Multilevel Threshold Secret and Function Sharing based on the Chinese Remainder Theorem

O. Ersoy, K. Kaya, and K. Kaskaloglu, Multilevel Threshold Secret and Func- tion Sharing based on the Chinese Remainder Theorem, arXiv: 1605.07988, https://arxiv.org/abs/1605.07988

work page internal anchor Pith review Pith/arXiv arXiv

[9] [9]

F. L. Tiplea, and C. C. Dr ˘ agan, Asymptotically ideal Chinese remainder theorem- based secret sharing schemes for multilevel and compartmented access structures, IET Information Security, vol. 15, no. 4, pp. 282-296, 2021

work page 2021

[10] [10]

Yang, S.-T

J. Yang, S.-T. Xia, X. Wang, J. Yuan, and F.-W. Fu, A perfect ideal hierarchical secret sharing scheme based on the CRT for Polynomial Rings, in: 2024 IEEE In- ternational Symposium on Information Theory (ISIT), Athens, Greece, pp.321-326. IEEE, 2024

work page 2024

[11] [11]

H. Li, J. Ding, F. Miao, C.Wang, C. Shu, Novel CRT-based Asymptotically Ideal Disjunctive Hierarchical Secret Sharing Scheme, 2026, arXiv:2603.16267

work page arXiv 2026

[12] [12]

Cohen, A Course in Computational Algebraic Number Theory, 4thed., Grad

H. Cohen, A Course in Computational Algebraic Number Theory, 4thed., Grad. Texts Math, Springer-Verlag, 2000

work page 2000

[13] [13]

C. C. Dr ˘ agan, and F. L. Tiplea, On the asymptotic idealness of the Asmuth-Bloom threshold secret sharing scheme, Information Sciences, Volumes 463¨C464, pp. 75-85, 2018

work page 2018

[14] [14]

Y. Ning, F. Miao, W. Huang, K. Meng, Y. Xiong, and X. Wang, Constructing ideal secret sharing schemes based on Chinese Remainder Theorem, in: Advances in Cryptology - ASIACRYPT 2018, Brisbane, QLD, Australia. Lecture Notes in Computer Science, vol. 11274, pp. 310-331. Springer, 2018

work page 2018

[15] [15]

Quisquater, B

M. Quisquater, B. Preneel, and J. Vandewalle, On the security of the threshold scheme based on the Chinese remainder theorem, in: Public Key Cryptography, PKC 2002. Lecture Notes in Computer Science, vol. 2274, pp.199-210. Springer, Berlin, Heidelberg, 2002

work page 2002

[16] [16]

E. F. Brickell, Some ideal secret sharing schemes, in: Advances in Cryptology- Eurocrypt’89, Houthalen, Belgium. Lecture Notes in Computer Science, vol.434, pp.468-475. Springer, 1989

work page 1989

[17] [17]

Asmuth and J

C. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE Transac- tions on Information Theory, vol. 30, no. 2, pp. 208-210, 1983. 26

work page 1983

[18] [18]

Mo, Ideal hierarchical secret sharing and lattice path matroids, Designs, Codes and Cryptography, vol.91, no.4, pp

S. Mo, Ideal hierarchical secret sharing and lattice path matroids, Designs, Codes and Cryptography, vol.91, no.4, pp. 1335-1349, 2023. 27

work page 2023