检索结果-内蒙古大学图书馆

multiplicative complexity of vector valued Boolean functions

THEORETICAL COMPUTER SCIENCE 2018年 720卷 36-46页

作者： Boyar, Joan Find, Magnus Gausdal Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark

We consider the multiplicative complexity of Boolean functions with multiple bits of output, studying how large a multiplicative complexity is necessary and sufficient to provide a desired nonlinearity. For so-called Sigma Pi Sigma circuits, we show that there is a tight connection between error correcting codes and circuits computing functions with high nonlinearity. Combining this with known coding theory results, we show that functions with n inputs and n outputs with the highest possible nonlinearity must have at least 2.32n AND gates. We further show that one cannot prove stronger lower bounds by only appealing to the nonlinearity of a function;we show a bilinear circuit computing a function with almost optimal nonlinearity with the number of AND gates being exactly the length of such a shortest code. Additionally we provide a function which, for general circuits, has multiplicative complexity at least 2n - 3. Finally we study the multiplicative complexity of "almost all" functions. We show that every function with n bits of input and m bits of output can be computed using at most 2.5(1 + o(1))root m2(n) AND gates. (C) 2018 Elsevier B.V. All rights reserved.

关键词： multiplicative complexity Nonlinearity Circuits Error correcting codes

来源：评论

学校读者我要写书评

暂无评论

multiplicative complexity OF THE TWO-DIMENSIONAL DISCRETE FOURIER-TRANSFORM DFT (2N, 2)

引用

ELECTRONICS LETTERS 1988年第9期24卷 559-561页

作者： MA, W YANG, D Department of Radio Engineering South China Institute of Technology Guangzhou China

We show that the two-dimensional discrete Fourier transform DFT (2n; 2) can be transformed into a series of distinct second versions of the discrete cosine transform DCT. As a result of the minimal number of real multiplications over the field Q to compute the length 2n second version DCT, we derive the minimum number of real multiplications over the field Q necessary to compute a two-dimensional discrete Fourier transform for 2n × 2n real input data.

关键词： multiplicative complexity fast Fourier transforms discrete cosine transform Other numerical methods real multiplications minimal number two-dimensional discrete Fourier transform

来源：评论

学校读者我要写书评

暂无评论

multiplicative complexity of XOR Based Regular Functions

引用

IEEE TRANSACTIONS ON COMPUTERS 2022年第11期71卷 2927-2939页

作者： Bernasconi, Anna Cimato, Stelvio Ciriani, Valentina Molteni, Maria Chiara Univ Pisa Dept Comp Sci I-56126 Pisa Italy Univ Milan Dept Comp Sci I-20122 Milan Italy

XOR-AND Graphs (XAGs) are an enrichment of the classical AND-Inverter Graphs (AIGs) with XOR nodes. In particular, XAGs are networks composed by ANDs, XORs, and inverters. Besides several emerging technologies applications, XAGs are often exploited in cryptography-related applications based on the multiplicative complexity of a Boolean function. The multiplicative complexity of a function is the minimum number of AND gates (i.e., multiplications) that are sufficient to represent the function over the basis {AND, XOR, NOT}. In fact, the minimization of the number of AND gates is important for high-level cryptography protocols such as secure multiparty computation, where processing AND gates is more expensive than processing XOR gates. Moreover, it is an indicator of the degree of vulnerability of the circuit, as a small number of AND gates corresponds to a high vulnerability to algebraic attacks. In this paper we study the multiplicative complexity of Boolean functions characterized by two particular regularities, called autosymmetry and D-reducibility. Moreover, we exploit these regularities for decreasing the number of AND nodes in XAGs. The experimental results validate the proposed approaches.

关键词： complexity theory Logic gates Cryptography Boolean functions Protocols Minimization Inverters Logic synthesis multiplicative complexity XOR-AND graphs regular Boolean functions

来源：评论

学校读者我要写书评

暂无评论

multiplicative complexity of bijective 4 x 4 S-boxes

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2014年第3期6卷 255-277页

作者： Zajac, Pavol Jokay, Matus FEI STU Inst Comp Sci & Math Bratislava 81219 Slovakia

multiplicative complexity of S-box is the minimum number of 2-input AND-gates required to implement the S-box in AND, XOR, NOT logic. We show that under an affine equivalence there is only a single class of bijective n x n S-boxes with multiplicative complexity 1. Furthermore, we show that each bijective 4 x 4 S-box has multiplicative complexity at most 5. Finally, we refine the bounds on the multiplicative complexity of each affine class of bijective 4 x 4 S-boxes.

关键词： S-box multiplicative complexity Affine equivalence

来源：评论

学校读者我要写书评

暂无评论

A lower bound for differential uniformity by multiplicative complexity & bijective functions of multiplicative complexity 1 over finite fields

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2024年第2期16卷 285-308页

作者： Steiner, Matthias Johann Alpen Adria Univ Klagenfurt Cybersecur Univ Str 65-67 A-9020 Klagenfurt Am Worthersee Austria

The multiplicative complexity of an S-box over a finite field is the minimum number of multiplications needed to implement the S-box as an arithmetic circuit. In this paper we fully characterize bijective S-boxes with multiplicative complexity 1 up to affine equivalence over any finite field. We show that under affine equivalence in odd characteristic there are two classes of bijective functions and in even characteristic there are three classes of bijective functions with multiplicative complexity 1. Moreover, in (Jeon et al., Cryptogr. Commun., 14(4), 849-874 (2022)) A-boxes where introduced to lower bound the differential uniformity of an S-box over F-2(n) via its multiplicative complexity. We generalize this concept to arbitrary finite fields. In particular, we show that the differential uniformity of a (n, m)-S-box over F(q )is at least q(n-l), where [(n-1)/(2)] +l is the multiplicative complexity of the S-box.

关键词： Arithmetic circuit multiplicative complexity M-box S-box Differential uniformity

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

引用

DESIGNS CODES AND CRYPTOGRAPHY 2017年第1-2期82卷 43-56页

作者： Zajac, Pavol Slovak Univ Technol Bratislava Ilkovicova 3 Bratislava 81219 Slovakia

Lightweight cipher designs try to minimize the implementation complexity of the cipher while maintaining some specified security level. Using only a small number of AND gates lowers the implementation costs, and enables easier protections against side-channel attacks. In our paper we study the connection between the number of AND gates (multiplicative complexity) and the complexity of algebraic attacks. We model the encryption with multiple right-hand sides (MRHS) equations. The resulting equation system is transformed into a syndrome decoding problem. The complexity of the decoding problem depends on the number of AND gates, and on the relative number of known output bits with respect to the number of unknown key bits. This allows us to apply results from coding theory, and to explicitly connect the complexity of the algebraic cryptanalysis to the multiplicative complexity of the cipher. This means that we can provide asymptotic upper bounds on the complexity of algebraic attacks on selected families of ciphers based on the hardness of the decoding problem.

关键词： Algebraic cryptanalysis multiplicative complexity Lightweight cryptography Decoding problem

来源：评论

学校读者我要写书评

暂无评论

On the multiplicative complexity of the inversion and division of Hamiltonian quaternions

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2002年第2期2卷 191-199页

作者： Bläser, M Kirrinnis, P Lauer, D Med Univ Lubeck Inst Theoret Informat D-23560 Lubeck Germany Univ Bonn Inst Informat 2 D-53117 Bonn Germany

The multiplicative complexity of a finite set of rational functions is the number of essential multiplications and divisions that are necessary and sufficient to compute these rational functions. We prove that the multiplicative complexity of inversion in the division algebra H of Hamiltonian quaternions over the reals, that is, the multiplicative complexity of the coordinates of the inverse of a generic element from H, is exactly eight. Furthermore, we show that the multiplicative complexity of the left and right division of Hamiltonian quaternions is at least eleven.

关键词： multiplicative complexity Hamiltonian quaternions

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on the multiplicative complexity of symmetric Boolean functions

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2019年第6期11卷 1339-1362页

作者： Brandao, Luis T. A. N. Calik, Cagdas Sonmez Turan, Meltem Peralta, Rene NIST Cryptog Technol Grp 100 Bur Dr Gaithersburg MD 20899 USA

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195-201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43-57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1-3), 223-246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions Sigma kn and counting functions Ekn with up to n =25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric Sigma 48 and the counting E48 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.

关键词： Symmetric Boolean functions multiplicative complexity Upper bounds Logic minimization 94A60 06E30

来源：评论

学校读者我要写书评

暂无评论

Differential uniformity and linearity of S-boxes by multiplicative complexity

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2022年第4期14卷 849-874页

作者： Jeon, Yongjin Baek, Seungjun Kim, Hangi Kim, Giyoon Kim, Jongsung Kookmin Univ Dept Financial Informat Secur Seoul South Korea Kookmin Univ Dept Informat Secur Cryptol & Math Dept Financial Informat Secur Seoul South Korea

A cryptographic primitive with low multiplicative complexity (MC) makes various applications efficient, but it may lead to cryptographic vulnerabilities. To find a trade-off between cryptographic resistance and MC, we propose a new tool called A-box, which is constructed using AND gates. In this paper, we prove several important properties of A-boxes, which provide the theoretical lower bounds of differential uniformity and linearity of corresponding S-boxes by MC. Specifically, we show that the differential uniformity (resp. linearity) of an (n, m)-bit S-box is at least 2(n- l), where its MC is left perpendicular n-1/2right perpendicular + l (resp. m - 1 + l). Furthermore, we develop an algorithm to find S-boxes with differential uniformity equal to the bounds with respect to their MC. We improve the algorithm previously proposed by Zajac and J ' okay (Cryptogr. Commun. 6(3), 255-277, 2014), which is applicable only to S-boxes of size lower than 5 bits, whereas ours can run on larger-sized S-boxes. We found a bijective (8, 8)-bit S-box with differential uniformity 16, linearity 128, and 8 nonlinear gates: this has better cryptographic security than the SKINNY S-box with differential uniformity 64, linearity 128, and 8 nonlinear gates. We believe that our results provide a better understanding of the relationship between cryptographic resistance and MC of S-boxes.

关键词： A-box S-box multiplicative complexity Differential uniformity Linearity

来源：评论

学校读者我要写书评

暂无评论

A tree search algorithm for low multiplicative complexity logic design

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2018年 83卷 132-143页

作者： Tay, Jia Jun Wong, M. L. Dennis Wong, Ming Ming Zhang, Cishen Hijazin, Ismat Swinburne Univ Technol Fac Engn Comp & Sci Sarawak Campus Sarawak Malaysia Heriot Watt Univ Malaysia Putrajaya Malaysia Nanyang Technol Univ Sch Comp Sci & Engn Nanyang Ave Singapore Singapore Swinburne Univ Technol Fac Sci Engn & Technol Hawthorn Vic Australia

Low multiplicative complexity logic design is a useful heuristic to achieve low gate count implementation of logic circuit. In this work, we propose a deterministic approach based on the currently known lower and upper bounds of multiplicative complexity for logic minimization problems with not more than five inputs. The proposed tree search algorithm achieves circuit minimization through decomposition of Positive Polarity Reed-Muller expressions. This approach allows low multiplicative complexity logic design to be executed without the consistency issue associated with the randomized approach in the original algorithm. Experimental results show over 85% improvement in computation time compared to solving the same problems using the previous randomized approach. We also demonstrate that the quality of results produce by the proposed algorithm is comparable, and in some cases, better than the results reported in previous works using the same heuristic. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Logic design multiplicative complexity Function decomposition Tree search algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：