کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4944414 | 1437993 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient probabilistic algorithm for estimating the algebraic properties of Boolean functions for large n
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Although several methods for estimating the resistance of a random Boolean function against (fast) algebraic attacks were proposed, these methods are usually infeasible in practice for relatively large number of input variables n (for instance n ⥠30) due to increased computational complexity. An efficient estimation of the resistance of Boolean functions, with relatively large number of inputs n, against (fast) algebraic attacks appears to be a rather difficult task. In this paper, the concept of partial linear relations decomposition is introduced, which decomposes any given nonlinear Boolean function into many linear (affine) subfunctions by using the disjoint sets of input variables. Based on this result, a general probabilistic decomposition algorithm for nonlinear Boolean functions is presented which gives a new framework for estimating the resistance of Boolean function against (fast) algebraic attacks. It is shown that our new probabilistic method gives very tight estimates (lower and upper bound) and it only requires about O(n22n) operations for a random Boolean function with n variables, thus having much less time complexity than previously known algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 402, September 2017, Pages 91-104
Journal: Information Sciences - Volume 402, September 2017, Pages 91-104
نویسندگان
Yongzhuang Wei, Enes Pasalic, Fengrong Zhang, Samir HodžiÄ,