Software implementation of zero-knowledge proof based on NP-complete problem of 3-coloring | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 30 ноября, печатный экземпляр отправим 4 декабря.

Опубликовать статью в журнале

Автор:

Научный руководитель:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №6 (505) февраль 2024 г.

Дата публикации: 12.02.2024

Статья просмотрена: 10 раз

Библиографическое описание:

Зенич, Д. Н. Software implementation of zero-knowledge proof based on NP-complete problem of 3-coloring / Д. Н. Зенич. — Текст : непосредственный // Молодой ученый. — 2024. — № 6 (505). — С. 5-7. — URL: https://moluch.ru/archive/505/111166/ (дата обращения: 21.11.2024).



The purpose of this article is to find a way to implement a zero-knowledge proof based on the NP-hard problem of 3-coloring in the form of software while maintaining the efficiency condition of the algorithm.

Keywords: zero-knowledge proof, authentication, algorithm, graph, protocol, 3-coloring.

Целью данной статьи является поиск способа реализации доказательства с нулевым разглашением, основанного на NP-сложной задаче о трехцветной раскраске графа, в виде программного обеспечения с сохранением условия эффективности алгоритма.

Ключевые слова: доказательство с нулевым разглашением, аутентификация, алгоритм, граф, протокол, криптография, трехцветная раскраска.

The emergence of processes such as identification and authentication was due to the need to distinguish people according to various characteristics, to compare a person with a specific group of people, and to determine whether a person is who he is trying to impersonate.

The most common method of identity verification in information systems remains single-factor authentication with a password, but this method is not only the most widespread, but also one of the oldest. If in ancient times the password fulfilled the duties assigned to it, then in our time, with the growth of computing power, the problems of this authentication method are becoming more pronounced. A simple password is easy to remember, but also easy to pick up, therefore, to increase the complexity of selection, it is necessary to increase the complexity of the password, but as it increases, the difficulty to remember also increases in direct proportion. In addition, to pass the authentication procedure, it is necessary to provide the relying party with the password itself, which can have extremely undesirable consequences in the unlikely but very real case if the security of the authentication system is compromised.

The use of zero-knowledge proof in authentication systems will save them from the problems listed above.

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true [1].

As is known, for any NP-complete problem there is no efficient solution algorithm, which means that on the basis of any NP-complete problem a zero-knowledge proof protocol can be constructed [2]. But there is a problem with programming the zero-knowledge proof.

Consider a zero-knowledge proof protocol based on the NP-complete 3-coloring problem [3]. The Prover claims to have a solution certificate for an instance of the 3-сoloring problem. He cannot simply disclose the solution certificate to the Verifier, the latter, in turn, cannot trust the Prover at his word and requires convincing evidence.

Изображение выглядит как линия, оригами, дизайн

Автоматически созданное описание

Fig. 1. An instance of the 3-coloring problem of G graph

Изображение выглядит как линия, круг, оригами

Автоматически созданное описание

Fig. 2. Certificate of solving the problem of 3-coloring graph G

To solve this problem, a third trusted party can be involved in the protocol. In this case, the Prover and the Verifier fully trust the Trusted, all three parties have information about the structure of the graph, but only the Prover and the Trustee have absolutely identical versions of its three-color coloring, and the latter undertake to change the colors of the vertices identically with each iteration of the protocol. It is important to clarify that the Trusted, unlike the Prover, who can be «dishonest», always has the right solution.

The protocol begins with the Verifier choosing a random edge and generate random bits and after which it passes the edge

and bit to Prover.

The Prover receive edge and bit , knowing colors and of vertices and he changes them in accordance with the obligation, thereby obtaining new colors and , then for vertices

and he picks values , , , such that and , at the same time, these pairs must be selected from one of three sets: 0:{(0;0),(2;2),(1;1)}, 1:{(1;2),(0;1),(2;0)}, 2:{(2;1),(1;0),(0;2)}. Depending on the received bit , the Prover passes values and , where
to the Verifier and changes all the colors of the graph vertices in accordance with the agreement.

The Prover receives values and . At this stage the Verifier can check if the vertices are not of the same color. This check is performed as follows: if the vertices and are of the same color, then therefore, the protocol terminates, otherwise the protocol continues, the Verifier passes an edge and bits and to Trusted.

Trusted receives the edge

and bits and .

If : knowing colors and of vertices and he changes them in accordance with the obligation, thereby obtaining new colors and , then for vertices

and he picks values , , , so that they are identical to the corresponding values of the Prover. Depending on the received bit , the Trusted sends values and , where , to the Verifier and changes all the colors of the graph vertices in accordance with the agreement.

The Verifier receives values and : at this stage the Verifier can check the Prover's knowledge of the 3-coloring. This check is performed as follows: if the Prover really knows the 3-coloring and changes all three colors at each iteration of the loop, then the equality will not be satisfied, otherwise the protocol ends.

If : knowing colors and of vertices and he changes them in accordance with the obligation, thereby obtaining new colors and

, then for vertices and he picks values , , , so that they are identical to the corresponding values of the Prover. Depending on the received bit , the Trusted sends value , where .

The Verifier receives value

: at this stage the Verifier can check the correctness of the answers sent by the Prover. This check is performed as follows: if the Prover actually sends correct answers, then the equality will hold, otherwise the protocol ends.

In conclusion, the idea of the article was to was to rethink the zero-knowledge proof based on the NP-complete 3-coloring problem and then apply this principle to create an authentication system that uses knowledge of the solution certificate in the process of authenticating subjects, which can become an alternative to password authentication methods.

References:

  1. Goldwasser S., Micali S., Rackoff C. The knowledge complexity of interactive proof systems // SIAM J. Comput. / M. Sudan — SIAM, 1989. — Vol. 18, Iss. 1. — P. 186— 208.
  2. Goldreich O., Micali S., Wigderson A. How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design: Extended Abstract // Advances in Cryptology — CRYPTO ’86: 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / A. M. Odlyzko — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Berlin Heidelberg, 1987. — P. 171–185. — 490 p.
  3. Goldreich O. Zero-Knowledge Proofs for NP: Commitment Schemes // Foundations of Cryptography Basic Tools: Volume 1. — Cambrige University Press, 2001. — P. 224. — 372 p.
Основные термины (генерируются автоматически): SIAM, CRYPTO, USA, нулевое разглашение.


Ключевые слова

protocol, algorithm, zero-knowledge proof, authentication, graph, 3-coloring

Похожие статьи

Mathematical Simulation of Industrial Waste Processing

The article is devoted to technological and environmental problems in the food industry. Authors suggested a cluster model to serve as a basis for the software, useful at the initial design stage, when it is important to determine the optimal set and...

End-to-end encryption systems: problems of the information protection

This paper investigates some methods of cryptographic protection of information during its transmission over insecure channels. Our work reveals the principle of encryption using a decentralized key distribution as a way to transform the processed in...

Features of developing mobile applications on the Thunkable platform

This article discusses the possibility of using a cloud environment for developing mobile applications, called Thunkable, in educational processes. The main features of working with the environment, its advantages and disadvantages are considered.

To the question of practical use of ''Smart home'' system

The article focuses on the design and creation process of the automated integrated system for monitoring and control of home appliances and other things used in a person's everyday life. The following advantages of the system are taken into considera...

Modeling the process of teaching a foreign language utterance using multimedia

The article reflects the main stages of modeling teaching utterance in multimedia context as a process of forming a speech action image. The properties of the information space are considered as the basis for image modeling, interactive components —...

Excel-application «Select switches»

Modern electric power systems are a combination of complex objects with various factors of mutual influence, and therefore, to solve any issues relating to the design and subsequent operation of these objects, the development and use of specialized s...

The role of teaching technologies in the development of speech and written speech in the English language

This article discusses the formation of language learning skills in the process of learning English to improve independent writing skills of students using information technology and the development of their creative abilities.

Logo detection in images with a complex background using the contour information of images

Text detection has gotten a great attention as highly active application-oriented research area in computer vision, artificial intelligence, and image processing. In this article, we implement the algorithm for text logo detection in images with a c...

Framework for assessing enterprise risks using the Analytic Hierarchy Process

This article is intended to introduce the way of adapting the Analytic Hierarchy Process Method to the assessment of economic risks at the enterprise. In order to show it we calculate the risks for the project of implementing cloud storage to the uni...

Selection of backend technologies for creation of web application

The article is devoted to analyzing various server technologies required for creating web applications. In the process of research, the importance of these technologies for providing performance, scalability and high functionality of web applications...

Похожие статьи

Mathematical Simulation of Industrial Waste Processing

The article is devoted to technological and environmental problems in the food industry. Authors suggested a cluster model to serve as a basis for the software, useful at the initial design stage, when it is important to determine the optimal set and...

End-to-end encryption systems: problems of the information protection

This paper investigates some methods of cryptographic protection of information during its transmission over insecure channels. Our work reveals the principle of encryption using a decentralized key distribution as a way to transform the processed in...

Features of developing mobile applications on the Thunkable platform

This article discusses the possibility of using a cloud environment for developing mobile applications, called Thunkable, in educational processes. The main features of working with the environment, its advantages and disadvantages are considered.

To the question of practical use of ''Smart home'' system

The article focuses on the design and creation process of the automated integrated system for monitoring and control of home appliances and other things used in a person's everyday life. The following advantages of the system are taken into considera...

Modeling the process of teaching a foreign language utterance using multimedia

The article reflects the main stages of modeling teaching utterance in multimedia context as a process of forming a speech action image. The properties of the information space are considered as the basis for image modeling, interactive components —...

Excel-application «Select switches»

Modern electric power systems are a combination of complex objects with various factors of mutual influence, and therefore, to solve any issues relating to the design and subsequent operation of these objects, the development and use of specialized s...

The role of teaching technologies in the development of speech and written speech in the English language

This article discusses the formation of language learning skills in the process of learning English to improve independent writing skills of students using information technology and the development of their creative abilities.

Logo detection in images with a complex background using the contour information of images

Text detection has gotten a great attention as highly active application-oriented research area in computer vision, artificial intelligence, and image processing. In this article, we implement the algorithm for text logo detection in images with a c...

Framework for assessing enterprise risks using the Analytic Hierarchy Process

This article is intended to introduce the way of adapting the Analytic Hierarchy Process Method to the assessment of economic risks at the enterprise. In order to show it we calculate the risks for the project of implementing cloud storage to the uni...

Selection of backend technologies for creation of web application

The article is devoted to analyzing various server technologies required for creating web applications. In the process of research, the importance of these technologies for providing performance, scalability and high functionality of web applications...

Задать вопрос