دائرة مشوشة

في بروتوكول الدائرة المشوشة، نستخدم النقل غير الواعي . في النقل غير الواعي، يتم نقل سلسلة نصية بين مُرسِل ومُستقبِل بالطريقة التالية: يمتلك المُرسِل سلسلتين نصيتين.${\displaystyle S_{0}}$و${\displaystyle S_{1}}$يختار المتلقي${\displaystyle b\in \{0,1\}}$ويرسل المرسل${\displaystyle S_{b}}$باستخدام بروتوكول النقل غير الواعي بحيث

1. لا يحصل المتلقي على أي معلومات حول السلسلة غير المرسلة${\displaystyle S_{(1-b)}}$،
2. قيمة${\displaystyle b}$لا يتم الكشف عنها للمرسل.

لاحظ أنه بينما لا يعرف المتلقي${\displaystyle S_{0},S_{1}}$القيم، عملياً يعرف المتلقي بعض المعلومات حول ما${\displaystyle S_{b}}$يقوم بتشفير البيانات بحيث لا يختار المتلقي بشكل أعمى${\displaystyle b}$أي إذا${\displaystyle S_{0}}$يشفر قيمة خاطئة،${\displaystyle S_{1}}$يقوم المتلقي بتشفير قيمة صحيحة ويريد الحصول على القيمة الصحيحة المشفرة، فيختار المتلقي${\displaystyle b=1}$.

يمكن إنشاء عملية النقل غير الواعية باستخدام التشفير غير المتماثل مثل نظام التشفير RSA .

المشغل${\displaystyle \parallel }$عملية دمج السلاسل النصية .${\displaystyle \oplus }$هي عملية XOR ثنائية . k هو مُعامل أمان وطول المفاتيح. يجب أن يكون أكبر من 80 وعادةً ما يتم ضبطه على 128.

يمكن توليد الدائرة المنطقية للدوال الصغيرة يدويًا. من المتعارف عليه استخدام بوابات XOR و AND ثنائية المدخلات . من المهم أن تحتوي الدائرة المولدة على أقل عدد ممكن من بوابات AND (انظر تحسين XOR الحر ). توجد طرق لتوليد الدائرة المُحسَّنة من حيث عدد بوابات AND باستخدام تقنية توليف المنطق . ^{[ 5 ]} دائرة مسألة المليونيرات هي دائرة مقارنة رقمية (وهي سلسلة من دوائر الجمع الكاملة تعمل كدائرة طرح وتُخرج علامة الحمل ). يمكن تنفيذ دائرة الجمع الكاملة باستخدام بوابة AND واحدة فقط وعدد من بوابات XOR . هذا يعني أن العدد الإجمالي لبوابات AND في دائرة مسألة المليونيرات يساوي عرض بتات المدخلات.

تقوم أليس (المُشَوِّهة) بتشفير الدائرة المنطقية في هذه الخطوة للحصول على دائرة مشوشة . تُعيّن أليس سلسلتين عشوائيتين تُسميان " التسميات" لكل سلك في الدائرة: واحدة للدلالة المنطقية 0 والأخرى للدلالة 1. (يبلغ طول التسمية k بت، حيث k هو مُعامل الأمان ، وعادةً ما يُضبط على 128). بعد ذلك، تنتقل إلى جميع البوابات في الدائرة وتستبدل 0 و1 في جداول الحقيقة بالتسميات المُناسبة. يُبيّن الجدول أدناه جدول الحقيقة لبوابة AND ذات مدخلين.${\displaystyle w^{a},w^{b}}$والإخراج${\displaystyle w^{c}}$:

استبدلت أليس الرقمين 0 و1 بالعلامات المقابلة لهما:

أ	ب	ج
${\displaystyle X_{0}^{a}}$	${\displaystyle X_{0}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{0}^{a}}$	${\displaystyle X_{1}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{1}^{a}}$	${\displaystyle X_{0}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{1}^{a}}$	${\displaystyle X_{1}^{b}}$	${\displaystyle X_{1}^{c}}$

ثم تقوم بتشفير مدخل الإخراج في جدول الحقيقة باستخدام تسميتي الإدخال المتطابقتين. يُسمى الجدول المُشفّر بالجدول المُشوَّش. يتم ذلك بحيث لا يمكن فك تشفير الجدول المُشوَّش إلا إذا كان لدى الشخص تسميتي الإدخال الصحيحتين. في الجدول أدناه،${\displaystyle Enc_{\kappa }(X)}$هو تشفير متماثل بمفتاحين حيث${\displaystyle \kappa }$المفتاح السري و X هي القيمة المراد تشفيرها (انظر تشفير الكتلة ذو المفتاح الثابت ).

جدول مشفر
${\displaystyle Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{0}^{a},X_{1}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{1}^{a},X_{0}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{1}^{a},X_{1}^{b}}(X_{1}^{c})}$

بعد ذلك، تقوم أليس بترتيب الجدول عشوائياً بحيث لا يمكن تحديد قيمة الناتج من الصف. اسم البروتوكول، " garbled "، مشتق من هذا الترتيب العشوائي .

طاولة مشوشة
${\displaystyle Enc_{X_{1}^{a},X_{1}^{b}}(X_{1}^{c})}$
${\displaystyle Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{0}^{a},X_{1}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{1}^{a},X_{0}^{b}}(X_{0}^{c})}$

ترسل أليس الجداول المشوشة المحسوبة لجميع البوابات في الدائرة إلى بوب. يحتاج بوب إلى تسميات الإدخال لفتح الجداول المشوشة. لذلك، تختار أليس التسميات المطابقة لإدخالها.${\displaystyle a}$ويرسلها إلى بوب. على سبيل المثال، إذا كانت مدخلات أليس هي${\displaystyle \mathbf {a} =a_{4}a_{3}a_{2}a_{1}a_{0}=01101}$ثم ترسل${\displaystyle X_{0}^{a_{4}}}$،${\displaystyle X_{1}^{a_{3}}}$،${\displaystyle X_{1}^{a_{2}}}$،${\displaystyle X_{0}^{a_{1}}}$، و${\displaystyle X_{1}^{a_{0}}}$إلى بوب. لن يتعلم بوب أي شيء عن مساهمة أليس.${\displaystyle \mathbf {a} }$، لأن التصنيفات يتم إنشاؤها عشوائياً بواسطة أليس وتبدو كسلاسل عشوائية بالنسبة لبوب.

يحتاج بوب أيضًا إلى التصنيفات المطابقة لمدخلاته. ويتلقى هذه التصنيفات من خلال عمليات نقل غير واعية لكل بت من مدخلاته. على سبيل المثال، إذا كانت مدخلات بوب هي${\displaystyle \mathbf {b} =b_{4}b_{3}b_{2}b_{1}b_{0}=10100}$بوب يطلب أولاً${\displaystyle b_{0}=0}$بين ملصقات أليس${\displaystyle X_{0}^{b_{0}}}$و${\displaystyle X_{1}^{b_{0}}}$من خلال عملية نقل غير واعية بنسبة 1 من 2 ، يتلقى${\displaystyle X_{0}^{b_{0}}}$وهكذا دواليك. بعد عمليات النقل غير الواعية ، لن تعلم أليس أي شيء عن مدخلات بوب، ولن يعلم بوب أي شيء عن العلامات الأخرى.

بعد نقل البيانات، حصل بوب على الجداول المشوّهة وعلامات الإدخال. قام بفحص جميع البوابات واحدة تلو الأخرى وحاول فك تشفير الصفوف في جداولها المشوّهة. تمكن من فتح صف واحد لكل جدول واستخراج علامة الإخراج المقابلة له.${\displaystyle X^{c}=Dec_{X^{a},X^{b}}(garbled\_table[i])}$، أين${\displaystyle 0\leq i\leq 3}$ويواصل التقييم حتى يصل إلى علامات الإخراج.

بعد التقييم، يحصل بوب على تصنيف المخرجات.${\displaystyle X^{c}}$وتعرف أليس أن هذا يرتبط بقيمة منطقية لأنها تمتلك كلا التصنيفين:${\displaystyle X_{0}^{c}}$و${\displaystyle X_{1}^{c}}$إما أن تشارك أليس معلوماتها مع بوب أو أن يكشف بوب عن الناتج لأليس بحيث يتعرف أحدهما أو كلاهما على الناتج.

في عملية التحسين هذه، تقوم أليس بتوليد بت عشوائي،${\displaystyle s}$، تسمى بت التحديد لكل سلك${\displaystyle w}$تقوم بتعيين البت الأول من التسمية إلى 0،${\displaystyle X_{0}^{a}}$ل${\displaystyle s}$والجزء الأول من الملصق رقم 1،${\displaystyle X_{1}^{a}}$، ل${\displaystyle {\bar {s}}}$( ليس من)${\displaystyle s}$وهي تفعل الشيء نفسه بالنسبة للأسلاك.${\displaystyle w^{b}}$ثم، بدلاً من التبديل العشوائي، تقوم بترتيب الجدول المشوّه وفقًا لبتات الاختيار المدخلة. بهذه الطريقة، لا يحتاج بوب إلى اختبار جميع صفوف الجدول الأربعة للعثور على الصف الصحيح، لأنه يتلقى بتات المؤشر مع كل تسمية سلكية، ويمكنه العثور على الصف الصحيح وفك تشفيره بمحاولة واحدة. هذا يقلل من عبء التقييم بمقدار أربعة أضعاف. كما أنه لا يكشف أي شيء عن قيمة الإخراج لأن بتات الاختيار يتم توليدها عشوائيًا. ^{[ 6 ]}

يُقلل هذا التحسين حجم الجداول المشوّهة من 4 صفوف إلى 3 صفوف. هنا، بدلاً من توليد تسمية لسلك الإخراج للبوابة عشوائيًا، تقوم أليس بتوليدها باستخدام دالة لتسميات الإدخال. تُولّد أليس تسميات الإخراج بحيث يصبح الإدخال الأول في الجدول المشوّه عبارة عن أصفار بالكامل، وبالتالي لا حاجة لإرساله: ^{[ 7 ]}

${\displaystyle {\begin{aligned}&Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})=0\\&X_{0}^{c}=Dec_{X_{0}^{a},X_{0}^{b}}(0).\end{aligned}}}$

في عملية التحسين هذه، تقوم أليس بتوليد قيمة عشوائية عالمية مكونة من (k-1) بت${\displaystyle R}$وهو أمر يبقى سراً. أثناء تشويش بوابات الإدخال${\displaystyle w^{a}}$و${\displaystyle w^{b}}$إنها لا تقوم إلا بإنشاء التصنيفات.${\displaystyle (X_{0}^{a},X_{0}^{b})}$ويحسب التصنيفات الأخرى على النحو التالي:${\displaystyle X_{1}^{a}=X_{0}^{a}\oplus (R\parallel 1)}$و${\displaystyle X_{1}^{b}=X_{0}^{b}\oplus (R\parallel 1)}$باستخدام هذه القيم، يتم تحديد تسمية سلك خرج بوابة XOR${\displaystyle w^{c}}$مع أسلاك الإدخال${\displaystyle w^{a}}$،${\displaystyle w^{b}}$تم ضبطه على${\displaystyle X^{c}=X^{a}\oplus X^{b}}$تم تقديم برهان الأمان في نموذج أوراكل العشوائي لهذا التحسين في ورقة Free-XOR. ^{[ 8 ]}

تتيح هذه الطريقة تشويه بوابات AND وتقييمها بكفاءة باستخدام خوارزمية AES ذات المفتاح الثابت ، بدلاً من استخدام دوال التجزئة التشفيرية المكلفة مثل SHA-2 . في مخطط التشويه هذا، المتوافق مع تقنيات Free XOR و Row Reduction ، يكون مفتاح الإخراج${\displaystyle X^{c}}$يتم تشفيرها باستخدام رمز الإدخال${\displaystyle X^{a}}$و${\displaystyle X^{b}}$باستخدام وظيفة التشفير${\displaystyle Enc(X^{a},X^{b},T,X^{c})=\pi (K)\oplus K\oplus X^{c}}$، أين${\displaystyle K=2X^{a}\oplus 4X^{b}\oplus T}$،${\displaystyle \pi }$هو تشفير كتلي ذو مفتاح ثابت (على سبيل المثال، تم إنشاؤه باستخدام AES )، و${\displaystyle T}$هو رقم فريد لكل بوابة (مثل معرف البوابة) يسمى tweak . ^{[ 9 ]}

يُقلل هذا التحسين حجم جدول التشويه لبوابات AND من 3 صفوف في تقنية تقليل الصفوف إلى صفين. وقد ثبت أن هذا هو الحد الأدنى النظري لعدد الصفوف في جدول التشويه، وذلك لفئة معينة من تقنيات التشويه. ^{[ 10 ]}