DOI: https://doi.org/10.1587/transfun.2025dmp0010
تاريخ النشر: 2026-01-01
المؤلف: Ren IGARI وآخرون
الموضوع الرئيسي: طرق رسمية في التحقق
نظرة عامة
تتناول الورقة مشكلة دورة هاملتونية، وهي تحدٍ NP-complete في نظرية الرسوم البيانية لها آثار كبيرة على التطبيقات العملية مثل تصميم VLSI ومشكلة البائع المتجول (TSP). يقدم المؤلفون بروتوكولات جديدة لإثبات المعرفة الصفرية الفيزيائية التي تسمح لطرف واحد بإثبات معرفة بحل ما لطرف آخر دون الكشف عن أي تفاصيل حول الحل نفسه. تظهر هذه البروتوكولات كفاءة محسّنة مقارنة بالطرق السابقة من خلال التركيز على حواف الرسم البياني بدلاً من الرؤوس، مما يقلل من عدد الخلطات والبطاقات المطلوبة.
على وجه التحديد، يستخدم البروتوكول الأول لمشكلة دورة هاملتونية ثلاث بطاقات لكل حافة لتمثيل أسماء مستعارة للرؤوس وعضوية الحافة في الدورة الهاملتونية. يعزز البروتوكول الثاني الكفاءة بشكل أكبر من خلال استخدام مصفوفة الجوار لرسم فرعي. بالإضافة إلى ذلك، يقترح المؤلفون بروتوكول إثبات معرفة صفرية لمشكلة TSP، والذي يتضمن تمثيل التزام صحيح جديد مع بروتوكول إضافة آمن. ستتضمن الأعمال المستقبلية تقييم كفاءة التزامات المسافة المستخدمة في هذا البروتوكول، لا سيما من حيث عدد الخلطات والبطاقات المطلوبة.
مقدمة
تناقش المقدمة التشفير القائم على البطاقات، وهي طريقة تستخدم بطاقات فعلية لتمكين عدة لاعبين من تنفيذ وظائف تشفيرية. على سبيل المثال، يمكن ترميز القيم ذات البت الواحد باستخدام ترتيبات البطاقات، مما يسمح بإجراء عمليات منطقية آمنة مثل AND. تشمل التطورات الأخيرة بروتوكولات إثبات المعرفة الصفرية الفيزيائية، حيث يمكن لمثبت (????) أن يظهر معرفة بحل لمشكلة (مثل سودوكو) لمتحقق (????) دون الكشف عن الحل نفسه. تقدم هذه الطريقة عدة مزايا مقارنة بإثباتات المعرفة الصفرية التقليدية المعتمدة على الكمبيوتر، بما في ذلك القضاء على تسريبات المدخلات السرية المحتملة، وقابلية التطبيق في ألعاب حل المشكلات، وزيادة فهم المفاهيم التشفيرية لغير الخبراء.
تسلط المقدمة الضوء أيضًا على مشكلة دورة هاملتونية، وهي مشكلة NP-complete معروفة في نظرية الرسوم البيانية، والتي تتعلق بتحديد وجود دورة هاملتونية في رسم بياني معين \( G = (V_G, E_G) \). لهذه المشكلة تطبيقات كبيرة، مثل تصميم التكامل على نطاق واسع جدًا (VLSI) ومشكلة البائع المتجول. نظرًا لكونها NP-complete، تفتقر الخوارزميات الفعالة لحل مشكلة دورة هاملتونية، مما يجعل بروتوكولات إثبات المعرفة الصفرية لهذه المشكلة ذات قيمة خاصة للأفراد الذين يرغبون في إثبات معرفتهم بحل.
نقاش
في هذا القسم، يقدم المؤلفون مساهماتهم في بروتوكولات إثبات المعرفة الصفرية الفيزيائية لمشكلة دورة هاملتونية ومشكلة البائع المتجول (TSP). يقترحون بروتوكولين متميزين يركزان على الحواف بدلاً من الرؤوس، مما يبسط البروتوكولات الحالية من خلال تقليل عدد الخلطات والبطاقات المطلوبة. يستخدم بروتوكولهم الأول خلطًا عن طريق كومة ويشمل التزامًا صحيحًا جديدًا يسمى التزام صحيح ذو حرارتين، والذي يقلل من عدد البطاقات اللازمة لتمثيل المسافات بين المدن. يسمح هذا الالتزام بإجراء إضافة ومقارنة آمنة للمسافات، وهو أمر ضروري لمشكلة TSP.
يقارن المؤلفون أيضًا بروتوكولاتهم مع البروتوكولات الموجودة، مشيرين إلى أن طرقهم تتطلب عددًا أقل من الخلطات والبطاقات، لا سيما في الرسوم البيانية الكثيفة. يظهر أن البروتوكول الأول أكثر كفاءة من البروتوكول التفاعلي الذي قدمه روانغويز وإيتوه، بينما يقدم البروتوكول الثاني مزايا من حيث استخدام البطاقات. يتم إثبات أمان كلا البروتوكولين من خلال الخصوصية، والموثوقية، وخصائص المعرفة الصفرية، مما يضمن أن المثبت يمكنه إقناع المتحقق بوجود دورة هاملتونية أو حل صحيح لمشكلة TSP دون الكشف عن أي معلومات إضافية. يختتم القسم بتوضيح تنظيم الورقة، والتي تشمل مراجعة للأعمال ذات الصلة، ومعلومات خلفية عن التشفير القائم على البطاقات، ووصفًا تفصيليًا للبروتوكولات المقترحة وتحليلات أمانها.
DOI: https://doi.org/10.1587/transfun.2025dmp0010
Publication Date: 2026-01-01
Author(s): Ren IGARI et al.
Primary Topic: Formal Methods in Verification
Overview
The paper addresses the Hamiltonian cycle problem, an NP-complete challenge in graph theory with significant implications for practical applications like VLSI design and the traveling salesman problem (TSP). The authors introduce novel physical zero-knowledge proof protocols that allow one party to prove knowledge of a solution to another without revealing any details about the solution itself. These protocols demonstrate improved efficiency over previous methods by focusing on the edges of the graph rather than the vertices, thereby reducing the number of required shuffles and cards.
Specifically, the first protocol for the Hamiltonian cycle problem utilizes three cards per edge to represent vertex pseudonyms and edge membership in the Hamiltonian cycle. The second protocol enhances efficiency further by employing the adjacency matrix of a subgraph. Additionally, the authors propose a zero-knowledge proof protocol for the TSP, which incorporates a new integer commitment representation along with a secure addition protocol. Future work will involve evaluating the efficiency of the distance commitments used in this protocol, particularly in terms of the number of shuffles and cards required.
Introduction
The introduction discusses card-based cryptography, a method utilizing physical cards to enable multiple players to execute cryptographic functions. For instance, one-bit values can be encoded using card arrangements, allowing for secure logical operations like AND. Recent advancements include physical zero-knowledge proof protocols, where a prover (????) can demonstrate knowledge of a solution to a problem (e.g., Sudoku) to a verifier (????) without revealing the solution itself. This approach offers several advantages over traditional computer-based zero-knowledge proofs, including the elimination of potential secret input leaks, applicability in problem-solving games, and enhanced comprehension of cryptographic concepts for non-experts.
The introduction also highlights the Hamiltonian cycle problem, a well-known NP-complete problem in graph theory, which involves determining the existence of a Hamiltonian cycle in a given graph \( G = (V_G, E_G) \). This problem has significant applications, such as in very large scale integration (VLSI) design and the traveling salesman problem. Given its NP-completeness, efficient algorithms for solving the Hamiltonian cycle problem are lacking, making zero-knowledge proof protocols for this problem particularly valuable for individuals wishing to prove their knowledge of a solution.
Discussion
In this section, the authors present their contributions to physical zero-knowledge proof protocols for the Hamiltonian cycle problem and the Traveling Salesman Problem (TSP). They propose two distinct protocols that focus on edges rather than vertices, simplifying the existing protocols by reducing the number of required shuffles and cards. Their first protocol utilizes a pile-scramble shuffle and incorporates a new integer commitment called the two-hot integer commitment, which minimizes the number of cards needed for representing distances between cities. This commitment allows for secure addition and comparison of distances, essential for the TSP.
The authors also compare their protocols with existing ones, highlighting that their methods require fewer shuffles and cards, particularly in dense graphs. The first protocol is shown to be more efficient than the interactive protocol by Ruangwises and Itoh, while the second protocol offers advantages in terms of card usage. The security of both protocols is established through completeness, soundness, and zero-knowledge properties, ensuring that the prover can convince the verifier of the existence of a Hamiltonian cycle or a valid TSP solution without revealing any additional information. The section concludes by outlining the organization of the paper, which includes a review of related works, background information on card-based cryptography, and detailed descriptions of the proposed protocols and their security analyses.