وظيفة الانحناء

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

تعني اللاخطية القصوى أن تقريب دالة منحنية بدالة خطية أمرٌ صعب، وهي خاصية مفيدة في الدفاع ضد التحليل الخطي للشفرات . إضافةً إلى ذلك، فإن اكتشاف أي تغيير في مخرجات الدالة لا يُعطي أي معلومات حول التغيير الذي طرأ على المدخلات، مما يجعل الدالة محصنة ضد التحليل التفاضلي للشفرات .

تم تعريف الدوال المنحنية وتسميتها في ستينيات القرن العشرين على يد أوسكار روثاوس في بحث لم يُنشر حتى عام 1976. ^{[ 1 ]} وقد خضعت هذه الدوال لدراسات مستفيضة لتطبيقاتها في علم التشفير ، كما طُبقت أيضًا في تقنيات الطيف المنتشر ، ونظرية الترميز ، والتصميم التوافقي . ويمكن توسيع تعريفها بعدة طرق، مما يؤدي إلى ظهور فئات مختلفة من الدوال المنحنية المعممة التي تشترك في العديد من الخصائص المفيدة للدوال الأصلية.

من المعروف أن VA Eliseev و OP Stepchenkov درسوا الدوال المنحنية، والتي أطلقوا عليها اسم الدوال الدنيا ، في الاتحاد السوفيتي عام 1962. ^{[ 2 ]} ومع ذلك، لم يتم رفع السرية عن نتائجهم حتى الآن.

تُعرف الدوال المنحنية أيضًا باسم الدوال البوليانية غير الخطية تمامًا ( PN ). وتُعرف بعض الدوال التي تقترب قدر الإمكان من اللاخطية التامة (مثل الدوال ذات عدد فردي من البتات، أو الدوال المتجهة) باسم الدوال غير الخطية شبه التامة ( APN ). ^{[ 3 ]}

تُعرَّف الدوال المنحنية بدلالة تحويل والش . تحويل والش لدالة منطقية${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$هي الوظيفة${\displaystyle {\hat {f}}:\mathbb {Z} _{2}^{n}\to \mathbb {Z} }$مقدم من

${\displaystyle {\hat {f}}(a)=\sum _{\scriptstyle {x\in \mathbb {Z} _{2}^{n}}}(-1)^{f(x)+a\cdot x},}$

حيث a · x = a₁x₁ ₊ a₂x₂ + _… + aₙxₙ ( mod 2) هو حاصل الضرب الداخلي في Zₙ² . _[ ^{4 ] أو} _بدلاً ^من ذلك ، ليكن S₀ ( a ) = { _x ∈ Zₙ² : f ( _x ) = a · x } و _{S₁ (} ^a ₎ = { x ∈ ^Zₙ² : f ( x ₎ ≠ a · x _} . ^إذن | S₀ ( a ) | + | S₁ ( _a ) | = 2ⁿ ، _{وبالتالي}  

${\displaystyle {\hat {f}}(a)=\left|S_{0}(a)\right|-\left|S_{1}(a)\right|=2\left|S_{0}(a)\right|-2^{n}.}$

لأي دالة منطقية f و a ∈ Z ⁿ ₂ ، يقع التحويل في النطاق

${\displaystyle -2^{n}\leq {\hat {f}}(a)\leq 2^{n}.}$

علاوة على ذلك، فإن الدالة الخطية f ₀ ( x ) = a · x والدالة الأفينية f ₁ ( x ) = a · x + 1 تمثلان الحالتين المتطرفتين، حيث

${\displaystyle {\hat {f}}_{0}(a)=2^{n},~{\hat {f}}_{1}(a)=-2^{n}.}$

وبالتالي، لكل a ∈ Z ⁿ ₂ قيمة${\displaystyle {\hat {f}}(a)}$يحدد مكان وجود الدالة f ( x ) في النطاق من f ₀ ( x ) إلى f ₁ ( x ).

عرّف روثاوس الدالة المنحنية بأنها دالة منطقية.${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$والتي يكون لتحويل والش قيمة مطلقة ثابتة . الدوال المنحنية متساوية البعد عن جميع الدوال الأفينية، لذا يصعب تقريبها بنفس القدر باستخدام أي دالة أفينية.

أبسط الأمثلة على _{الدوال المنحنية} ، _{المكتوبة} بالصيغة الجبرية _{العادية} ، هي F ( x₁ , x₂ ₎ = x₁x₂ و G ( x₁ _, x₂ _, x₃ , x₄ ₎ = x₁x₂ ⊕ _{x₃x₄ .} ويستمر _هذا النمط _{: x₁x₂ ⊕} x₃x₄ ⊕ … ⊕ _{xₙ₋₁ ، حيث} xₙ دالة _منحنية .​_​​${\displaystyle \mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}$لكل عدد زوجي n ، ولكن هناك مجموعة واسعة من الدوال المنحنية الأخرى مع ازدياد n . ^{[ 5 ]} تُسمى متتالية القيم (−1) ^{f ( x )} ، حيث x ∈ Z ⁿ ₂ مرتبة ترتيبًا معجميًا ، متتالية منحنية ؛ وتتمتع الدوال المنحنية والمتتاليات المنحنية بخصائص متكافئة. في هذا الشكل ±1، يُمكن حساب تحويل والش بسهولة كما يلي:

${\displaystyle {\hat {f}}(a)=W\left(2^{n}\right)(-1)^{f(a)},}$

حيث W (2 ⁿ ) هي مصفوفة والش المرتبة ترتيبًا طبيعيًا ويتم التعامل مع التسلسل كمتجه عمودي . ^{[ 6 ]}

أثبت روثاوس أن الدوال المنحنية لا توجد إلا للأعداد الزوجية n ، وأنه بالنسبة للدالة المنحنية f ،${\displaystyle \left|{\hat {f}}(a)\right|=2^{n/2}}$لكل a ∈ Z ⁿ ₂ . ^{[ 4 ]} في الواقع،${\displaystyle {\hat {f}}(a)=2^{n/2}(-1)^{g(a)}}$حيث يكون المنحنى g منحنيًا أيضًا. في هذه الحالة،${\displaystyle {\hat {g}}(a)=2^{n/2}(-1)^{f(a)}}$لذلك، تُعتبر الدالتان f و g دالتين مزدوجتين . ^{[ 6 ]}

لكل دالة منحنية وزن هامينغ (عدد مرات أخذها القيمة 1) يساوي 2n⁻¹ ± ^{2n /2⁻¹ ، وهي في} الواقع تتطابق مع أي دالة خطية عند إحدى هاتين النقطتين. لذا، فإن ^{اللاخطية} للدالة f ( أقل عدد مرات تطابقها مع أي دالة خطية) هي 2n⁻¹ - ^{2n /2⁻¹ ، وهي} القيمة القصوى الممكنة. وعلى العكس، فإن أي دالة منطقية ذات لاخطية ^{2n⁻¹ -} 2n ^{/ 2⁻¹} هي دالة منحنية. [ ^{4 ] درجة} الدالة f في الصيغة الجبرية العادية (وتسمى الرتبة اللاخطية للدالة f ) ^هي على الأكثر n / 2 (لـ n > 2 ) . ^{[ 5 ]}

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

توجد عدة أنواع من الإنشاءات للدوال المنحنية. ^{[ 2 ]}

• الإنشاءات التوافقية: الإنشاءات التكرارية، إنشاء مايورانا-ماكفارلاند، الانتشار الجزئي، دوال ديلون ودوبيرتين المنحنية، دوال الحد الأدنى المنحنية، الدوال التكرارية المنحنية
• الإنشاءات الجبرية: الدوال المنحنية أحادية الحد ذات أسس Gold و Dillon و Kasami و Canteaut–Leander و Canteaut–Charpin–Kuyreghyan؛ دوال Niho المنحنية، إلخ.

في وقت مبكر من عام 1982، تم اكتشاف أن المتتاليات ذات الطول الأقصى القائمة على الدوال المنحنية تتمتع بخصائص الارتباط المتبادل والارتباط الذاتي التي تنافس تلك الخاصة برموز غولد ورموز كاسامي المستخدمة في تقنية CDMA . ^{[ 9 ]} لهذه المتتاليات تطبيقات عديدة في تقنيات الطيف المنتشر .

تُعدّ خصائص الدوال المنحنية ذات أهمية بالغة في التشفير الرقمي الحديث ، الذي يسعى إلى إخفاء العلاقات بين المدخلات والمخرجات. في عام ١٩٨٨، أدرك فوريه أن تحويل والش للدالة يُمكن استخدامه لإثبات استيفائها لمعيار الانهيار الصارم (SAC) والتعميمات ذات الرتب الأعلى، وأوصى باستخدام هذه الأداة لاختيار المرشحين لصناديق الاستبدال ( S-boxes) الجيدة التي تحقق انتشارًا شبه مثالي . ^{[ ١٠ ]} في الواقع، الدوال التي تستوفي معيار الانهيار الصارم (SAC) لأعلى رتبة ممكنة هي دائمًا دوال منحنية. ^{[ ١١ ]} علاوة على ذلك، فإن الدوال المنحنية بعيدة كل البعد عن امتلاك ما يُسمى بالبنى الخطية ، أي المتجهات غير الصفرية a بحيث يكون f ( x + a ) + f ( x ) ثابتًا. في لغة التحليل التفاضلي للتشفير (التي ظهرت بعد اكتشاف هذه الخاصية)، فإن مشتقة الدالة المنحنية f عند كل نقطة غير صفرية a (أي f( a ) = f ( x + _a ) + f ( x ) ) هي دالة منطقية متوازنة ، تأخذ كل قيمة من قيمها نصف الوقت بالضبط. تُسمى هذه الخاصية باللاخطية التامة . ^{[ 5 ]}

بالنظر إلى خصائص الانتشار الجيدة هذه، ومقاومتها شبه التامة للتحليل التشفيري التفاضلي، ومقاومتها بحكم التعريف للتحليل التشفيري الخطي ، قد تبدو الدوال المنحنية في البداية الخيار الأمثل للدوال التشفيرية الآمنة مثل صناديق الاستبدال (S-boxes). لكن عيبها الجوهري يكمن في عدم توازنها. على وجه الخصوص، لا يمكن إنشاء صندوق استبدال قابل للعكس مباشرةً من الدوال المنحنية، كما أن تشفير التدفق باستخدام دالة دمج منحنية يكون عرضةً لهجوم الارتباط . بدلاً من ذلك، يمكن البدء بدالة منحنية وإضافة قيم مناسبة عشوائيًا حتى يصبح الناتج متوازنًا. لا تزال الدالة المعدلة تتمتع بدرجة عالية من اللاخطية، وبما أن هذه الدوال نادرة جدًا، فإن العملية ستكون أسرع بكثير من البحث الشامل. ^{[ 5 ]} لكن الدوال المنتجة بهذه الطريقة قد تفقد خصائص مرغوبة أخرى، بل قد تفشل في تلبية شرط التوازن الآمن (SAC) - لذا فإن الاختبار الدقيق ضروري. ^{[ 11 ]} وقد عمل عدد من خبراء التشفير على تقنيات لتوليد دوال متوازنة تحافظ على أكبر قدر ممكن من الخصائص التشفيرية الجيدة للدوال المنحنية. ^{[ 12 ] [ 13 ] [ 14 ]}

تم دمج بعض هذه الأبحاث النظرية في خوارزميات تشفير حقيقية. تستخدم عملية تصميم CAST ، التي استخدمها كارلايل آدامز وستافورد تافاريس لإنشاء صناديق الاستبدال (S-boxes) لتشفير الكتل CAST-128 و CAST-256 ، دوالًا منحنية. ^{[ 14 ]} تستخدم دالة التجزئة التشفيرية HAVAL دوالًا منطقية مبنية من ممثلين لجميع فئات التكافؤ الأربع للدوال المنحنية على ستة متغيرات. ^{[ 15 ]} يستخدم تشفير التدفق Grain مسجل إزاحة خطي غير خطي ذو تغذية راجعة متعددة الحدود، مصمم ليكون مجموع دالة منحنية ودالة خطية. ^{[ 16 ]}

تم وصف أكثر من 25 تعميمًا مختلفًا للدوال المنحنية في دراسة توكاريفا لعام 2015. ^{[ ٢ ]} توجد تعميمات جبرية ( دوال بنت ذات قيم q ، ودوال بنت من الرتبة p ، ودوال بنت على حقل منتهٍ، ودوال بنت البولية المعممة لشميدت، ودوال بنت من زمرة أبيلية منتهية إلى مجموعة الأعداد المركبة على دائرة الوحدة، ودوال بنت من زمرة أبيلية منتهية إلى زمرة أبيلية منتهية، ودوال بنت غير أبيلية، ودوال بنت المتجهة من الرتبة G، ودوال بنت متعددة الأبعاد على زمرة أبيلية منتهية)، وتعميمات توافقية (دوال بنت متناظرة، ودوال بنت متجانسة، ودوال بنت متناظرة دورانيًا، ودوال بنت عادية، ودوال بنت ذاتية التناظر ومضادة ذاتية التناظر، ودوال بنت معرفة جزئيًا، ودوال مستوية، ودوال بنت من الرتبة Z، ودوال بنت كمومية)، وتعميمات تشفيرية (دوال بنت شبه، ودوال بنت متوازنة، ودوال بنت جزئيًا، ودوال بنت فائقة، ودوال بنت من رتبة أعلى، ودوال بنت من الرتبة k ). الوظائف).

أكثر أنواع الدوال المنحنية المعممة شيوعاً هي من النوع mod m ،${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$بحيث

${\displaystyle {\hat {f}}(a)=\sum _{x\in \mathbb {Z} _{m}^{n}}e^{{\frac {2\pi i}{m}}(f(x)-a\cdot x)}}$

لها قيمة مطلقة ثابتة m ^{n /2} . دوال غير خطية تمامًا${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$تُعرف الدوال المنحنية المعممة بأنها تلك التي تأخذ فيها الدالة f(x + a) - f(a) القيمة m لكل n - 1 مرة، وذلك لكل قيمة غير صفرية a . إذا كان m عددًا أوليًا ، فإن ^{العكس صحيح} . في معظم الحالات ، يُؤخذ العدد الأولي m فقط في الاعتبار. بالنسبة للأعداد الأولية الفردية m ، توجد دوال منحنية معممة لكل عدد موجب n ، سواء كان زوجيًا أو فرديًا. تتمتع هذه الدوال بالعديد من الخصائص التشفيرية الجيدة نفسها التي تتمتع بها الدوال المنحنية الثنائية. ^{[ 17 ] [ 18 ]}

الدوال شبه المنحنية هي نظير فردي للدوال المنحنية. الدالة شبه المنحنية هي${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$حيث n عدد فردي، بحيث${\displaystyle \left|{\hat {f}}\right|}$لا تأخذ إلا القيمتين 0 و m ^{( n +1)/2} . كما أنها تتمتع بخصائص تشفيرية جيدة، وبعضها متوازن، حيث تأخذ جميع القيم الممكنة بنفس القدر من التكرار. ^{[ 19 ]}

تشكل الدوال المنحنية جزئيًا فئة واسعة تُحدد بشرط على تحويل والش ودوال الارتباط الذاتي. جميع الدوال الأفينية والمنحنية هي دوال منحنية جزئيًا. وهذه بدورها فئة فرعية مناسبة من الدوال المستوية . ^{[ 20 ]}

تكمن فكرة الدوال فائقة الانحناء في تعظيم أقصر مسافة ممكنة إلى جميع الدوال البوليانية الناتجة عن أحاديات تقابلية على الحقل المنتهي GF(2n ⁾ ، وليس فقط الدوال الأفينية. بالنسبة لهذه الدوال، تكون هذه المسافة ثابتة، مما قد يجعلها مقاومة لهجمات الاستيفاء .

وقد أُطلقت أسماء أخرى ذات صلة على فئات الوظائف ذات الأهمية في مجال التشفير${\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}^{n}}$مثل الدوال شبه المنحنية والدوال الملتوية . ورغم أنها ليست دوال منحنية بحد ذاتها (فهي ليست حتى دوال منطقية)، إلا أنها ترتبط ارتباطًا وثيقًا بالدوال المنحنية وتتمتع بخصائص غير خطية جيدة.

• مناعة الارتباط

• سي. كارليت (مايو 1993). فئتان جديدتان من الدوال المنحنية . يورو كريبت 93. الصفحات 77-101 . 
• ج. سيبري؛ إكس. تشانغ (مارس 1994). "إنشاء دوال منحنية من دالتين منحنيتين معروفتين". المجلة الأسترالية الآسيوية للتوافقية . 9 : 21-35 . CiteSeerX 10.1.1.55.531 . ISSN 1034-4942 .  
• كولبورن، تشارلز ج .؛ دينيتز، جيفري هـ. (2006). دليل التصاميم التوافقية (  الطبعة الثانية). مطبعة سي آر سي . الصفحات 337-339 . رقم ISBN  978-1-58488-506-1.
• كوسيك، تي دبليو؛ ستانيكا، ب. (2009). الدوال المنطقية المشفرة وتطبيقاتها . دار النشر الأكاديمية. ISBN 9780123748904.