دالة ناؤور-رينجولد العشوائية الزائفة

في عام 1997، وصف موني ناور وعمر رينغولد طرقًا فعالة لإنشاء العديد من العناصر التشفيرية الأساسية في التشفير بالمفتاح الخاص والتشفير بالمفتاح العام . وكانت نتيجتهما إنشاء دالة شبه عشوائية فعالة . ليكن p و l عددين أوليين بحيث l يقسم p − 1. اختر عنصرًا g ∈${\displaystyle {\mathbb {F} _{p}}^{*}}$من الرتبة الضربية l . عندئذٍ _، لكل متجه ذي (n+1) بُعد a = ( a₀ , _a₁ , ..., aₙ ₎ ∈${\displaystyle (\mathbb {F} _{l})^{n+1}}$إنهم يحددون الوظيفة

$${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}$$

حيث x  = x ₁ ... x _n هو التمثيل الثنائي للعدد الصحيح x ، 0  ≤ x ≤ 2 ^{n −1} ، مع بعض الأصفار الإضافية في البداية إذا لزم الأمر. ^{[ 1 ]}

لنفترض أن p  = 7 و l  = 3؛ إذن l يقسم p − 1. اختر g  = 4 ∈${\displaystyle {\mathbb {F} _{7}}^{*}}$من الرتبة الضربية 3 (لأن ^4³ = 6⁴ ≡ 1 mod  7). بالنسبة لـ n  = 3، و a  = (1, 1, 2, 1)، و x  = 5 (التمثيل الثنائي للعدد 5 هو 101)، يمكننا حساب${\displaystyle f_{a}(5)}$على النحو التالي:

$${\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}$$

$${\displaystyle f_{a}(5)=4^{1\cdot 1^{1}2^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}}$$

تقييم الوظيفة${\displaystyle f_{a}(x)}$يمكن إنجاز ذلك بكفاءة عالية في بناء ناور-رينغولد . حساب قيمة الدالة${\displaystyle f_{a}(x)}$عند أي نقطة معينة، يكون الناتج قابلاً للمقارنة مع عملية أسية نمطية واحدة وعمليات ضرب نمطية من الرتبة n. ويمكن حساب هذه الدالة بالتوازي باستخدام دوائر عتبة ذات عمق محدود وحجم متعدد الحدود.

يمكن استخدام دالة Naor –Reingold كأساس للعديد من المخططات التشفيرية بما في ذلك التشفير المتماثل والمصادقة والتوقيعات الرقمية .

لنفترض أن المهاجم يرى عدة مخرجات للدالة، على سبيل المثال${\displaystyle f_{a}(1)=g^{a_{1}},f_{a}(2)=g^{a_{2}},f_{a}(3)=g^{a_{1}a_{2}}}$...${\displaystyle f_{a}(k)=g^{a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$ويريد أن يحسب${\displaystyle f_{a}(k+1)}$لنفترض، تبسيطًا، أن _x1 = 0، عندها يحتاج المهاجم إلى حل مسألة ديفي-هيلمان الحسابية (CDH) بين${\displaystyle f_{a}(1)=g^{a_{1}}}$و${\displaystyle f_{a}(k)=g^{a_{2}^{x_{2}}...a_{n}^{x_{n}}}}$للحصول على${\displaystyle f_{a}(k+1)=g^{a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}}$بشكل عام، يؤدي الانتقال من k إلى k + 1 إلى تغيير نمط البتات، وما لم يكن k + 1 قوة للعدد 2، يمكن تقسيم الأس إلى${\displaystyle f_{a}(k+1)}$بحيث تتوافق العملية الحسابية مع حساب مفتاح ديفي-هيلمان بين نتيجتين سابقتين. يسعى هذا المهاجم إلى التنبؤ بالعنصر التالي في التسلسل . سيكون هذا الهجوم بالغ الخطورة، ولكن من الممكن أيضًا التصدي له بالعمل ضمن مجموعات لحل مسألة ديفي-هيلمان الصعبة .

يُعدّ حجم تعقيدها الخطي أحد المقاييس الطبيعية لمدى فائدة متتالية ما لأغراض التشفير . التعقيد الخطي لمتتالية مكونة من n عنصرًا W( x )، حيث x = 0, 1, 2, ..., n – 1، على حلقة${\displaystyle {\mathcal {R}}}$يمثل طول العلاقة التكرارية الخطية الأقصر W( x + l ) = A _{_{l -1}} W( x + l -1) + ... + A_₀ W( x )، حيث x = 0, 1, 2, ..., n – l -1، و A_₀ , ..., A_{_{l -1}} ∈${\displaystyle {\mathcal {R}}}$، وهو ما يتحقق من خلال هذه المتتالية.

بالنسبة للبعض${\displaystyle \gamma }$> 0، n ≥ (1+${\displaystyle \gamma }$)${\displaystyle \log l}$، لأي${\displaystyle \delta >0}$، عندما تكون قيمة l كبيرة بما فيه الكفاية ، يصبح التعقيد الخطي للمتتالية${\displaystyle f_{a}(x)}$،0 ≤ x ≤ 2 ^n-1 ، ويرمز لها بـ${\displaystyle L_{a}}$يرضي

$${\displaystyle L_{a}\geqslant {\begin{cases}l^{1-\ \delta \,\!}&{\text{, if }}\gamma \,\!\geqslant 2\\l^{\left({\tfrac {\ \gamma \,\!}{2-\ \delta \,\!}}\right)}&{\text{, if }}\gamma \,\!<2\end{cases}}}$$

للجميع باستثناء ربما على الأكثر${\displaystyle 3(l-1)^{n-\delta }}$المتجهات أ ∈${\displaystyle (\mathbb {F} _{l})^{n}}$[ ^{3 ]} إن نطاق هذا العمل له عيوب، وهو أنه لا ينطبق على الحالة المثيرة للاهتمام للغاية ^.${\displaystyle \log p\approx \log n\approx {n.}}$

التوزيع الإحصائي لـ${\displaystyle f_{a}(x)}$ يقترب التوزيع بشكل أسي من التوزيع المنتظم لجميع المتجهات a ∈ تقريبًا${\displaystyle (\mathbb {F} _{l})^{n}}$.

يترك${\displaystyle {\mathbf {D} }_{a}}$ليكن التباين في المجموعة${\displaystyle \{f_{a}(x)|0\leq x\leq 2^{n-1}\}}$وبالتالي، إذا${\displaystyle n=\log p}$إذا كان طول البت لـ p، فعندئذٍ لجميع المتجهات a ∈${\displaystyle (\mathbb {F} _{l})^{n}}$المقيّد${\displaystyle {\mathbf {D} }_{a}\leq \Delta (l,p)}$يحجز، حيث

$$\displaystyle \Delta (l,p)={\begin{cases}p^{\left({\tfrac {1-\ \gamma \,\!}{2}}\right)}l^{\left({\tfrac {-1}{2}}\right)}\log ^{2}p&{\text{ إذا كان }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ إذا كان }}p^{\gamma \,\!}>l\geqslant p^{\left({\tfrac {2}{3}}\right)}\\p^{\left({\tfrac {1}{4}}\right)}l^{\left({\tfrac {-5}{8}}\right)}\log \log^{2}p&{\text{ إذا كان }}p^{\left({\tfrac {2}{3}}\right)}>l\geqslant p^{\left({\tfrac {1}{2}}\right)}\\p^{\left({\tfrac {1}{8}}\right)}l^{\left({\tfrac {-3}{8}}\right)}\log^{2}p&{\text{ إذا كان }}p^{\left({\tfrac {1}{2}}\right)}>l\geqslant p^{\left({\tfrac {1}{3}}\right)}\\\end{cases}}}$$ و $${\displaystyle \gamma =2.5-\log 3=0.9150\cdots }$$

على الرغم من أن هذه الخاصية لا يبدو أن لها أي آثار تشفيرية مباشرة، إلا أن الحقيقة المعاكسة، أي التوزيع غير المنتظم، إذا كانت صحيحة، ستكون لها عواقب وخيمة على تطبيقات هذه الوظيفة. ^{[ 4 ]}

يُعدّ تمثيل هذه الدالة على المنحنى الإهليلجي ذا أهمية أيضًا. وعلى وجه الخصوص، قد يُسهم في تحسين أمان التشفير للنظام المقابل. ليكن p عددًا أوليًا أكبر من 3، وليكن E منحنى إهليلجيًا على${\displaystyle \mathbb {F} _{p}}$ثم يُعرّف كل متجه a متتالية منتهية في المجموعة الفرعية${\displaystyle \langle G\rangle }$مثل: $${\displaystyle F_{a}(x)=(a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G}$$

أين${\displaystyle x=x_{1}\dots x_{n}}$ هو التمثيل الثنائي للعدد الصحيح${\displaystyle x,0\leq x\leq 2^{n-1}}$تُعرَّف متتالية المنحنيات الإهليلجية لناور-رينغولد على النحو التالي :$${\displaystyle u_{k}=X(f_{a}(k))\;{\mbox{حيث }}X(P){\mbox{ هو الإحداثي السيني لـ}}\;P\in E.}$$^{[ 5 ]}

إذا تحققت فرضية ديفي-هيلمان المتعلقة بالقرار ، فإن المؤشر k لا يكفي للحساب${\displaystyle u_{k}}$في وقت متعدد الحدود، حتى لو قام المهاجم بتنفيذ عدد كبير من الاستعلامات إلى أوراكل عشوائي في وقت متعدد الحدود.

• افتراض ديفي-هيلمان لاتخاذ القرار
• حقل منتهي
• مولد التوافق العكسي
• الأرقام العشوائية الزائفة المتطابقة المعكوسة المعممة

• ناور، موني؛ رينغولد، عمر (2004)، "إنشاءات نظرية الأعداد لدوال شبه عشوائية فعالة"، مجلة رابطة آلات الحوسبة ، 51 (2): 231-262 ، doi : 10.1145/972639.972643 ، S2CID 8665271 .
• شبارلينسكي، إيغور (2003)، التطبيقات التشفيرية لنظرية الأعداد التحليلية: الحدود الدنيا للتعقيد والعشوائية الزائفة (الطبعة الأولى  )، بيركهاوزر بازل، ISBN 978-3-7643-6654-4
• جولدرايش، أوديد (1998)، التشفير الحديث، البراهين الاحتمالية والعشوائية الزائفة (الطبعة الأولى  )، سبرينغر، ISBN 978-3-540-64766-9