خطة الالتزام

الموسوعة الحرة

مخطط الالتزام هو أداة تشفيرية أساسية تُمكّن المستخدم من الالتزام بقيمة (أو عبارة) مُختارة مع إخفائها عن الآخرين، مع إمكانية الكشف عن القيمة المُلتزم بها لاحقًا. [ 1 ] صُممت مخططات الالتزام بحيث لا يستطيع أي طرف تغيير القيمة أو العبارة بعد الالتزام بها؛ أي أن مخططات الالتزام مُلزمة . تُستخدم مخططات الالتزام في العديد من بروتوكولات التشفير، بما في ذلك قلب العملة الآمن، وإثباتات المعرفة الصفرية ، والحوسبة الآمنة .

إحدى طرق تصور آلية الالتزام هي تخيل المرسل وكأنه يضع رسالة في صندوق مغلق، ثم يسلم الصندوق إلى المستلم. تبقى الرسالة مخفية عن المستلم، الذي لا يستطيع فتح القفل بنفسه. وبما أن الصندوق بحوزة المستلم، فلا يمكن تغيير الرسالة بداخله ، وإنما يمكن الكشف عنها فقط إذا اختار المرسل إعطاءه المفتاح في وقت لاحق.

تتم التفاعلات في مخطط الالتزام على مرحلتين:

  1. مرحلة الالتزام التي يتم خلالها اختيار قيمة وتثبيتها
  2. مرحلة الكشف التي يكشف خلالها المرسل عن القيمة، ثم يتحقق المستلم من صحتها.

في الاستعارة السابقة، تمثل مرحلة الالتزام قيام المرسل بوضع الرسالة في الصندوق وإغلاقه. أما مرحلة الكشف فتمثل قيام المرسل بإعطاء المفتاح للمستقبل، الذي يستخدمه لفتح الصندوق والتحقق من محتوياته. الصندوق المغلق هو الالتزام، والمفتاح هو الدليل.

في البروتوكولات البسيطة، تتألف مرحلة الالتزام من رسالة واحدة من المرسل إلى المُستقبِل، تُسمى رسالة الالتزام . من الضروري ألا يتمكن المُستقبِل من استخراج القيمة المُختارة من الرسالة في ذلك الوقت (وهذا ما يُسمى خاصية الإخفاء ). أما مرحلة الكشف البسيطة فتتألف من رسالة واحدة، تُسمى رسالة الفتح ، من المرسل إلى المُستقبِل، يتبعها فحص يُجريه المُستقبِل. يجب أن تكون القيمة المُختارة خلال مرحلة الالتزام هي القيمة الوحيدة التي يستطيع المرسل حسابها والتي تُصبح صالحة خلال مرحلة الكشف (وهذا ما يُسمى خاصية الربط ).

ربما تمّت صياغة مفهوم مخططات الالتزام رسميًا لأول مرة على يد جيل براسارد ، وديفيد شوم ، وكلود كريبو في عام 1988، [ 2 ] كجزء من بروتوكولات المعرفة الصفرية المختلفة لـ NP ، استنادًا إلى أنواع مختلفة من مخططات الالتزام. [ 3 ] [ 4 ] ولكن استُخدم المفهوم قبل ذلك دون معالجته رسميًا. [ 5 ] [ 6 ] ظهر مفهوم الالتزامات مبكرًا في أعمال مانويل بلوم ، [ 7 ] وشيمون إيفن ، [ 8 ] وآدي شامير وآخرون. [ 9 ] يبدو أن المصطلح قد ابتكره بلوم، [ 6 ] على الرغم من أنه يمكن تسمية مخططات الالتزام بمخططات التزام البت بشكل متبادل - أحيانًا مخصصة للحالة الخاصة التي تكون فيها القيمة الملتزم بها بتًا . قبل ذلك، كان يُنظر إلى الالتزام عبر دوال التجزئة أحادية الاتجاه، على سبيل المثال، كجزء من توقيع لامبورت ، وهو مخطط التوقيع الأصلي أحادي البت لمرة واحدة.

التطبيقات

رمي العملة

لنفترض أن أليس وبوب يريدان حل نزاع ما عن طريق رمي العملة . إذا كانا موجودين فعليًا في نفس المكان، فقد يكون الإجراء المعتاد كما يلي:

  1. أليس "تتنبأ" بنتيجة رمية العملة،
  2. بوب يقلب العملة،
  3. إذا كان توقع أليس صحيحاً، فإنها تفوز، وإلا يفوز بوب.

إذا لم يكن أليس وبوب في نفس المكان، تنشأ مشكلة. فبمجرد أن تُعلن أليس عن نتيجة رمي العملة، يُمكن لبوب أن يُحدد النتيجة التي تُناسبه. وبالمثل، إذا لم تُعلن أليس عن اختيارها لبوب، فبعد أن يرمي بوب العملة ويُعلن النتيجة، يُمكن لأليس أن تُخبره بأنها اختارت النتيجة التي تُناسبه. يُمكن لأليس وبوب استخدام الالتزامات في إجراء يسمح لكليهما بالوثوق بالنتيجة.

  1. أليس "تتوقع" نتيجة رمي العملة، لكنها لا تخبر بوب إلا بالتزامها بتوقعها.
  2. يقلب بوب العملة المعدنية ويعلن النتيجة،
  3. أليس تكشف عما التزمت به،
  4. يتأكد بوب من أن مكالمة أليس تتطابق مع التزامها.
  5. إذا تطابقت نتيجة أليس مع نتيجة العملة التي أبلغ عنها بوب، فإن أليس تفوز.

لكي يتمكن بوب من تحريف النتائج لصالحه، يجب أن يفهم المغزى الضمني في التزام أليس. إذا كان نظام الالتزام جيدًا، فلن يتمكن بوب من تحريف النتائج. وبالمثل، لا تستطيع أليس التأثير على النتيجة إذا لم تتمكن من تغيير القيمة التي التزمت بها.

يوجد تطبيق واقعي لهذه المشكلة، عندما يلتزم الناس (غالباً في وسائل الإعلام) بقرار أو يقدمون إجابة في "مظروف مغلق"، ثم يُفتح لاحقاً. ويمكن اعتبار عبارة "دعونا نكتشف ما إذا كانت هذه هي إجابة المرشح"، على سبيل المثال في برنامج مسابقات، نموذجاً لهذا النظام.

براهين المعرفة الصفرية

من الأمثلة المحفزة استخدام مخططات الالتزام في براهين المعرفة الصفرية . تُستخدم الالتزامات في براهين المعرفة الصفرية لغرضين رئيسيين: أولًا، لتمكين المُثبت من المشاركة في براهين "الاختيار والاختيار" حيث يُعرض على المُدقِّق خيارٌ لما يجب معرفته، ولا يكشف المُثبت إلا ما يتوافق مع اختيار المُدقِّق. تسمح مخططات الالتزام للمُثبت بتحديد جميع المعلومات مسبقًا، والكشف فقط عما يجب الكشف عنه لاحقًا في البرهان. [ 10 ] ثانيًا، يستخدم المُدقِّق الالتزامات أيضًا في براهين المعرفة الصفرية، حيث يُحدد غالبًا خياراته مسبقًا في التزام. يسمح هذا بتكوين براهين المعرفة الصفرية بالتوازي دون الكشف عن معلومات إضافية للمُثبت. [ 11 ]

مخططات التوقيع

نظام لامبورت للتوقيع هو نظام توقيع رقمي يعتمد على الاحتفاظ بمجموعتين من حزم البيانات السرية ، ونشر تجزئات قابلة للتحقق من حزم البيانات، ثم الكشف بشكل انتقائي عن أجزاء من حزم البيانات السرية بطريقة تتوافق تحديدًا مع البيانات المراد توقيعها. وبهذه الطريقة، يصبح الالتزام العلني المسبق بالقيم السرية جزءًا أساسيًا من آلية عمل النظام.

نظرًا لعدم إمكانية استخدام نظام توقيع لامبورت أكثر من مرة، فقد طُوّر نظامٌ لدمج العديد من مجموعات مفاتيح لامبورت ضمن قيمة عامة واحدة يمكن ربطها بشخصٍ ما والتحقق منها من قِبل الآخرين. يستخدم هذا النظام أشجار التجزئة لضغط العديد من مجموعات التزام مفاتيح لامبورت المنشورة في قيمة تجزئة واحدة يمكن ربطها بالمؤلف المحتمل للبيانات التي سيتم التحقق منها لاحقًا.

مشاركة الأسرار القابلة للتحقق

يُعدّ تبادل الأسرار القابل للتحقق تطبيقًا هامًا آخر للالتزامات ، وهو عنصر أساسي في الحوسبة الآمنة متعددة الأطراف . في نظام تبادل الأسرار ، يتلقى كل طرف من الأطراف المتعددة "حصصًا" من قيمة يُفترض إخفاؤها عن الجميع. إذا اجتمع عدد كافٍ من الأطراف، يُمكن استخدام حصصهم لإعادة بناء السر، ولكن حتى مجموعة خبيثة صغيرة الحجم لن تتمكن من معرفة أي شيء. يُمثّل تبادل الأسرار أساسًا للعديد من بروتوكولات الحوسبة الآمنة : فمن أجل حساب دالة بشكل آمن لمدخلات مشتركة، يتم التلاعب بحصص السر. مع ذلك، إذا كان من المقرر أن تُولّد أطراف خبيثة حصصًا، فقد يكون من المهم التحقق من صحتها. في نظام تبادل الأسرار القابل للتحقق، يُصاحب توزيع السر التزاماتٌ بالحصص الفردية. لا تكشف هذه الالتزامات أي شيء يُمكن أن يُفيد مجموعة خبيثة، لكن الحصص تسمح لكل طرف بالتحقق من صحة حصته. [ 12 ]

حماية

تختلف التعريفات الرسمية لأنظمة الالتزام اختلافًا كبيرًا في الترميز والأسلوب. يتمثل أحد هذه الأساليب في ما إذا كان نظام الالتزام يوفر أمانًا تامًا أو حسابيًا فيما يتعلق بخصائص الإخفاء أو الربط. ويتمثل أسلوب آخر في ما إذا كان الالتزام تفاعليًا، أي ما إذا كان من الممكن اعتبار كل من مرحلة الالتزام ومرحلة الكشف منفذتين بواسطة بروتوكول تشفير، أو ما إذا كانتا غير تفاعليتين، وتتكونان من خوارزميتين: الالتزام والتحقق من الكشف . في الحالة الأخيرة، يمكن غالبًا اعتبار التحقق من الكشف نسخةً غير عشوائية من الالتزام ، حيث تشكل العشوائية المستخدمة في الالتزام معلومات الفتح.

إذا تم حساب الالتزام C لقيمة x على النحو التالي C:=Commit(x,open) حيث open هي العشوائية المستخدمة لحساب الالتزام، فإن CheckReveal (C,x,open) يختزل ببساطة إلى التحقق من المعادلة C=Commit (x,open) .

باستخدام هذه الرموز وبعض المعرفة بالدوال الرياضية ونظرية الاحتمالات، نُصيغ صيغًا رسمية لخصائص الربط والإخفاء في الالتزامات. أهم تركيبتين لهذه الخصائص هما: مخططات الالتزام التي توفر ربطًا تامًا وإخفاءً حسابيًا، ومخططات الالتزام التي توفر ربطًا حسابيًا وإخفاءً تامًا. تجدر الإشارة إلى أنه لا يمكن لأي مخطط التزام أن يكون في الوقت نفسه رابطًا تامًا ومخفيًا تمامًا؛ إذ يمكن لخصم ذي قدرة حسابية غير محدودة أن يُنشئ ببساطة دالة Commit(x,open) لكل قيمة من قيمتي x و open حتى يجد زوجًا يُخرج القيمة C ، وفي مخطط الربط التام، يُحدد هذا الزوج قيمة x بشكل فريد .

الربط الحسابي

لنفترض أن الفتح يتم اختياره من مجموعة الأحجام2ك{\displaystyle 2^{k}}أي أنه يمكن تمثيله كسلسلة مكونة من k بت، ولتكن يقترفك{\displaystyle {\text{Commit}}_{k}}ليكن مخطط الالتزام المقابل. وبما أن حجم k يحدد أمان مخطط الالتزام، فإنه يُطلق عليه اسم معامل الأمان .

ثم بالنسبة لجميع الخوارزميات ذات الوقت متعدد الحدود الاحتمالي غير المنتظم التي تُخرجx،x′{\displaystyle x,x'}وoصهـن،oصهـن′{\displaystyle open,open'}مع زيادة الطول k ، فإن احتمال أنx≠x′{\displaystyle x\neq x'}ويقترفك(x،oصهـن)=يقترفك(x′،oصهـن′){\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}هي دالة مهملة في k .

هذا شكل من أشكال التحليل التقاربي . من الممكن أيضًا صياغة نفس المتطلب باستخدام أمان ملموس : مخطط الالتزام هو(ت،ϵ){\displaystyle (t,\epsilon )}آمن، إذا كان ذلك لجميع الخوارزميات التي تعمل في الوقت t وتُخرجx،x′،oصهـن،oصهـن′{\displaystyle x,x',open,open'}احتمال أنx≠x′{\displaystyle x\neq x'}ويقترف(x،oصهـن)=يقترف(x′،oصهـن′){\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}هو على الأكثرϵ{\displaystyle \epsilon }.

إخفاء مثالي، إحصائي، وحسابي

يتركيوك{\displaystyle U_{k}}ليكن التوزيع المنتظم على2ك{\displaystyle 2^{k}}القيم الافتتاحية لمعامل الأمان k . يكون مخطط الالتزام مثاليًا أو إحصائيًا أو حسابيًا على التوالي، إذا كان لكلx≠x′{\displaystyle x\neq x'}مجموعات الاحتمالات{يقترفك(x،يوك)}ك∈شمال{\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}و{يقترفك(x′،يوك)}ك∈شمال{\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}متساوية، أو متقاربة إحصائياً ، أو غير قابلة للتمييز حسابياً .

استحالة وجود مخططات التزام قابلة للتكوين عالميًا

يستحيل تطبيق مخططات الالتزام في إطار قابلية التركيب الشاملة (UC). والسبب هو أن التزام UC يجب أن يكون قابلاً للاستخراج ، كما أوضح كانيتي وفيشلين [ 13 ] وسيتم شرحه أدناه.

تعمل وظيفة الالتزام المثالية، المشار إليها هنا بالرمز F ، تقريبًا على النحو التالي. يرسل الملتزم C القيمة m إلى F ، التي تخزنها وترسل "إيصالًا" إلى المستلم R. لاحقًا ، يرسل C "فتحًا" إلى F ، التي ترسل m إلى R.

لنفترض الآن أن لدينا بروتوكولًا π يُحقق هذه الوظيفة. ولنفترض أن المُلتزم C قد تعطل. في إطار عمل UC، يعني هذا أساسًا أن C أصبح الآن تحت سيطرة البيئة، التي تحاول التمييز بين تنفيذ البروتوكول والعملية المثالية. لنفترض بيئة تختار رسالة m ثم تُخبر C بالتصرف وفقًا لما هو مُحدد في π ، كما لو أنه قد التزم بـ m . لاحظ هنا أنه لتحقيق F ، يجب على المُستقبِل، بعد تلقي الالتزام، إخراج رسالة "receipt". بعد أن ترى البيئة هذه الرسالة، تُخبر C بفتح الالتزام.

لا يكون البروتوكول آمنًا إلا إذا كان هذا السيناريو مطابقًا تمامًا للحالة المثالية، حيث تتفاعل الوظيفة مع محاكي S. في هذه الحالة، يتحكم S في C. تحديدًا، عندما يُخرج R قيمة "receipt"، يجب على F أن يفعل الشيء نفسه. والطريقة الوحيدة لتحقيق ذلك هي أن يُخبر S برنامج C بإرسال قيمة إلى F. مع ذلك، تجدر الإشارة إلى أنه في هذه المرحلة، لا يكون m معروفًا لـ S. لذا، عند فتح الالتزام أثناء تنفيذ البروتوكول، من غير المرجح أن يفتح F لـ m ، إلا إذا تمكن S من استخراج m من الرسائل التي تلقاها من البيئة قبل أن يُخرج R قيمة الإيصال.

مع ذلك، لا يمكن إخفاء بروتوكول قابل للاستخراج بهذا المعنى إحصائيًا. لنفترض وجود محاكي S. الآن، لنفترض بيئةً تُفسد R بدلًا من C. بالإضافة إلى ذلك ، تُشغّل هذه البيئة نسخةً من S. تُغذّى الرسائل الواردة من C إلى S ، وتُعاد توجيه الردود من S إلى C.

في البداية، تُخبر البيئة C بالالتزام برسالة m . في مرحلة ما من التفاعل، ستلتزم S بقيمة m′ . تُسلّم هذه الرسالة إلى R ، الذي يُخرج m′ . لاحظ أنه بافتراضنا، لدينا m′ = m باحتمالية عالية . الآن، في العملية المثالية، يجب على المحاكي أن يُخرج m . لكن هذا مستحيل، لأنه في هذه المرحلة لم يتم فتح الالتزام بعد، لذا فإن الرسالة الوحيدة التي يمكن أن يكون R قد استلمها في العملية المثالية هي رسالة "استلام". وبالتالي، لدينا تناقض.

بناء

يمكن أن يكون مخطط الالتزام إما ملزمًا تمامًا (يستحيل على أليس تغيير التزامها بعد إبرامه، حتى لو كانت لديها موارد حاسوبية غير محدودة)؛ أو مُخفيًا تمامًا (يستحيل على بوب معرفة الالتزام دون أن تكشفه أليس، حتى لو كانت لديه موارد حاسوبية غير محدودة)؛ أو مُصاغًا كمخطط التزام يعتمد على الحالة، والذي يكون إما مُخفيًا أو مُلزمًا اعتمادًا على حل مشكلة أخرى. [ 14 ] [ 15 ] لا يمكن أن يكون مخطط الالتزام مُخفيًا تمامًا وملزمًا تمامًا في الوقت نفسه.

الالتزام بالبت في نموذج أوراكل العشوائي

تُعدّ مخططات الالتزام بالبتات سهلة الإنشاء في نموذج أوراكل العشوائي . بافتراض دالة تجزئة H ذات مخرجات 3k بت ، ولتثبيت الرسالة m المكونة من k بت ، تُنشئ أليس سلسلة عشوائية R مكونة من k بت وترسلها إلى بوب H( R || m ). احتمال وجود أي R′ و m′ حيث m′ ≠ m بحيث يكون H( R′ || m′ ) = H( R || m ) هو ≈ 2 − k ، ولكن لاختبار أي تخمين للرسالة m، سيحتاج بوب إلى إجراء 2k (للتخمين الخاطئ) أو 2k - 1 (كمعدل للتخمين الصحيح) استعلامًا إلى أوراكل العشوائي. [ 16 ] نلاحظ أن المخططات السابقة القائمة على دوال التجزئة، يمكن اعتبارها في جوهرها مخططات قائمة على تبسيط هذه الدوال كنموذج أوراكل عشوائي.

الالتزام بالبتات من أي تبديل أحادي الاتجاه

يمكن إنشاء مخطط التزام بت من أي دالة أحادية الاتجاه قابلة للحقن . يعتمد المخطط على حقيقة أنه يمكن تعديل كل دالة أحادية الاتجاه (عبر نظرية غولدريتش-ليفين ) لتمتلك مسندًا حسابيًا أساسيًا (مع الاحتفاظ بخاصية الحقن).

لتكن f دالة أحادية الاتجاه أحادية التباين، و h دالة منطقية أساسية. عندئذٍ، لكي تلتزم أليس بالبت b، تختار مدخلاً عشوائياً x وترسل الثلاثية

(ح،و(x)،ب⊕ح(x)){\displaystyle (h,f(x),b\oplus h(x))}

إلى بوب، حيث⊕{\displaystyle \oplus }يرمز إلى عملية XOR، أي الجمع الثنائي بتردد 2. لإلغاء الالتزام، ترسل أليس ببساطة x إلى بوب. يتحقق بوب من خلال حساب f ( x ) ومقارنتها بالقيمة الملتزم بها. هذه الطريقة تخفي البيانات لأن بوب يحتاج لاستعادة b إلى استعادة h ( x ). بما أن h دالة حسابية معقدة، فإن استعادة h ( x ) من f ( x ) باحتمالية أكبر من النصف تُعادل صعوبة عكس f . ينتج الربط التام من كون f دالة أحادية، وبالتالي فإن f ( x ) لها صورة عكسية واحدة فقط.

التزام البت من مولد شبه عشوائي

لاحظ أنه بما أننا لا نعرف كيفية إنشاء تبديل أحادي الاتجاه من أي دالة أحادية الاتجاه، فإن هذا القسم يقلل من قوة الافتراض التشفيري اللازم لإنشاء بروتوكول التزام البت.

في عام 1991، أوضح موني ناور كيفية إنشاء مخطط التزام بت من مولد أرقام شبه عشوائية آمن تشفيرياً . [ 17 ] ويكون البناء كما يلي: إذا كان G مولد أرقام شبه عشوائية بحيث يأخذ G من n بت إلى 3n بت ، فإذا أرادت أليس الالتزام بالبت b :

  • يختار بوب متجهًا عشوائيًا مكونًا من 3 بتات R ويرسل R إلى أليس.
  • تقوم أليس باختيار متجه عشوائي مكون من n بت Y وحساب المتجه المكون من 3 n بت G ( Y ).
  • إذا كانت قيمة b تساوي 1، فإن أليس ترسل G ( Y ) إلى بوب، وإلا فإنها ترسل عملية XOR الثنائية لـ G ( Y ) و R إلى بوب.

لإلغاء الالتزام، ترسل أليس Y إلى بوب، الذي يمكنه بعد ذلك التحقق مما إذا كان قد استلم في البداية G ( Y ) أو G ( Y ).⊕{\displaystyle \oplus }ر .

هذا المخطط مُلزم إحصائيًا، ما يعني أنه حتى لو كانت أليس غير محدودة حسابيًا، فلا يمكنها الغش باحتمالية أكبر من 2 − n . لكي تغش أليس، ستحتاج إلى إيجاد Y' بحيث يكون G ( Y' ) = G ( Y ).⊕{\displaystyle \oplus }إذا تمكنت من إيجاد قيمة R ، فبإمكانها التراجع عن قرارها بإرسال الحقيقة و Y ، أو إرسال الإجابة المعاكسة و Y' . مع ذلك، فإن G ( Y ) و G ( Y' ) لا تستطيعان إنتاج سوى 2n قيمة ممكنة لكل منهما (أي 2 ^ 2n )، بينما يتم اختيار R من بين 2 ^3n قيمة . ولأنها لا تختار R ، فإن احتمال وجود قيمة Y' تحقق المعادلة المطلوبة للغش هو 2 ^2n / 2 ^3n = 2 - n .

تنبع خاصية الإخفاء من اختزال قياسي، فإذا استطاع بوب أن يحدد ما إذا كانت أليس قد التزمت بصفر أو واحد، فإنه يستطيع أيضًا التمييز بين مخرجات مولد الأرقام العشوائية الزائفة G والأرقام العشوائية الحقيقية، وهو ما يتناقض مع الأمان التشفيري لـ G.

مخطط ربط مثالي قائم على مشكلة اللوغاريتم المنفصل وما بعدها

تختار أليس مجموعة من الرتبة الأولية p ، مع مولد g .

تختار أليس عشوائيًا قيمة سرية x من 0 إلى p − 1 لتلتزم بها، ثم تحسب c = g x وتنشرها . تنص مسألة اللوغاريتم المتقطع على أنه من غير الممكن حساب x انطلاقًا من c ، لذا، وبناءً على هذا الافتراض، لا يستطيع بوب حساب x . من جهة أخرى، لا تستطيع أليس حساب x ′ <> x بحيث يكون g x ′ = c ، وبالتالي فإن الخطة ملزمة.  

لا يُعدّ هذا المخطط مُخفيًا تمامًا، إذ يُمكن لأي شخص اكتشاف الالتزام إذا تمكّن من حلّ مسألة اللوغاريتم المنفصل . في الواقع، لا يُخفي هذا المخطط شيئًا على الإطلاق مقارنةً بلعبة الإخفاء القياسية، حيث لا يستطيع المُهاجم تخمين أيّ من الرسالتين اللتين اختارهما تمّ الالتزام بها - على غرار لعبة IND-CPA . إحدى نتائج ذلك هي أنه إذا كان نطاق القيم المُحتملة لـ x صغيرًا، فسيتمكّن المُهاجم ببساطة من تجربة جميعها ولن يكون الالتزام مُخفيًا.

يُعدّ مثالٌ أفضل على مخطط التزام مُلزم تمامًا هو ذلك الذي يكون فيه الالتزام هو تشفير x باستخدام نظام تشفير بمفتاح عام آمن دلاليًا وكامل تمامًا، ويكون فك الالتزام هو سلسلة البتات العشوائية المستخدمة لتشفير x . ومن الأمثلة على مخطط التزام يُخفي المعلومات نظريًا مخطط التزام بيدرسن [ 18 ] ، وهو مُلزم حسابيًا بافتراض اللوغاريتم المنفصل [ 19 ] . بالإضافة إلى المخطط المذكور أعلاه، يستخدم هذا المخطط مولدًا آخر h من المجموعة الأولية وعددًا عشوائيًا r . يتم تعيين الالتزام.ج=زxحر{\displaystyle c=g^{x}h^{r}}[ 20 ]​

ترتبط هذه البنى ارتباطًا وثيقًا بالخصائص الجبرية للمجموعات الأساسية وتستند إليها، وقد بدا المفهوم في الأصل مرتبطًا ارتباطًا وثيقًا بالجبر. ومع ذلك، فقد ثبت أنه من الممكن بناء مخططات التزام ملزمة إحصائيًا على افتراضات عامة غير منظمة، وذلك من خلال مفهوم التجزئة التفاعلية للالتزامات من افتراضات التعقيد العامة (وتحديدًا، استنادًا إلى أي تبديل أحادي الاتجاه) كما في [ 21 ] .

مخطط التزام يخفي تمامًا قائم على RSA

أليس تختارشمال{\displaystyle N}بحيثشمال=ص⋅q{\displaystyle N=p\cdot q}، أينص{\displaystyle p}وq{\displaystyle q}هي أعداد أولية سرية كبيرة. بالإضافة إلى ذلك، فهي تختار عددًا أوليًاهـ{\displaystyle e}بحيثهـ>شمال2{\displaystyle e>N^{2}}وزجد(هـ،ϕ(شمال2))=1{\displaystyle gcd(e,\phi (N^{2}))=1}ثم تقوم أليس بحساب رقم عامزم{\displaystyle g_{m}}كعنصر من عناصر النظام الأقصى فيZشمال2*{\displaystyle \mathbb {Z} _{N^{2}}^{*}}[ 22 ] وأخيرًا ، تلتزم أليس بسرهام{\displaystyle m}عن طريق توليد رقم عشوائي أولاًر{\displaystyle r}منZشمال2*{\displaystyle \mathbb {Z} _{N^{2}}^{*}}ثم عن طريق الحسابج=مهـزمر{\displaystyle c=m^{e}g_{m}^{r}}.

يعتمد أمان الالتزام المذكور أعلاه على صعوبة مشكلة RSA، ويتميز بإخفاء مثالي وربط حسابي. [ 23 ]

الخصائص المتماثلة الجمعية والضربية للالتزامات

يُقدّم مخطط التزام بيدرسن خاصيةً متماثلةً مثيرةً للاهتمام تسمح بإجراء عملية الجمع بين التزامين. وبشكلٍ أكثر تحديدًا، بالنظر إلى رسالتينم1{\displaystyle m_{1}}وم2{\displaystyle m_{2}}والعشوائيةر1{\displaystyle r_{1}}ور2{\displaystyle r_{2}}وبالتالي، من الممكن إنشاء التزام جديد بحيث:ج(م1،ر1)⋅ج(م2،ر2)=ج(م1+م2،ر1+ر2){\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}رسميًا:

ج(م1،ر1)⋅ج(م2،ر2)=زم1حر1⋅زم2حر2=زم1+م2حر1+ر2=ج(م1+م2،ر1+ر2){\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}

لفتح التزام بيدرسن المذكور أعلاه لرسالة جديدةم1+م2{\displaystyle m_{1}+m_{2}}العشوائيةر1{\displaystyle r_{1}}ور2{\displaystyle r_{2}}يجب إضافته.

وبالمثل، فإن الالتزام القائم على RSA المذكور أعلاه يتمتع بخاصية التماثل فيما يتعلق بعملية الضرب. بالنظر إلى رسالتينم1{\displaystyle m_{1}}وم2{\displaystyle m_{2}}مع العشوائيةر1{\displaystyle r_{1}}ور2{\displaystyle r_{2}}وبالتالي، يمكن حساب ما يلي:ج(م1،ر1)⋅ج(م2،ر2)=ج(م1⋅م2،ر1+ر2){\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}رسميًا: ج(م1،ر1)⋅ج(م2،ر2)=م1هـزمر1⋅م2هـزمر2=(م1⋅م2)هـزمر1+ر2=ج(م1⋅م2،ر1+ر2){\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}.

لفتح الالتزام أعلاه لرسالة جديدةم1⋅م2{\displaystyle m_{1}\cdot m_{2}}العشوائيةر1{\displaystyle r_{1}}ور2{\displaystyle r_{2}}يجب إضافته. يتم توزيع هذا الالتزام المُنشأ حديثًا بشكل مشابه للالتزام الجديد بـم1⋅م2{\displaystyle m_{1}\cdot m_{2}}.

كشف جزئي

تسمح بعض خطط الالتزام بتقديم دليل على جزء فقط من القيمة الملتزم بها. في هذه الخطط، تكون القيمة السريةX{\displaystyle X}هو متجه يتكون من العديد من القيم القابلة للفصل بشكل فردي.

X=(x1،x2،...،xن){\displaystyle X=(x_{1},x_{2},...,x_{n})}

الالتزامج{\displaystyle C}يتم حسابها منX{\displaystyle X}في مرحلة الالتزام. عادةً، في مرحلة الكشف، يكشف المُثبت عن كل شيءX{\displaystyle X}وبعض بيانات الإثبات الإضافية (مثلR{\displaystyle R}في عملية الالتزام البسيط بالبتات ). بدلاً من ذلك، يستطيع المُثبت الكشف عن أي قيمة واحدة منX{\displaystyle X}متجه، وإنشاء دليل فعال على أنه أصليأنا{\displaystyle i}العنصر رقم 1 من المتجه الأصلي الذي أنشأ الالتزامج{\displaystyle C}لا يتطلب البرهان أي قيم لـX{\displaystyle X}بخلافxأنا{\displaystyle x_{i}}سيتم الكشف عنها، ومن المستحيل إنشاء براهين صحيحة تكشف عن قيم مختلفة لأي منxأنا{\displaystyle x_{i}}[ 24 ]​

التجزئة المتجهة

التجزئة المتجهة هي خوارزمية بسيطة للكشف الجزئي عن التزام المتجهات تعتمد على التزام البتات. القيمم1،م2،...من{\displaystyle m_{1},m_{2},...m_{n}}يتم اختيارها عشوائياً. يتم إنشاء الالتزامات الفردية عن طريق التجزئة.y1=ح(x1||م1)،y2=ح(x2||م2)،...{\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}يتم حساب الالتزام الإجمالي على النحو التالي:

ج=ح(y1||y2||...||yن){\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}

لإثبات أحد عناصر المتجهX{\displaystyle X}يكشف المُثبت عن القيم

(أنا،y1،y2،...،yأنا-1،xأنا،مأنا،yأنا+1،...،yن){\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}

يستطيع جهاز التحقق إجراء الحساباتyأنا{\displaystyle y_{i}}منxأنا{\displaystyle x_{i}}ومأنا{\displaystyle m_{i}}ثم يصبح قادراً على التحقق من أن تجزئة جميعy{\displaystyle y}القيم هي الالتزامج{\displaystyle C}لسوء الحظ، الدليل هويا(ن){\displaystyle O(n)}من حيث الحجم ووقت التحقق. أو بدلاً من ذلك، إذاج{\displaystyle C}هي مجموعة الكلy{\displaystyle y}إذا كانت القيم هي الأساس، فإن الالتزام هويا(ن){\displaystyle O(n)}من حيث الحجم، والدليل هويا(1){\displaystyle O(1)}من حيث الحجم ووقت التحقق. في كلتا الحالتين، يتناسب الالتزام أو الإثبات معيا(ن){\displaystyle O(n)}وهذا ليس الأمثل.

شجرة ميركل

من الأمثلة الشائعة على مخطط الكشف الجزئي العملي شجرة ميركل ، حيث يتم إنشاء شجرة تجزئة ثنائية من عناصرX{\displaystyle X}يُنشئ هذا المخطط التزامات هييا(1){\displaystyle O(1)}من حيث الحجم، وإثباتات ذلكيا(سجل2⁡ن){\displaystyle O(\log _{2}{n})}من حيث الحجم ووقت التحقق. تجزئة الجذر للشجرة هي الالتزامج{\displaystyle C}لإثبات أن ما تم الكشف عنهxأنا{\displaystyle x_{i}}هو جزء من الشجرة الأصلية، فقطسجل2⁡ن{\displaystyle \log _{2}{n}}يجب الكشف عن قيم التجزئة من الشجرة، قيمة واحدة من كل مستوى، كدليل. يستطيع المُدقِّق تتبُّع المسار من عقدة الورقة المُطالب بها وصولًا إلى الجذر، مع حساب تجزئة العقد الشقيقة في كل مستوى، والوصول في النهاية إلى قيمة عقدة الجذر التي يجب أن تساويج{\displaystyle C}[ 25 ]​

التزام KZG

يستخدم التزام كيت-زافيروتشا-غولدبيرغ (KZG) التشفير القائم على الاقتران لبناء مخطط كشف جزئي معيا(1){\displaystyle O(1)}أحجام الالتزامات، وأحجام الإثباتات، ووقت التحقق من الإثباتات. بعبارة أخرى، كمان{\displaystyle n}عدد القيم فيX{\displaystyle X}ومع زيادة حجم الالتزامات والإثباتات، لا تزداد حجماً، ولا تتطلب الإثباتات أي جهد إضافي للتحقق منها.

يتطلب التزام KZG مجموعة محددة مسبقًا من المعلمات لإنشاء اقتران ، وعنصر باب خلفي موثوق. على سبيل المثال، يمكن استخدام اقتران تيت . افترض أنجي1،جي2{\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}هي المجموعات المضافة، وجيتي{\displaystyle \mathbb {G} _{T}}هي المجموعة الضربية للزوج. بعبارة أخرى، الزوج هو الخريطةهـ:جي1×جي2→جيتي{\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}. يتركت∈Fص{\displaystyle t\in \mathbb {F} _{p}}كن عنصر الباب المصيدة (إذاص{\displaystyle p}هو الترتيب الأساسي لـجي1{\displaystyle \mathbb {G} _{1}}وجي2{\displaystyle \mathbb {G} _{2}})، ودعجي{\displaystyle G}وح{\displaystyle H}كن مولدًا لـجي1{\displaystyle \mathbb {G} _{1}}وجي2{\displaystyle \mathbb {G} _{2}}على التوالي. وكجزء من إعداد المعلمات، نفترض أنجي⋅تأنا{\displaystyle G\cdot t^{i}}وح⋅تأنا{\displaystyle H\cdot t^{i}}هي قيم معروفة ومشتركة لعدد كبير من القيم الصحيحة الموجبة لـأنا{\displaystyle i}، بينما قيمة الباب الخلفيت{\displaystyle t}يتم التخلص منها ولا يعرفها أحد.

يقترف

تُعيد آلية الالتزام KZG صياغة متجه القيم المراد الالتزام بها على شكل متعدد الحدود. أولاً، نحسب متعدد الحدود بحيثص(أنا)=xأنا{\displaystyle p(i)=x_{i}}لجميع قيمxأنا{\displaystyle x_{i}}في متجهنا. يسمح لنا استيفاء لاغرانج بحساب تلك متعددة الحدود

ص(x)=∑أنا=0ن-1xأنا∏0≤ج<ن،ج≠أناx-جأنا-ج{\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}

بموجب هذه الصيغة، تقوم متعددة الحدود الآن بترميز المتجه، حيثص(0)=x0،ص(1)=x1،...{\displaystyle p(0)=x_{0},p(1)=x_{1},...}. يتركص0،ص1،...،صن-1{\displaystyle p_{0},p_{1},...,p_{n-1}}لتكن معاملاتص{\displaystyle p}بحيثص(x)=∑أنا=0ن-1صأناxأنا{\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}يتم حساب الالتزام على النحو التالي:

ج=∑أنا=0ن-1صأناجيتأنا{\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}

يتم حساب ذلك ببساطة كحاصل ضرب نقطي بين القيم المحددة مسبقًاجي⋅تأنا{\displaystyle G\cdot t^{i}}ومعاملات كثير الحدودصأنا{\displaystyle p_{i}}. منذجي1{\displaystyle \mathbb {G} _{1}}هي مجموعة جمعية ذات خاصية التجميع والتبديل،ج{\displaystyle C}يساوي ببساطةجي⋅ص(ت){\displaystyle G\cdot p(t)}، لأن جميع عمليات الجمع والضرب معجي{\displaystyle G}يمكن توزيعها خارج نطاق التقييم. نظرًا لقيمة الباب الخلفيت{\displaystyle t}غير معروف، والالتزامج{\displaystyle C}هي في الأساس متعددة الحدود التي يتم تقييمها عند رقم غير معروف لأحد، مع إخفاء النتيجة في عنصر مبهم منجي1{\displaystyle \mathbb {G} _{1}}.

يكشف

يجب أن يثبت برهان KZG أن البيانات المُكتشفة هي القيمة الأصلية لـxأنا{\displaystyle x_{i}}متىج{\displaystyle C}تم حسابها. لنفترضy=xأنا{\displaystyle y=x_{i}}، القيمة المُكتشفة التي يجب علينا إثباتها. بما أن متجهxأنا{\displaystyle x_{i}}تمت إعادة صياغتها في شكل متعددة حدود، ونحن بحاجة حقًا إلى إثبات أن متعددة الحدودص{\displaystyle p}، عند تقييمها فيأنا{\displaystyle i}، يأخذ القيمةy{\displaystyle y}ببساطة، كل ما نحتاجه هو إثبات ذلك.ص(أنا)=y{\displaystyle p(i)=y}سنفعل ذلك من خلال إثبات أن طرحy{\displaystyle y}منص{\displaystyle p}ينتج جذرًا عندأنا{\displaystyle i}عرّف متعددة الحدودq{\displaystyle q}مثل

q(x)=ص(x)-yx-أنا{\displaystyle q(x)={\frac {p(x)-y}{x-i}}}

هذه المعادلة متعددة الحدود هي بحد ذاتها دليل على أنص(أنا)=y{\displaystyle p(i)=y}لأنه إذاq{\displaystyle q}موجود، إذنص(x)-y{\displaystyle p(x)-y}يقبل القسمة علىx-أنا{\displaystyle x-i}مما يعني أن لها جذراً فيأنا{\displaystyle i}، لذاص(أنا)-y=0{\displaystyle p(i)-y=0}(أو بعبارة أخرى،ص(أنا)=y{\displaystyle p(i)=y}سيُثبت برهان KZG أنq{\displaystyle q}موجود وله هذه الخاصية.

يقوم برنامج إثبات النتائج بالحسابq{\displaystyle q}من خلال قسمة كثير الحدود المذكورة أعلاه، ثم يتم حساب قيمة إثبات KZGπ{\displaystyle \pi }

π=∑أنا=0ن-1qأناجيتأنا{\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}

هذا يساويجي⋅q(ت){\displaystyle G\cdot q(t)}كما سبق. بعبارة أخرى، قيمة البرهان هي متعددة الحدودq{\displaystyle q}تم تقييمها مرة أخرى عند قيمة الباب الخلفيت{\displaystyle t}، مخفية في المولدجي{\displaystyle G}لجي1{\displaystyle \mathbb {G} _{1}}.

لا يمكن إجراء هذه العملية الحسابية إلا إذا كانت كثيرات الحدود المذكورة أعلاه قابلة للقسمة بالتساوي، لأنه في هذه الحالة يكون ناتج القسمةq{\displaystyle q}هي دالة متعددة الحدود، وليست دالة كسرية . ونظرًا لبنية البوابة، لا يمكن حساب قيمة دالة كسرية عند قيمة البوابة، وإنما يمكن فقط حساب قيمة متعددة الحدود باستخدام التراكيب الخطية للثوابت المعروفة المحسوبة مسبقًا.جي⋅تأنا{\displaystyle G\cdot t^{i}}ولهذا السبب يستحيل إثبات قيمة غير صحيحة لـxأنا{\displaystyle x_{i}}.

يؤكد

وللتحقق من صحة البرهان، يتم استخدام الخريطة الثنائية الخطية للاقتران لإظهار أن قيمة البرهانπ{\displaystyle \pi }يلخص متعدد الحدود الحقيقيq{\displaystyle q}وهذا يدل على الخاصية المطلوبة، وهي أنص(x)-y{\displaystyle p(x)-y}تم تقسيمه بالتساوي علىx-أنا{\displaystyle x-i}تتحقق عملية التحقق من المساواة

هـ(π،ح⋅ت-ح⋅أنا) =؟ هـ(ج-جي⋅y،ح){\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}

أينهـ{\displaystyle e}هي دالة التحويل الثنائي الخطي كما هو موضح أعلاه.ح⋅ت{\displaystyle H\cdot t}هو ثابت محسوب مسبقًا،ح⋅أنا{\displaystyle H\cdot i}يتم حسابها بناءً علىأنا{\displaystyle i}.

عن طريق إعادة كتابة الحساب في مجموعة الاقترانجيتي{\displaystyle \mathbb {G} _{T}}، بالاستبدال فيπ=q(ت)⋅جي{\displaystyle \pi =q(t)\cdot G}وج=ص(ت)⋅جي{\displaystyle C=p(t)\cdot G}، والسماحτ(x)=هـ(جي،ح)x{\displaystyle \tau (x)=e(G,H)^{x}}إذا كانت دالة مساعدة للرفع إلى مجموعة الاقتران، فإن التحقق من الإثبات يكون أكثر وضوحًا.

هـ(π،ح⋅ت-ح⋅أنا)=هـ(ج-جي⋅y،ح){\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}
هـ(جي⋅q(ت)،ح⋅ت-ح⋅أنا)=هـ(جي⋅ص(ت)-جي⋅y،ح){\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}
هـ(جي⋅q(ت)،ح⋅(ت-أنا))=هـ(جي⋅(ص(ت)-y)،ح){\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}
هـ(جي،ح)q(ت)⋅(ت-أنا)=هـ(جي،ح)ص(ت)-y{\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}
τ(q(ت)⋅(ت-أنا))=τ(ص(ت)-y){\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}

بافتراض صحة بناء الخريطة الثنائية الخطية، فإن هذا يوضح أنq(x)(x-أنا)=ص(x)-y{\displaystyle q(x)(x-i)=p(x)-y}، دون أن يعلم المدقق ما هوص{\displaystyle p}أوq{\displaystyle q}يمكن للمُدقِّق أن يطمئن إلى ذلك لأنه إذاτ(q(ت)⋅(ت-أنا))=τ(ص(ت)-y){\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}ثم تُقيّم كثيرات الحدود إلى نفس الناتج عند قيمة الباب الخلفيx=ت{\displaystyle x=t}يُظهر هذا أن كثيرات الحدود متطابقة، لأنه إذا تم بناء المعاملات بشكل صحيح، فإن قيمة الباب الخلفي غير معروفة لأحد، مما يعني أن هندسة كثيرة حدود للحصول على قيمة محددة عند الباب الخلفي أمر مستحيل (وفقًا لفرضية شوارتز-زيبيل ).q(x)(x-أنا)=ص(x)-y{\displaystyle q(x)(x-i)=p(x)-y}تم التحقق من صحة ذلك، إذنq{\displaystyle q}تم التحقق من وجوده، لذلكص(x)-y{\displaystyle p(x)-y}يجب أن يكون متعدد الحدود قابلاً للقسمة على(x-أنا){\displaystyle (x-i)}، لذاص(أنا)-y=0{\displaystyle p(i)-y=0}وذلك بسبب نظرية العامل . وهذا يثبت أنأنا{\displaystyle i}يجب أن تكون القيمة th للمتجه الملتزم مساوية لـy{\displaystyle y}، لأن هذا هو ناتج تقييم متعددة الحدود الملتزمة عندأنا{\displaystyle i}.

لماذا يتم استخدام اقتران الخرائط الثنائية الخطية

تكمن فائدة اقتران الخرائط الثنائية الخطية في السماح بضربq(x){\displaystyle q(x)}بواسطةx-أنا{\displaystyle x-i}أن يحدث ذلك بأمان. تكمن هذه القيم حقًا فيجي1{\displaystyle \mathbb {G} _{1}}حيث يُفترض أن عملية القسمة صعبة حسابيًا. على سبيل المثال،جي1{\displaystyle \mathbb {G} _{1}}قد يكون منحنىً إهليلجيًا على حقل منتهٍ، كما هو شائع في تشفير المنحنيات الإهليلجية . عندئذٍ، يُطلق على فرضية القسمة اسم مسألة اللوغاريتم المنفصل للمنحنى الإهليلجي ، وهذه الفرضية هي التي تمنع حساب قيمة الباب الخلفي، مما يجعلها أيضًا أساسًا لالتزامات KZG. في هذه الحالة، نريد التحقق مما إذاq(x)(x-أنا)=ص(x)-y{\displaystyle q(x)(x-i)=p(x)-y}لا يمكن القيام بذلك بدون اقتران، لأن القيم على منحنىجي⋅q(x){\displaystyle G\cdot q(x)}وجي⋅(x-أنا){\displaystyle G\cdot (x-i)}لا يمكننا الحسابجي⋅(q(x)(x-أنا)){\displaystyle G\cdot (q(x)(x-i))}سيؤدي ذلك إلى انتهاك فرضية ديفي-هيلمان الحسابية ، وهي فرضية أساسية في تشفير المنحنيات الإهليلجية . لذا، نستخدم بدلاً من ذلك عملية الاقتران لتجنب هذه المشكلة.q(x){\displaystyle q(x)}لا يزال مضروبًا فيجي{\displaystyle G}للحصول علىجي⋅q(x){\displaystyle G\cdot q(x)}لكن الجانب الآخر من عملية الضرب يتم في المجموعة المزدوجةجي2{\displaystyle \mathbb {G} _{2}}، لذا،ح⋅(ت-أنا){\displaystyle H\cdot (t-i)}نقوم بالحسابهـ(جي⋅q(ت)،ح⋅(ت-أنا)){\displaystyle e(G\cdot q(t),H\cdot (t-i))}، وهو ما يساوي، بسبب خاصية الخطية الثنائية للدالةهـ(جي،ح)q(ت)⋅(ت-أنا){\displaystyle e(G,H)^{q(t)\cdot (t-i)}}في مجموعة المخرجات هذهجيتي{\displaystyle \mathbb {G} _{T}}لا تزال لدينا مشكلة اللوغاريتم المتقطع ، لذلك على الرغم من أننا نعرف تلك القيمة وهـ(جي،ح){\displaystyle e(G,H)}لا يمكننا استخراج الأسq(ت)⋅(ت-أنا){\displaystyle q(t)\cdot (t-i)}مما يمنع أي تناقض مع اللوغاريتم المتقطع سابقًا. يمكن مقارنة هذه القيمة بـهـ(جي⋅(ص(ت)-y)،ح)=هـ(جي،ح)ص(ت)-y{\displaystyle e(G\cdot (p(t)-y),H)=e(G,H)^{p(t)-y}}مع ذلك، وإذاهـ(جي،ح)q(ت)⋅(ت-أنا)=هـ(جي،ح)ص(ت)-y{\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}نستطيع أن نستنتج أنq(ت)⋅(ت-أنا)=ص(ت)-y{\displaystyle q(t)\cdot (t-i)=p(t)-y}, without ever knowing what the actual value of t{\displaystyle t} is, let alone q(t)(t−i){\displaystyle q(t)(t-i)}.

Additionally, a KZG commitment can be extended to prove the values of any arbitrary k{\displaystyle k} values of X{\displaystyle X} (not just one value), with the proof size remaining O(1){\displaystyle O(1)}, but the proof verification time scales with O(k){\displaystyle O(k)}. The proof is the same, but instead of subtracting a constant y{\displaystyle y}, we subtract a polynomial that causes multiple roots, at all the locations we want to prove, and instead of dividing by x−i{\displaystyle x-i} we divide by ∏ix−i{\textstyle \prod _{i}x-i} for those same locations.[26]

Quantum bit commitment

It is an interesting question in quantum cryptography if unconditionally secure bit commitment protocols exist on the quantum level, that is, protocols which are (at least asymptotically) binding and concealing even if there are no restrictions on the computational resources. One could hope that there might be a way to exploit the intrinsic properties of quantum mechanics, as in the protocols for unconditionally secure key distribution.

However, this is impossible, as Dominic Mayers showed in 1996 . Any such protocol can be reduced to a protocol where the system is in one of two pure states after the commitment phase, depending on the bit Alice wants to commit. If the protocol is unconditionally concealing, then Alice can unitarily transform these states into each other using the properties of the Schmidt decomposition, effectively defeating the binding property.

One subtle assumption of the proof is that the commit phase must be finished at some point in time. This leaves room for protocols that require a continuing information flow until the bit is unveiled or the protocol is cancelled, in which case it is not binding anymore.[28] More generally, Mayers's proof applies only to protocols that exploit quantum physics but not special relativity. Kent has shown that there exist unconditionally secure protocols for bit commitment that exploit the principle of special relativity stating that information cannot travel faster than light.[29]

Commitments based on physical unclonable functions

Physical unclonable functions (PUFs) rely on the use of a physical key with internal randomness, which is hard to clone or to emulate. Electronic, optical and other types of PUFs[30] have been discussed extensively in the literature, in connection with their potential cryptographic applications including commitment schemes.[31][32]

See also

مراجع

  1. ↑ عوديد غولدرايش (2001). أسس التشفير : المجلد 1، الأدوات الأساسية. مطبعة جامعة كامبريدج. ISBN 0-521-79172-3. : 224
  2. ↑ جيل براسارد، ديفيد شوم، وكلود كريبو، إثباتات الحد الأدنى من الكشف عن المعرفة ، مجلة علوم الحاسوب والنظم، المجلد 37، الصفحات 156-189، 1988.
  3. ↑ غولدريتش، أوديد؛ ميكالي، سيلفيو؛ ويغدرسون، آفي (1991). "براهين لا تُثبت شيئًا سوى صحتها" . مجلة ACM . 38 (3): 690-728 . CiteSeerX 10.1.1.420.1478 . doi : 10.1145/116825.116852 . S2CID 2389804 .  
  4. ↑ راسل إمباغليازو، موتي يونغ: حسابات الحد الأدنى من المعرفة المباشرة. CRYPTO 1987: 40-51
  5. ↑ ناور، موني (1991). "التزام البت باستخدام العشوائية الزائفة" . مجلة علم التشفير . 4 (2): 151-158 . doi : 10.1007/BF00196774 . S2CID 15002247 . 
  6. 1 2 كلود كريبو، الالتزام ، مختبر التشفير والمعلومات الكمومية، كلية علوم الحاسوب بجامعة ماكجيل ، تم الاطلاع عليه في 11 أبريل 2008
  7. ↑ مانويل بلوم، قلب العملة عبر الهاتف ، وقائع مؤتمر CRYPTO 1981، الصفحات 11-15، 1981، أعيد طبعه في SIGACT News المجلد 15، الصفحات 23-27، 1983، كلية علوم الحاسوب بجامعة كارنيجي ميلون .
  8. ↑ شيمون إيفن. بروتوكول توقيع العقود. في ألين غيرشو ، محرر، التقدم في علم التشفير (وقائع مؤتمر CRYPTO '82)، الصفحات 148-153، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 1982.
  9. ↑ أ. شامير، ر. ل. ريفست ، ول. أدلمان، " بوكر العقل " . في ديفيد أ. كلارنر ، محرر، البستاني الرياضي ( ISBN) 978-1-4684-6686-7)، الصفحات 37-43. وادزورث، بلمونت، كاليفورنيا، 1981.
  10. ↑ أوديد غولدريتش ، سيلفيو ميكالي ، وآفي ويغدرسون ، براهين لا تُنتج شيئًا سوى صحتها، أو أن جميع اللغات في NP لديها أنظمة إثبات ذات معرفة صفرية ، مجلة ACM ، 38: 3، ص 690-728، 1991
  11. ↑ أوديد غولدريتش وهوغو كراوتشيك ، حول تركيب أنظمة إثبات المعرفة الصفرية ، مجلة SIAM للحوسبة ، 25: 1، ص 169-192، 1996
  12. ↑ جينارو؛ روزاريو؛ رابين، مايكل أو.؛ ​​رابين، تال. "تبسيط VSS والحسابات متعددة الأطراف السريعة مع تطبيقات على التشفير العتبة". وقائع الندوة السنوية السابعة عشرة لجمعية ACM حول مبادئ الحوسبة الموزعة . يونيو 1998.
  13. ↑ ر. كانيتي وم. فيشلين. الالتزامات القابلة للتركيب عالميًا.
  14. ↑ شين هين أونغ وسليل فادان (1990). المعرفة الصفرية الكاملة في جولة ثابتة، في وقائع مؤتمر STOC، ص 482-493، المشار إليه في شين هين أونغ وسليل فادان (2008). تكافؤ بين المعرفة الصفرية والالتزامات، نظرية التشفير.
  15. ^ توشيا إيتو، ييجي أوتا، هيروكي شيزويا (1997). لغة بدائية تعتمد على التشفير، في J. Cryptol., 10(1):37-49، مستشهد بها في Shien Hin Ong وSalil Vadhan (2008). التكافؤ بين صفر المعرفة والالتزامات، نظرية التشفير.
  16. ↑ فاغنر، ديفيد (2006)، حلول منتصف الفصل الدراسي ، ص 2 ، تم الاطلاع عليه بتاريخ 26 أكتوبر 2015 
  17. ↑ "المراجع: الالتزام بالبت باستخدام مولدات الأرقام العشوائية الزائفة - Naor (ResearchIndex)" . Citeseer.ist.psu.edu . تاريخ الاسترجاع: 7 يونيو 2014 .
  18. ↑ بيدرسن، توربن برايدز (1992). "مشاركة الأسرار القابلة للتحقق الآمنة غير التفاعلية والقائمة على نظرية المعلومات". التطورات في علم التشفير - CRYPTO '91 . سلسلة محاضرات في علوم الحاسوب. المجلد 576. برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ. الصفحات 129-140 . doi : 10.1007/3-540-46766-1_9 . ISBN   978-3-540-55188-1.
  19. ↑ ميتيري، روبرتو؛ دونغ، تشانغيو (2017). "التحليل التشفيري الآلي لمخطط التزام بيدرسن". المؤتمر الدولي حول الأساليب الرياضية والنماذج والهياكل لأمن شبكات الحاسوب . سبرينغر. ص 275-287 . 
  20. ↑ تانغ، تشونمينغ؛ باي، دينغي؛ ليو، تشوجون؛ هي، يونغ (16 أغسطس 2004). "بيدرسن: مشاركة سرية قابلة للتحقق وآمنة غير تفاعلية ونظرية معلوماتية" (ملف PDF) . أرشيف مطبوعات علم التشفير الإلكترونية . التقدم في علم التشفير CRYPTO 1991، سبرينغر. مؤرشف من الأصل (ملف PDF) في 11 أغسطس 2017. تم الاطلاع عليه في 2 فبراير 2019 .
  21. ↑ موني ناور، رافائيل أوستروفسكي، راماراثنام فينكاتيسان، موتي يونغ: حجج المعرفة الصفرية المثالية لـ NP باستخدام أي تبديل أحادي الاتجاه. مجلة علم التشفير 11(2): 87-108 (1998)
  22. ↑ مينيز، ألفريد جيه؛ فان أورشوت، بول سي؛ فانستون، سكوت إيه (2018). دليل التشفير التطبيقي . مطبعة سي آر سي.
  23. ↑ موريس، ديميتريس؛ تسوتسوس، نكتاريوس جورجيوس (26 يناير 2022). "التنكر: تجميع متعدد الأطراف قابل للتحقق مع التزامات مضاعفة آمنة" (ملف PDF) . أرشيف الطباعة الإلكترونية لعلم التشفير .
  24. ↑ كاتالانو، داريو؛ فيوري، داريو (2013). "التزامات المتجهات وتطبيقاتها" . التشفير بالمفتاح العام - PKC 2013. سلسلة محاضرات في علوم الحاسوب. المجلد 7778. سبرينغر برلين هايدلبرغ. الصفحات 55-72 . doi : 10.1007/978-3-642-36362-7_5 . ISBN   978-3-642-36362-7.كاتالانو، داريو؛ فيوري، داريو (2013). "التزامات المتجهات وتطبيقاتها" (ملف PDF) . الرابطة الدولية لأبحاث التشفير .
  25. ^ بيكر ، جورج (2008-07-18). “مخططات توقيع Merkle وأشجار Merkle وتحليل التشفير الخاص بها” (PDF) . جامعة الرور بوخوم. ص. 16. مؤرشفة من الأصلي (PDF) بتاريخ 22-12-2014 . تم الاسترجاع 2013/11/20 . 
  26. ↑ كيت، أنيكيت؛ زافيروتشا، غريغوري؛ غولدبيرغ، إيان (2010). "الالتزامات ذات الحجم الثابت لكثيرات الحدود وتطبيقاتها" (ملف PDF) . المؤتمر الدولي لنظرية وتطبيق علم التشفير وأمن المعلومات .
  27. ↑ براسارد، جيل؛ كريبو، كلود؛ مايرز، دومينيك؛ سالفاي، لويس (1997). "مراجعة موجزة حول استحالة الالتزام الكمي للبت". arXiv : quant-ph/9712023 .
  28. ↑ كينت، أدريان (1999). "الالتزام الكلاسيكي الآمن بالبتات باستخدام قنوات اتصال ذات سعة ثابتة". arXiv : quant-ph/9906103 .
  29. ↑ كينت، أ. (1999). "التزام البت الآمن غير المشروط". مجلة Physical Review Letters ، 83 (7): 1447-1450 . arXiv : quant-ph/9810068 . Bibcode : 1999PhRvL..83.1447K . doi : 10.1103/PhysRevLett.83.1447 . S2CID 8823466 . 
  30. ↑ ماكغراث، توماس؛ باغجي، إبراهيم إي.؛ وانغ، زيمينغ إم.؛ روديغ، أوتز؛ يونغ، روبرت جيه. (2019-02-12). "تصنيف PUF" . مراجعات الفيزياء التطبيقية . 6 (1): 011303. Bibcode : 2019ApPRv...6a1303M . doi : 10.1063/1.5079407 .
  31. ↑ روهرماير، أولريش؛ فان دايك، مارتن (2013-04-01). "حول الاستخدام العملي للوظائف المادية غير القابلة للاستنساخ في بروتوكولات النقل غير الواعي والتزام البت". مجلة هندسة التشفير . 3 (1): 17-28 . doi : 10.1007/s13389-013-0052-8 . hdl : 1721.1/103985 . ISSN 2190-8516 . S2CID 15713318 .  
  32. ↑ نيكولوبولوس، جورجيوس م. (30-09-2019). "مخطط بصري للالتزامات التشفيرية باستخدام مفاتيح مادية غير قابلة للاستنساخ". أوبتكس إكسبرس . 27 (20): 29367-29379 . arXiv : 1909.13094 . Bibcode : 2019OExpr..2729367N . doi : 10.1364/OE.27.029367 . ISSN 1094-4087 . PMID 31684673. S2CID 203593129 .