TY - JOUR ID - TI - A Zero Knowledge Authentication Protocol Based on Novel Heuristic Algorithm of Dense Induced Subgraphs Isomorphism بروتوكولات التوثيق بالمعرفة الصفرية بالاعتماد على خوارزمية الكشف عن البيانات الكثيفة المقطعية المتشاكلة AU - N. M. G. Al-Saidi AU - N.A. Rajab AU - H. N. Abdul-Rahman PY - 2015 VL - 33 IS - 1 Part (B) Scientific SP - 110 EP - 126 JO - Engineering and Technology Journal مجلة الهندسة والتكنولوجيا SN - 16816900 24120758 AB - 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 NP-complete 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.

توفر البيانات أدوات مفيدة للنماذج الرياضية المختلفة التي تستخدم في التطبيقات الواقعية. ان للبيانات الكثيفة فوائد عديدة، على سبيل المثال شبكة الإنترنت والشبكات الاجتماعية. كما ان كثافة هذه البيانات تتحدد بعدد حقيقي من الحافات التي تحتويها.يستخدم مصطلح" الشبكة" للدلالة على كيان العالم الحقيقي الذي يحول الى بيان. يوجد في هذا العالم العديد من الشبكات التي تشترك في ما بينها لتجعل العالم اصغر.بالتالي فان هنالك حاجة كبيرة لاقتراح خوارزميات تتعامل مع البيانات والبيانات الجزئية لتحدد فيما إذا كانت هياكلها متطابقة. ان تقليل مساحة البحث في هذه الشبكات تحفز العديد من الباحثين لاقتراح خوارزمية جديدة فعالة لهذا الغرض. نظرا للفائده النظرية والعملية للبيانات المتشاكله، تم اقتراح خوارزمية جديدة لتحديد التشاكل بين اي اثنين من البيانات الكثيفة. وعلاوة على ذلك،تم اقتراح خوارزمية جديدة لتحديد البيانات الجزئية المتشاكلة,تعتمد على تحليل البيان إلى مجموعة من المسارات، من ثم تحديد اقصرالمسارات التي تربط بين اي رأسين من روؤس البيان. ان استخدام التشاكل الجزئي في البيانات هو تحسين على استخدام التشاكل في بروتوكولات المعرفة الصفرية(Zero-Knowledge). هذا التحسين يكمن في كون التشاكل الجزئي هو من المسائل المعقدة (NP-Complete)، وبالتالي فانه من الصعب على الاشخاص غير المخولين حلها. في حين تم حل مسائل التشاكل في البيانات وبالتالي تعرضها لهجمات من قبل المستخدمين المتطفلين.تم تطبيقا لخوارزميات باستخدام لغة الـ VB، مع واجهتين سهلة الاستخدام,لكي تكون مفيدة للمستخدم المستفيد. ER -