What question did this study set out to answer?

Diese Forschung hat zum Ziel, effiziente physische Null-Wissen-Beweisprotokolle zur Lösung des Hamiltonschen Zyklus- und des Problem des Handlungsreisenden zu entwickeln.

March 28, 2026Open Access

Effiziente physische ZKP-Protokolle für das Hamiltonsche Zyklusproblem und das Problem des Handlungsreisenden

Key Points

Diese Forschung hat zum Ziel, effiziente physische Null-Wissen-Beweisprotokolle zur Lösung des Hamiltonschen Zyklus- und des Problem des Handlungsreisenden zu entwickeln.
Vorgeschlagene neue Null-Wissen-Beweisprotokolle für das Hamiltonsche Zyklusproblem.
Entwickeltes Protokoll für das Problem des Handlungsreisenden mit ganzzahliger Engagement-Darstellung.
Nutzung sicherer Additionsprotokolle zur Steigerung der Effizienz.
Neue Protokolle zeigen verbesserte Effizienz im Vergleich zu früheren Methoden.
Protokolle ermöglichen es, Wissen über Lösungen zu beweisen, ohne die Lösungen selbst preiszugeben.

Abstract

Das Hamiltonsche Zyklusproblem ist ein bekanntes NP-vollständiges Problem in der Graphentheorie. Dieses Problem steht in Bezug zu vielen praktischen Problemen wie dem Entwurf von sehr großen integrierten Schaltungen (VLSI) und dem Problem des Handlungsreisenden (TSP). Da es NP-vollständig ist, gibt es keinen effizienten Algorithmus zur Lösung des Hamiltonschen Zyklusproblems, und daher ist seine Lösung wertvoll. In dieser Arbeit schlagen wir neue physische Null-Wissen-Beweisprotokolle für das Hamiltonsche Zyklusproblem vor, wobei eine Entität ihr Wissen über eine Lösung einer anderen Entität beweisen kann, ohne Informationen über die wertvolle Lösung preiszugeben. Unsere Protokolle sind effizienter als die vorherigen Protokolle. Wir schlagen auch ein physisches Null-Wissen-Beweisprotokoll für TSP vor, eines der Bausteine ist eine neue Darstellung eines ganzzahligen Engagements mit einem sicheren Additionsprotokoll.

Bookmark

View Full Paper