A zero knowledge authentication protocol based on novel heuristic algorithm of dense induced subgraphs isomorphism
Other Title(s)
بروتوكولات التوثيق بالمعرفة الصفرية بالاعتماد على خوارزمية الكشف عن البيانات الكثيفة المقطعية المتشاكلة
Joint Authors
Rajab, N. A.
Abd al-Rahman, H. N.
al-Saidi, Nadiyah Muhammad Ghanim Jawhar
Source
Engineering and Technology Journal
Issue
Vol. 33, Issue 1B (31 Jan. 2015), pp.110-126, 17 p.
Publisher
Publication Date
2015-01-31
Country of Publication
Iraq
No. of Pages
17
Main Subjects
Abstract AR
توفر البيانات أدوات مفيدة للنماذج الرياضية المختلفة التي تستخدم في التطبيقات الواقعية.
إن للبيانات الكثيفة فوائد عديدة، على سبيل المثال شبكة الإنترنت و الشبكات الاجتماعية.
كما أن كثافة هذه البيانات تتحدد بعدد حقيقي من الحافات التي تحتويها يستخدم مصطلح "الشبكة" للدلالة على كيان العالم الحقيقي الذي يحول إلى بيان.
يوجد في هذا العالم العديد من الشبكات التي تشترك في ما بينها لتجعل العالم أصغر.
بالتالي فإن هنالك حاجة كبيرة لاقتراح خوارزميات تتعامل مع البيانات و البيانات الجزئية لتحدد فيما إذا كانت هياكلها متطابقة.
إن تقليل مساحة البحث في هذه الشبكات تحفز العديد من الباحثين لاقتراح خوارزمية جديدة فعالة لهذا الغرض.
نظراً للفائدة النظرية و العملية للبيانات المتشاكلة، تم اقتراح خوارزمية جديدة لتحديد التشاكل بين أي اثنين من البيانات الكثيفة.
و علاوة على ذلك، تم اقتراح خوارزمية جديدة لتحديد البيانات الجزئية المتشاكلة، تعتمد على تحليل البيان إلى مجموعة من المسارات، من ثم تحديد أقصر المسارات التي تربط بين أي رأسين من رؤوس البيان.
إن استخدام التشاكل الجزئي في البيانات هو تحسين على استخدام التشاكل في بروتوكولات المعرفة الصفرية (Zero-Knowledge).
هذا التحسين يكمن في كون التشاكل الجزئي هو من المسائل المعقدة (NP-Complete)، و بالتالي فإنه من الصعب على الأشخاص غير المخولين حلها.
في حين تم حل مسائل التشاكل في البيانات و بالتالي تعرضها لهجمات من قبل المستخدمين المتطفلين.
تم تطبيقا لخوارزميات باستخدام لغة الـ VB، مع واجهتين سهلة الاستخدام، لكي تكون مفيدة للمستخدم المستفيد.
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.
American Psychological Association (APA)
al-Saidi, Nadiyah Muhammad Ghanim Jawhar& Rajab, N. A.& Abd al-Rahman, H. N.. 2015. A zero knowledge authentication protocol based on novel heuristic algorithm of dense induced subgraphs isomorphism. Engineering and Technology Journal،Vol. 33, no. 1B, pp.110-126.
https://search.emarefa.net/detail/BIM-565034
Modern Language Association (MLA)
al-Saidi, Nadiyah Muhammad Ghanim Jawhar…[et al.]. A zero knowledge authentication protocol based on novel heuristic algorithm of dense induced subgraphs isomorphism. Engineering and Technology Journal Vol. 33, no. 1B ( 2015), pp.110-126.
https://search.emarefa.net/detail/BIM-565034
American Medical Association (AMA)
al-Saidi, Nadiyah Muhammad Ghanim Jawhar& Rajab, N. A.& Abd al-Rahman, H. N.. A zero knowledge authentication protocol based on novel heuristic algorithm of dense induced subgraphs isomorphism. Engineering and Technology Journal. 2015. Vol. 33, no. 1B, pp.110-126.
https://search.emarefa.net/detail/BIM-565034
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 125-126
Record ID
BIM-565034