معضلة التراكم

في تحليل الشفرات ، تُعدّ نظرية التراكم مبدأً يُستخدم في تحليل الشفرات الخطي لبناء تقريبات خطية لعمل خوارزميات التشفير الكتلي . وقد قدّمها ميتسورو ماتسوي (1993) كأداة تحليلية لتحليل الشفرات الخطي. ^{[ 1 ]} تنصّ النظرية على أن الانحياز (انحراف القيمة المتوقعة عن 1/2) لدالة منطقية خطية (شرط XOR) لمتغيرات عشوائية ثنائية مستقلة يرتبط بحاصل ضرب انحيازات المدخلات: ^{[ 2 ]}

${\displaystyle \varepsilon (X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=2^{n-1}\prod _{i=1}^{n}\varepsilon (X_{i})}$

أو

${\displaystyle I(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=\prod _{i=1}^{n}I(X_{i})}$

أين${\displaystyle \varepsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$هو الانحياز (نحو الصفر ^{[ 3 ]} ) و${\displaystyle I\in [-1,1]}$عدم التوازن : ^{[ 4 ] [ 5 ]}

${\displaystyle \varepsilon (X)=P(X=0)-{\frac {1}{2}}}$

${\displaystyle I(X)=P(X=0)-P(X=1)=2\varepsilon (X).}$

وعلى العكس من ذلك، إذا لم تتحقق اللمة، فإن متغيرات الإدخال ليست مستقلة. ^{[ 6 ]}

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

لاحظ أنه بالنسبة لمتغيرين، فإن الكمية${\displaystyle I(X\oplus Y)}$هو مقياس ارتباط لـ${\displaystyle X}$و​${\displaystyle Y}$، يساوي​${\displaystyle P(X=Y)-P(X\neq Y)}$⁠ ;${\displaystyle I(X)}$يمكن تفسير ذلك على أنه ارتباط بين${\displaystyle X}$مع​${\displaystyle 0}$⁠ .

يمكن التعبير عن معضلة التراكم بشكل أكثر طبيعية عندما تأخذ المتغيرات العشوائية قيمًا في${\displaystyle \{-1,1\}}$إذا أدخلنا متغيرات${\displaystyle \chi _{i}=1-2X_{i}=(-1)^{X_{i}}}$(الرسم التخطيطي ⁠${\displaystyle 0}$إلى​​${\displaystyle 1}$و​​${\displaystyle 1}$إلى​​${\displaystyle -1}$ثم ، من خلال الفحص، تتحول عملية XOR إلى ناتج:

${\displaystyle \chi _{1}\chi _{2}\cdots \chi _{n}=1-2(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=(-1)^{X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}}}$

وبما أن القيم المتوقعة هي الاختلالات ،${\displaystyle E(\chi _{i})=I(X_{i})}$ثم تنص اللمة على ما يلي :

${\displaystyle E\left(\prod _{i=1}^{n}\chi _{i}\right)=\prod _{i=1}^{n}E(\chi _{i}),}$

وهي خاصية معروفة للقيمة المتوقعة للمتغيرات المستقلة .

بالنسبة للمتغيرات التابعة، يكتسب النموذج أعلاه حدًا للتغاير (موجبًا كان أم سالبًا) ، وبالتالي لا تصح اللمة. في الواقع، بما أن متغيري برنولي مستقلان إذا وفقط إذا كانا غير مرتبطين (أي أن تغايرهما يساوي صفرًا؛ انظر عدم الارتباط )، فإن لدينا عكس لمة التراكم: إذا لم تصح، فإن المتغيرين ليسا مستقلين (غير مرتبطين).

تسمح نظرية التراكم لمحلل الشفرات بتحديد احتمالية تحقق المساواة التالية:

${\displaystyle X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0}$

يحمل ، حيث${\displaystyle X}$المتغيرات الثنائية هي (أي بتات: إما${\displaystyle 0}$أو​​${\displaystyle 1}$) .

دع​${\displaystyle P(A)}$⁠ تشير إلى "احتمالية أن ⁠${\displaystyle A}$" صحيح". إذا كانت قيمته تساوي واحدًا ، "${\displaystyle A}$من المؤكد أن يحدث ذلك، وإذا كان يساوي صفرًا ،${\displaystyle A}$لا يمكن أن يحدث ذلك. أولاً، سننظر في نظرية التراكم لمتغيرين ثنائيين، حيث${\displaystyle P(X_{1}=0)=p_{1}}$و​${\displaystyle P(X_{2}=0)=p_{2}}$⁠ .

والآن، ننتقل إلى ما يلي:

${\displaystyle P(X_{1}\oplus X_{2}=0).}$

بسبب خصائص عملية XOR ، فإن هذا يعادل

${\displaystyle P(X_{1}=X_{2}).}$

⁠${\displaystyle X_{1}=X_{2}=0}$و​​${\displaystyle X_{1}=X_{2}=1}$هي أحداث متنافية ،لذلك يمكننا القول

${\displaystyle P(X_{1}=X_{2})=P(X_{1}=X_{2}=0)+P(X_{1}=X_{2}=1)=P(X_{1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1).}$

الآن، يجب أن نفترض الفرضية الأساسية لنظرية التراكم: المتغيرات الثنائية التي نتعامل معها مستقلة ؛ أي أن حالة أحدها لا تؤثر على حالة أي من المتغيرات الأخرى. وبالتالي، يمكننا توسيع دالة الاحتمال كما يلي:

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =P(X_{1}=0)P(X_{2}=0)+P(X_{1}=1)P(X_{2}=1)}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1})(1-p_{2})}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1}-p_{2}+p_{1}p_{2})}$
	${\displaystyle =2p_{1}p_{2}-p_{1}-p_{2}+1}$

والآن نعبر عن الاحتمالات${\displaystyle p_{1}}$و​​${\displaystyle p_{2}}$كما​​${\displaystyle {\tfrac {1}{2}}+\varepsilon _{1}}$و​​${\displaystyle {\tfrac {1}{2}}+\varepsilon _{2}}$، حيث​${\displaystyle \varepsilon }$تمثل s انحرافات الاحتمالية - مقدار انحراف الاحتمالية عن${\displaystyle {\tfrac {1}{2}}}$⁠ .

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =2(1/2+\varepsilon _{1})(1/2+\varepsilon _{2})-(1/2+\varepsilon _{1})-(1/2+\varepsilon _{2})+1}$
	${\displaystyle =1/2+\varepsilon _{1}+\varepsilon _{2}+2\varepsilon _{1}\varepsilon _{2}-1/2-\varepsilon _{1}-1/2-\varepsilon _{2}+1}$
	${\displaystyle =1/2+2\varepsilon _{1}\varepsilon _{2}}$

وبالتالي فإن التحيز الاحتمالي${\displaystyle \varepsilon _{1,2}}$بالنسبة لمجموع XOR أعلاه، يكون${\displaystyle 2\varepsilon _{1}\varepsilon _{2}}$⁠ .

يمكن توسيع هذه الصيغة لتشمل المزيد${\displaystyle X}$s كما يلي:

${\displaystyle P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\varepsilon _{i}}$

لاحظ أنه إذا كان أي من ⁠${\displaystyle \varepsilon }$إذا كانت قيمة s تساوي صفرًا؛ أي أن أحد المتغيرات الثنائية غير متحيز، فإن دالة الاحتمال بأكملها ستكون غير متحيزة - تساوي ⁠${\displaystyle {\tfrac {1}{2}}}$⁠ .

وهناك تعريف آخر ذو صلة ومختلف قليلاً للتحيز وهو ⁠${\displaystyle \varepsilon _{i}=P(X_{i}=1)-P(X_{i}=0)}$في الواقع ، هو أقل بمرتين من القيمة السابقة. الميزة هي أنه الآن مع

${\displaystyle \varepsilon _{\text{total}}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

لدينا

${\displaystyle \varepsilon _{\text{total}}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

إن إضافة المتغيرات العشوائية تعني مضاعفة تحيزاتها (وفقًا للتعريف الثاني).

عملياً، الـ${\displaystyle X}$تمثل s تقريبات لمكونات الاستبدال ( S-boxes ) في تشفيرات الكتل. عادةً ،${\displaystyle X}$القيم هي مدخلات إلى صندوق الاستبدال (S-box) و${\displaystyle Y}$تمثل القيم المخرجات المقابلة. بمجرد النظر إلى مربعات الاستبدال (S-boxes)، يستطيع محلل الشفرات تحديد انحرافات الاحتمالية. تكمن الحيلة في إيجاد توليفات من قيم المدخلات والمخرجات التي تكون احتمالاتها صفرًا أو واحدًا. كلما اقترب التقريب من الصفر أو الواحد، زادت فائدته في تحليل الشفرات الخطي.

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

• التباين §  الخصائص – تباين مجموع متغيرات حقيقية مستقلة