افتراض ديفي-هيلمان للقرار

يُعد افتراض ديفي -هيلمان الحاسم (DDH) افتراضًا يتعلق بصعوبة الحساب في مسألة معينة تتضمن اللوغاريتمات المنفصلة في المجموعات الدورية . ويُستخدم كأساس لإثبات أمان العديد من بروتوكولات التشفير ، وأبرزها أنظمة التشفير ElGamal و Cramer-Shoup .

لنفترض مجموعة دورية (ضربية)${\displaystyle G}$من النظام${\displaystyle q}$ومع مولد كهربائي${\displaystyle g}$ينص افتراض DDH على أنه، بالنظر إلى${\displaystyle g^{a}}$و${\displaystyle g^{b}}$لاختيار موحد ومستقل ${\displaystyle a,b\in \mathbb {Z} _{q}}$، القيمة${\displaystyle g^{ab}}$"يبدو" كعنصر عشوائي في${\displaystyle G}$.

يمكن التعبير عن هذا المفهوم البديهي رسميًا بالقول إن توزيعي الاحتمال التاليين لا يمكن تمييزهما حسابيًا (في معامل الأمان ،${\displaystyle n=\log(q)}$):

• ${\displaystyle (g^{a},g^{b},g^{ab})}$، أين${\displaystyle a}$و${\displaystyle b}$يتم اختيارها عشوائياً وبشكل مستقل من${\displaystyle \mathbb {Z} _{q}}$.
• ${\displaystyle (g^{a},g^{b},g^{c})}$، أين${\displaystyle a,b,c}$يتم اختيارها عشوائياً وبشكل مستقل من${\displaystyle \mathbb {Z} _{q}}$.

غالباً ما تسمى الثلاثيات من النوع الأول بالثلاثيات DDH أو مجموعات DDH .

يرتبط افتراض DDH بافتراض اللوغاريتم المنفصل . إذا كان من الممكن حساب اللوغاريتمات المنفصلة بكفاءة في${\displaystyle G}$إذاً، فإن افتراض DDH لن يكون صحيحاً في${\displaystyle G}$. منح${\displaystyle (g^{a},g^{b},z)}$يمكن للمرء أن يقرر بكفاءة ما إذا${\displaystyle z=g^{ab}}$من خلال أخذ المنفصل أولاً${\displaystyle \log _{g}}$ل${\displaystyle g^{a}}$ثم المقارنة${\displaystyle z}$مع${\displaystyle (g^{b})^{a}}$.

يُعتبر افتراض DDH أقوى من افتراض اللوغاريتم المنفصل، لأن هناك مجموعات يُعتقد أن حساب اللوغاريتمات المنفصلة فيها صعب (وبالتالي يُعتقد أن افتراض DL صحيح)، بينما يسهل اكتشاف مجموعات DDH (وبالتالي يكون افتراض DDH خاطئًا). ولهذا السبب، يُعتبر اشتراط صحة افتراض DDH في مجموعة ما شرطًا أكثر تقييدًا من شرط DL.

يرتبط افتراض DDH أيضًا بافتراض Diffie-Hellman الحسابي (CDH). إذا كان من الممكن حساب ذلك بكفاءة${\displaystyle g^{ab}}$من${\displaystyle (g^{a},g^{b})}$عندئذٍ، يمكن التمييز بسهولة بين توزيعي الاحتمال المذكورين أعلاه. يُعتبر افتراض DDH أقوى من افتراض CDH، لأنه إذا تم حل CDH، فهذا يعني أنه يمكننا الحصول على${\displaystyle g^{ab}}$، وسيصبح الجواب على خلع الورك الخلقي واضحاً.

إن مشكلة اكتشاف مجموعات DDH هي مشكلة عشوائية ذاتية الاختزال ، مما يعني، بشكل تقريبي، أنه إذا كان الأمر صعبًا حتى بالنسبة لجزء صغير من المدخلات، فسيكون الأمر صعبًا بالنسبة لجميع المدخلات تقريبًا؛ وإذا كان الأمر سهلاً حتى بالنسبة لجزء صغير من المدخلات، فسيكون الأمر سهلاً بالنسبة لجميع المدخلات تقريبًا.

عند استخدام بروتوكول تشفير يعتمد أمانه على افتراض DDH، فمن المهم أن يتم تنفيذ البروتوكول باستخدام مجموعات يُعتقد أن DDH ينطبق عليها:

• المجموعة الفرعية${\displaystyle \mathbb {G} _{q}}$ل${\displaystyle k}$البقايا رقم -th modulo a prime${\displaystyle p=kq+1}$، أين${\displaystyle q}$وهو أيضًا عدد أولي كبير (يُسمى أيضًا زمرة شنور ). في حالة${\displaystyle k=2}$وهذا يتوافق مع مجموعة البقايا التربيعية modulo a عدد أولي آمن .
• مجموعة القسمة${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$لضمان أمان رأس المال الأساسي${\displaystyle p=2q+1}$، والتي تتكون من المشاركات${\displaystyle \{\{1,-1\},\ldots \{q,-q\}\}}$هذه المجموعات المشاركة${\displaystyle \{x,-x\}}$يمكن تمثيلها بواسطة${\displaystyle x}$وهذا يعني${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}\equiv \{1,\ldots ,q\}}$. منذ${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$و${\displaystyle \mathbb {G} _{q}}$متماثلة، ويمكن حساب التماثل بكفاءة في كلا الاتجاهين، فإن DDH صعب بنفس القدر في كلتا المجموعتين.
• منحنى إهليلجي من الرتبة الأولية${\displaystyle E}$في الملعب${\displaystyle GF(p)}$، أين${\displaystyle p}$هو عدد أولي، بشرط${\displaystyle E}$يتمتع بدرجة تضمين كبيرة.
• مصفوفة جاكوبية لمنحنى إهليلجي فائق على الحقل${\displaystyle GF(p)}$مع عدد أولي من القواسم المختزلة، حيث${\displaystyle p}$يكون أوليًا، بشرط أن يكون للمصفوفة اليعقوبية درجة تضمين كبيرة.

من المهم الإشارة إلى أن فرضية DDH لا تنطبق في المجموعة الضربية${\displaystyle \mathbb {Z} _{p}^{*}}$، أين${\displaystyle p}$هو عدد أولي. هذا لأنه إذا${\displaystyle g}$هو مولد لـ${\displaystyle \mathbb {Z} _{p}^{*}}$ثم رمز ليجندر لـ${\displaystyle g^{a}}$يكشف ما إذا كان${\displaystyle a}$زوجي أو فردي. معطى${\displaystyle g^{a}}$،${\displaystyle g^{b}}$و${\displaystyle g^{ab}}$وبالتالي، يمكن للمرء حساب ومقارنة أقل بت أهمية بكفاءة${\displaystyle a}$،${\displaystyle b}$و${\displaystyle ab}$، على التوالي، مما يوفر طريقة احتمالية للتمييز${\displaystyle g^{ab}}$من عنصر مجموعة عشوائي.

لا ينطبق افتراض DDH على المنحنيات الإهليلجية فوق${\displaystyle GF(p)}$مع درجة تضمين صغيرة (على سبيل المثال، أقل من${\displaystyle \log ^{2}(p)}$)، وهي فئة تشمل المنحنيات الإهليلجية فائقة التفرد . وذلك لأن اقتران ويل أو اقتران تيت يمكن استخدامهما لحل المشكلة مباشرة على النحو التالي: معطى${\displaystyle P,aP,bP,cP}$على مثل هذا المنحنى، يمكن للمرء أن يحسب${\displaystyle e(P,cP)}$و${\displaystyle e(aP,bP)}$بسبب خاصية الخطية الثنائية للاقترانات، يكون التعبيران متساويين إذا وفقط إذا${\displaystyle ab=c}$modulo ترتيب${\displaystyle P}$إذا كانت درجة التضمين كبيرة (على سبيل المثال، بحجم حوالي${\displaystyle p}$في هذه الحالة، سيظل افتراض DDH قائمًا لأن عملية الاقتران لا يمكن حسابها. حتى لو كانت درجة التضمين صغيرة، فهناك بعض المجموعات الفرعية للمنحنى التي يُعتقد أن افتراض DDH ينطبق عليها.

• مسألة ديفي-هيلمان
• تبادل مفاتيح ديفي-هيلمان
• افتراضات صعوبة الحساب
• افتراض XDH
• افتراض الخطية القرارية

• بونيه، دان (1998). "مسألة ديفي-هيلمان للقرار". وقائع الندوة الثالثة لنظرية الأعداد الخوارزمية . سلسلة محاضرات في علوم الحاسوب. المجلد  1423. الصفحات 48-63 . CiteSeerX 10.1.1.461.9971 . doi : 10.1007/BFb0054851 . ISBN   978-3-540-64657-0.