A zero knowledge authentication protocol based on novel heuristic algorithm of dense induced subgraphs isomorphism

Abstract EN

Graphs provide an useful mathematical tool for modeling various real world phenomena.

Dense graphs arise in many places of interest, for instance the internet and social networks to name just two.

The density of a graph should be a real number reflecting just how many edges it contains.

Many networks found in the real world share the so-called “small world” property that is organized into communities.

These organizations rely on close relationships of people belonging to a same subgroup.

The term “network” is used to denote the real world entity that usually maps to a graph after it is modeled.

Therefore, there is greater need to propose more efficient graph and subgraph match methods to decide if their structures are identical.

Reduce the search space in these networks motivate many researchers to give generously persevering attempt to propose a new efficient algorithm for that purpose.

According to theoretical and practical interest in graph isomorphism, a new algorithm for determining graph isomorphism between two dense graphs is proposed.

Furthermore, a new algorithm for determining an induced subgraph isomorphism between pattern and target graphs is proposed also.

Those algorithms are analyzed from complexity point of view to demonstrate its effectiveness after applying it to several types of graphs.

It is demonstrated that subgraph isomorphism is an improvement over the use of graph isomorphism in the zero knowledge protocol.

The improvement comes from subgraph isomorphism being an NPcomplete problem, and therefore, more difficult for an unauthorized user to solve.

Whereas, the graph isomorphism problem has been solved therefore, is vulnerable to attacks of malicious users.

The algorithms have been applied using VB-language, with two easy to use interfaces to be helpful for the beneficiary.