نظام التشفير Paillier

1. اختر عددين أوليين كبيرين${\displaystyle p}$و${\displaystyle q}$بشكل عشوائي ومستقل عن بعضها البعض بحيث${\displaystyle \gcd(pq,(p-1)(q-1))=1}$تُضمن هذه الخاصية إذا كان كلا العددين الأوليين متساويين في الطول. ^{[ 1 ]}
2. الحوسبة${\displaystyle n=pq}$و${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$. lcm تعني المضاعف المشترك الأصغر .
3. اختر عددًا صحيحًا عشوائيًا${\displaystyle g}$أين${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. يضمن${\displaystyle n}$يقسم ترتيب${\displaystyle g}$عن طريق التحقق من وجود المعكوس الضربي المعياري التالي :${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$،

حيث الدالة${\displaystyle L}$يُعرَّف بأنه${\displaystyle L(x)={\frac {x-1}{n}}}$.

لاحظ أن الترميز${\displaystyle {\frac {a}{b}}}$لا يدل على الضرب المعياري لـ${\displaystyle a}$مضروبًا في المعكوس الضربي المعياري لـ${\displaystyle b}$بل بالأحرى ناتج قسمة${\displaystyle a}$مقسوماً على${\displaystyle b}$أي، أكبر قيمة عددية صحيحة${\displaystyle v\geq 0}$لتحقيق العلاقة${\displaystyle a\geq vb}$.

• المفتاح العام (للتشفير) هو${\displaystyle (n,g)}$.
• المفتاح الخاص (مفتاح فك التشفير) هو${\displaystyle (\lambda ,\mu ).}$

في حالة استخدام p وq بطول متساوٍ، فإن أحد أشكال خطوات توليد المفاتيح المذكورة أعلاه سيكون أبسط وهو تعيين${\displaystyle g=n+1,\lambda =\varphi (n),}$و${\displaystyle \mu =\varphi (n)^{-1}{\bmod {n}}}$، أين${\displaystyle \varphi (n)=(p-1)(q-1)}$[ ^{1 ]} يُوصى بالصيغة الأبسط لأغراض التنفيذ، لأن وقت الحساب في الصيغة العامة ^هو${\displaystyle \mu }$يمكن أن تكون عالية جدًا مع الأعداد الأولية الكبيرة بما فيه الكفاية p و q.

1. يترك${\displaystyle m}$رسالة سيتم تشفيرها حيث${\displaystyle 0\leq m<n}$
2. اختر عشوائيا${\displaystyle r}$أين${\displaystyle 0<r<n}$و ${\displaystyle \gcd(r,n)=1}$( ملاحظة: إذا وجدت قيمة تحتوي على${\displaystyle \gcd(r,n)\neq 1}$يمكنك استخدام هذا لحساب المفتاح الخاص: هذا احتمال ضعيف بما يكفي لتجاهله.)
3. احسب النص المشفر كالتالي:${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

1. يترك${\displaystyle c}$ليكن النص المشفر المراد فك تشفيره، حيث${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. احسب رسالة النص الأصلي على النحو التالي:${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

كما تشير الورقة الأصلية ^{[ 2 ] ، فإن فك التشفير هو "بشكل أساسي عملية أسية واحدة modulo}${\displaystyle n^{2}}$"

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

• الجمع المتماثل للنصوص العادية

ناتج فك تشفير نصين مشفرين يساوي مجموع النصين الأصليين المقابلين لهما.

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

ناتج عملية تحويل النص المشفر إلى نص عادي يثير${\displaystyle g}$سيتم فك التشفير إلى مجموع النصوص الأصلية المقابلة،

${\displaystyle D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

• الضرب المتماثل للنصوص العادية

النص المشفر المرفوع إلى قوة النص الأصلي يُفك تشفيره ليصبح حاصل ضرب النصين الأصليين.

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},\,}$

${\displaystyle D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}}.\,}$

وبشكل أعم، فإن النص المشفر المرفوع إلى ثابت k سيتم فك تشفيره إلى حاصل ضرب النص الأصلي في الثابت.

${\displaystyle D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.\,}$

ومع ذلك، بالنظر إلى تشفيرات Paillier لرسالتين، لا توجد طريقة معروفة لحساب تشفير ناتج هذه الرسائل دون معرفة المفتاح الخاص.

يستغل نظام التشفير Paillier حقيقة أنه يمكن حساب بعض اللوغاريتمات المنفصلة بسهولة.

على سبيل المثال، بحسب نظرية ذات الحدين ،

${\displaystyle (1+n)^{x}=\sum _{k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{قوى أعلى من }}n}$

وهذا يدل على أن:

${\displaystyle (1+n)^{x}\equiv 1+nx{\pmod {n^{2}}}}$

لذلك، إذا:

${\displaystyle y=(1+n)^{x}{\bmod {n}}^{2}}$

ثم

${\displaystyle x\equiv {\frac {y-1}{n}}{\pmod {n}}}$.

هكذا:

${\displaystyle L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}}$،

حيث الدالة${\displaystyle L}$يُعرَّف بأنه${\displaystyle L(u)={\frac {u-1}{n}}}$(ناتج قسمة عدد صحيح) و${\displaystyle x\in \mathbb {Z} _{n}}$.

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

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

لكن باييه وبوانتشيفال اقترحا نظام تشفير مُحسَّنًا يدمج التجزئة المُدمجة للرسالة m مع قيمة عشوائية r . وعلى غرار نظام تشفير كرامر-شوب ، تمنع التجزئة المُهاجم، المُعطى فقط c، من تغيير m بشكلٍ ذي معنى. ومن خلال هذا التعديل، يُمكن إثبات أن النظام المُحسَّن آمن وفقًا لمعيار IND-CCA2 في نموذج أوراكل العشوائي .