🔢 mathematics

Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

Die Autoren stellen zwei hierarchische Geheimnisverteilungs-Schemata vor, die auf dem chinesischen Restsatz für den Integer-Ring und Einwegfunktionen basieren, um sowohl disjunkte als auch konjunkte Zugriffskontrollen mit asymptotisch idealer Informationsrate und nachgewiesener Sicherheit zu ermöglichen.

Ursprüngliche Autoren: Jian Ding, Cheng Wang, Hongju Li, Cheng Shu, Haifeng Yu

Veröffentlicht 2026-03-24

📖 4 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Jian Ding, Cheng Wang, Hongju Li, Cheng Shu, Haifeng Yu

Originalarbeit unter CC0 1.0 der Gemeinfreiheit gewidmet (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

🏰 Der geheime Schatz und die unterschiedlichen Schlüssel

Stellen Sie sich vor, eine Gruppe von Menschen möchte einen riesigen, wertvollen Schatz (das Geheimnis) sicher verwahren. In der klassischen Welt des „Shamir's Secret Sharing" haben alle Teilnehmer genau die gleichen Rechte: Man braucht eine bestimmte Anzahl von Leuten (z. B. 5 von 10), um den Schatz zu öffnen. Egal, ob es der Chef oder ein Praktikant ist – alle Schlüssel wiegen gleich viel.

Aber im echten Leben ist das oft nicht fair oder praktisch. Ein CEO sollte mehr Macht haben als ein Junior-Mitarbeiter. Ein Sicherheitschef sollte schneller Zugriff haben als ein Buchhalter. Hier kommt das Hierarchische Geheimnis-Sharing (HSS) ins Spiel. Man teilt die Gruppe in Ebenen ein (z. B. „Manager", „Manager-Assistenten", „Mitarbeiter"), und jede Ebene hat eine andere Schwelle, um den Schatz zu öffnen.

🧩 Das Problem: Die alten Methoden hatten Mängel

Bisher gab es zwei Hauptprobleme bei den Methoden, die auf dem Chinesischen Restsatz (CRT) basierten (eine mathematische Regel, die es erlaubt, große Zahlen aus kleinen Teilen wiederherzustellen):

Unsicherheit: Manche alten Methoden waren wie ein Schloss mit einem schwachen Riegel – Hacker konnten sie knacken.
Ineffizienz: Andere Methoden waren sicher, aber sehr „dick". Die Schlüssel (die Daten, die jeder Teilnehmer speichern muss) waren viel größer als das Geheimnis selbst. Das ist, als würde man einen kleinen Diamanten in einen riesigen, schweren Safe verpacken. Das nennt man eine schlechte „Informationsrate".

💡 Die neue Lösung: Ein schlauer Trick mit „Einweg-Toren"

Die Autoren dieses Papiers (Jian Ding und sein Team) haben nun zwei neue Methoden entwickelt: eine für disjunkte Hierarchien (man kann den Schatz öffnen, wenn entweder die Manager oder eine große Gruppe von Mitarbeitern da ist) und eine für konjunktive Hierarchien (man braucht sowohl Manager als auch Mitarbeiter).

Hier ist, wie ihre neue Methode funktioniert, einfach erklärt:

1. Die Bausteine: Der „k-compact" Zahlenhaufen

Stellen Sie sich vor, jeder Teilnehmer bekommt einen einzigartigen, riesigen Schlüssel (eine große Primzahl). Die Autoren haben eine spezielle Art, diese Schlüssel zu wählen, damit sie alle „nahe beieinander" liegen, aber trotzdem nicht voneinander teilbar sind.

Die Analogie: Stellen Sie sich vor, jeder Schlüssel ist ein Schloss mit einem sehr spezifischen Riegel. Die neuen Schlüssel sind so gewählt, dass sie alle ungefähr die gleiche Größe haben (wie eine Reihe von Ziegelsteinen, die fast gleich groß sind), aber perfekt ineinander passen, wenn man sie kombiniert.

2. Der Trick mit den „Einweg-Toren" (One-Way Functions)

Das ist der geniale Teil, der die Sicherheit garantiert.

Die Analogie: Stellen Sie sich vor, der Dealer (der Schatzmeister) gibt jedem Teilnehmer nicht nur einen Teil des Schlüssels, sondern auch eine Einweg-Tür.
- Wenn Sie die Tür von außen betreten (den öffentlichen Wert sehen), können Sie nicht herausfinden, was dahinter liegt.
- Aber wenn Sie Ihren eigenen Schlüssel haben, können Sie durch die Tür gehen und den Weg zum Schatz freilegen.
- Frühere Methoden ließen diese Türen offen oder hatten keine. Die neuen Methoden nutzen diese „Einweg-Türen", um sicherzustellen, dass Unbefugte, die nicht genug Schlüssel haben, absolut nichts über den Schatz herausfinden können.

3. Warum ist es „asymptotisch ideal"?

Das klingt kompliziert, ist aber einfach:

Ideal bedeutet: Die Größe des Schlüssels, den jeder speichern muss, ist fast genau so groß wie das Geheimnis selbst. Kein unnötiger Ballast.
Asymptotisch bedeutet: Je größer das Geheimnis wird (z. B. ein riesiges Dokument statt nur einer Zahl), desto näher kommt die Effizienz an 100% heran.
Die Metapher: Frühere Methoden waren wie ein schwerer Rucksack, in dem nur ein kleiner Stein lag. Die neue Methode ist wie ein Rucksack, der fast genau so groß ist wie der Stein selbst. Je größer der Stein wird, desto perfekter passt der Rucksack.

🚀 Was bringt das in der Praxis?

Die Autoren haben bewiesen, dass ihre beiden neuen Systeme:

Sicher sind: Hacker können sie nicht knacken, selbst wenn sie viele Teile des Puzzles haben, aber nicht genug für den Schatz.
Flexibel sind: Man kann den Teilnehmern Schlüssel unterschiedlicher Größe geben (z. B. bekommt der Chef einen etwas größeren Schlüssel, der mehr Informationen trägt, aber trotzdem effizient bleibt).
Schnell sind: Die Berechnungen sind für Computer leicht zu bewältigen (polynomielle Zeit), im Gegensatz zu alten Methoden, die Stunden oder Tage dauern könnten.

Zusammenfassung in einem Satz

Die Autoren haben einen neuen, sicheren und extrem effizienten Weg gefunden, geheime Informationen so aufzuteilen, dass verschiedene Gruppen von Menschen (von Chefs bis zu Praktikanten) unterschiedliche Zugriffsrechte haben, ohne dass die Datenmenge unnötig aufgebläht wird – alles dank eines cleveren Zusammenspiels aus alten mathematischen Regeln und modernen „Einweg-Türen".

1. Problemstellung

Das klassische Shamir'sche Secret-Sharing-Verfahren weist allen Teilnehmern gleiche Privilegien zu. In vielen realen Szenarien ist es jedoch notwendig, Teilnehmern unterschiedliche Autoritätsstufen zuzuweisen. Hierfür wurden hierarchische Secret-Sharing-Verfahren (HSS) entwickelt, die die Teilnehmer in disjunkte Teilmengen mit unterschiedlichen Schwellenwerten unterteilen. Es gibt zwei Haupttypen von Zugriffsstrukturen:

Disjunktive Hierarchische Secret Sharing (DHSS): Eine autorisierte Menge muss die Schwellenbedingung in mindestens einer Hierarchieebene erfüllen.
Konjunktive Hierarchische Secret Sharing (CHSS): Eine autorisierte Menge muss die Schwellenbedingung in allen Hierarchieebenen erfüllen.

Bisherige Ansätze basierend auf dem Chinesischen Restsatz (CRT) für den Integer-Ring hatten signifikante Nachteile: Entweder waren sie unsicher (wie die von Harn et al. oder Tiplea et al.), oder sie erreichten keine ideale Informationsrate (Information Rate $\rho < 1/2$ oder $\rho < 1$ ), oder sie erforderten exponentielle Rechenzeit für den Dealer. Das Ziel war die Entwicklung von HSS-Schemata, die sicher, asymptotisch ideal (Informationsrate nähert sich 1 an) und flexibel in Bezug auf die Share-Größen sind.

2. Methodik

Die Autoren schlagen zwei neue Schemata vor, die auf einer Kombination aus dem Chinesischen Restsatz (CRT) für den Integer-Ring und Einwegfunktionen (One-Way Functions) basieren.

Kernkomponenten:

k-kompakte Folgen von teilerfremden Zahlen (k-compact sequences of co-primes): Das Schema nutzt eine spezielle Folge von Primzahlen $m_0, m_1, \dots, m_n$ , die bestimmte Dichteeigenschaften erfüllen ( $km_0 < m_i < km_0 + m_0^\theta$ ). Dies ermöglicht es, die Asmuth-Bloom-Bedingung für große $m_0$ zu erfüllen und eine hohe Informationsrate zu garantieren.
Einwegfunktionen: Um die Sicherheit zu gewährleisten und die Lücken in früheren CRT-basierten Schemata zu schließen, werden öffentlich bekannte, verschiedene Einwegfunktionen $h_\ell(\cdot)$ verwendet. Diese verbergen Teile der Geheimnisse vor nicht autorisierten Mengen.
Share-Generierung:
- Der Dealer wählt eine geheime Zahl $s$ und generiert zufällige Werte, um eine verschlüsselte Zahl $y_\ell$ zu konstruieren, die modulo $m_0$ das Geheimnis ergibt.
- Shares werden als $s_i = y_\ell \pmod{m_i}$ (oder zufällige Werte für bestimmte Teilnehmer) berechnet.
- Öffentliche Werte $w_i^{(\ell)}$ werden veröffentlicht, die die Differenz zwischen $y_\ell$ und dem Ergebnis der Einwegfunktion auf dem Share darstellen.
Rekonstruktion:
- Autorisierte Mengen nutzen ihre Shares und die öffentlichen Werte, um unter Verwendung der Einwegfunktionen die Werte $s_i^{(\ell)}$ zu rekonstruieren.
- Mithilfe des CRT wird $y_\ell$ wiederhergestellt, woraus sich das Geheimnis $s = y_\ell \pmod{m_0}$ ableiten lässt.
- Beim konjunktiven Schema (CHSS) wird das Geheimnis als Summe von Teilgeheimnissen $\delta_\ell$ rekonstruiert, die jeweils über CRT ermittelt werden.

3. Wichtige Beiträge

Die Hauptbeiträge der Arbeit sind:

Entwicklung eines asymptotisch idealen DHSS-Schemas: Im Gegensatz zu früheren idealen Schemata (die keine flexiblen Share-Größen zuließen) oder CRT-basierten Schemata (die unsicher waren oder eine niedrige Informationsrate hatten), bietet dieses Schema flexible Share-Größen, ist sicher und erreicht eine Informationsrate, die sich asymptotisch 1 nähert.
Entwicklung eines asymptotisch idealen CHSS-Schemas: Ähnlich wie beim DHSS wird hier ein sicheres Schema mit flexiblen Share-Größen und einer Informationsrate $\to 1$ vorgestellt, das die Einschränkungen früherer Arbeiten (wie die von Yuan et al. oder Tiplea et al.) überwindet.
Sicherheitsbeweise: Die Autoren beweisen mathematisch, dass beide Schemata asymptotisch perfekt sind (nicht autorisierte Mengen erhalten asymptotisch keine Information über das Geheimnis) und asymptotisch ideal sind (die Informationsrate geht gegen 1, wenn die Größe des Geheimnisses wächst).
Vergleich mit dem Stand der Technik: Die Arbeit zeigt in Tabellen, dass ihre Schemata die einzige Kombination aus Sicherheit, Unterstützung flexibler Share-Größen und asymptotischer Idealität unter den CRT-basierten Ansätzen bieten.

4. Ergebnisse

Korrektheit: Es wurde bewiesen, dass jede autorisierte Menge das Geheimnis korrekt rekonstruieren kann.
Sicherheit (Asymptotische Perfektheit): Für jede nicht autorisierte Menge $B$ geht der Informationsverlust $\Delta(|S|) = H(S) - H(S|V_B)$ gegen 0, wenn die Größe des Geheimnisraums $|S|$ (bzw. $m_0$ ) gegen unendlich geht. Dies wird durch die Analyse der Anzahl möglicher Kandidaten für das Geheimnis unter Verwendung der Eigenschaften der k-kompakten Folgen gezeigt.
Informationsrate: Die Informationsrate $\rho$ nähert sich dem Wert 1 an, da die Größe der Shares ( $m_i$ ) im Verhältnis zur Geheimnisgröße ( $m_0$ ) bei großen $m_0$ nur geringfügig größer wird (dank der Eigenschaft $m_i \approx k \cdot m_0$ ).
Effizienz: Die Rechenkomplexität für den Dealer und die Teilnehmer ist polynomial, im Gegensatz zu früheren Ansätzen, die exponentielle Zeit benötigten oder Matrizen auf Nicht-Singularität prüfen mussten.

5. Bedeutung

Diese Arbeit adressiert eine langjährige Lücke in der Kryptographie: Die Konstruktion von hierarchischen Secret-Sharing-Verfahren, die gleichzeitig sicher, effizient und nahezu ideal (hohe Informationsrate) sind, während sie die Flexibilität unterschiedlicher Share-Größen beibehalten.

Praktische Relevanz: Die Schemata eignen sich für Anwendungen, in denen verschiedene Abteilungen oder Hierarchieebenen unterschiedliche Zugriffsrechte benötigen (z. B. Finanzwesen, militärische Befehlsketten), ohne dass der Overhead durch große Shares oder unsichere Konstruktionen in Kauf genommen werden muss.
Theoretischer Fortschritt: Die Arbeit widerlegt implizit die Sicherheit einiger zuvor als sicher geltender CRT-basierter Schemata und liefert einen neuen, robusten Baustein für die Konstruktion von Secret-Sharing-Systemen auf dem Integer-Ring. Sie zeigt, dass Einwegfunktionen in Kombination mit dem CRT effektiv genutzt werden können, um die Sicherheitslücken zu schließen, die bei reinen CRT-Ansätzen auftreten.

Zusammenfassend stellen die vorgeschlagenen DHSS- und CHSS-Schemata einen bedeutenden Schritt nach vorne dar, um hierarchische Zugriffskontrollen in Secret-Sharing-Systemen sowohl theoretisch als auch praktisch zu optimieren.