Changhui CHEN Haibin KAN Jie PENG Li WANG
Permutation polynomials have been studied for a long time and have important applications in cryptography, coding theory and combinatorial designs. In this paper, by means of the multivariate method and the resultant, we propose four new classes of permutation quadrinomials over 𝔽q3, where q is a prime power. We also show that they are not quasi-multiplicative equivalent to known ones. Moreover, we compare their differential uniformity with that of some known classes of permutation trinomials for some small q.
Changhui CHEN Haibin KAN Jie PENG Li WANG
Permutation polynomials have important applications in cryptography, coding theory and combinatorial designs. In this letter, we construct four classes of permutation polynomials over 𝔽2n × 𝔽2n, where 𝔽2n is the finite field with 2n elements.
Yuuki AOIKE Masashi KIYOMI Yasuaki KOBAYASHI Yota OTACHI
In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely LONGEST INCREASING SUBSEQUENCE RECONFIGURATION. We give a polynomial-time algorithm for deciding whether there is a reconfiguration sequence between two longest increasing subsequences in a sequence. This implies that INDEPENDENT SET RECONFIGURATION and TOKEN SLIDING are polynomial-time solvable on permutation graphs, provided that the input two independent sets are largest among all independent sets in the input graph. We also consider a special case, where the underlying permutation graph of an input sequence is bipartite. In this case, we give a polynomial-time algorithm for finding a shortest reconfiguration sequence (if it exists).
Jing LIANG Ke LI Kunjie YU Caitong YUE Yaxin LI Hui SONG
The selection of mutation strategy greatly affects the performance of differential evolution algorithm (DE). For different types of optimization problems, different mutation strategies should be selected. How to choose a suitable mutation strategy for different problems is a challenging task. To deal with this challenge, this paper proposes a novel DE algorithm based on local fitness landscape, called FLIDE. In the proposed method, fitness landscape information is obtained to guide the selection of mutation operators. In this way, different problems can be solved with proper evolutionary mechanisms. Moreover, a population adjustment method is used to balance the search ability and population diversity. On one hand, the diversity of the population in the early stage is enhanced with a relative large population. One the other hand, the computational cost is reduced in the later stage with a relative small population. The evolutionary information is utilized as much as possible to guide the search direction. The proposed method is compared with five popular algorithms on 30 test functions with different characteristics. Experimental results show that the proposed FLIDE is more effective on problems with high dimensions.
Shigenori KINJO Takayuki GAMOH Masaaki YAMANAKA
A new zero-forcing block diagonalization (ZF-BD) scheme that enables both a more simplified ZF-BD and further increase in sum rate of MU-MIMO channels is proposed in this paper. The proposed scheme provides the improvement in BER performance for equivalent SU-MIMO channels. The proposed scheme consists of two components. First, a permuted channel matrix (PCM), which is given by moving the submatrix related to a target user to the bottom of a downlink MIMO channel matrix, is newly defined to obtain a precoding matrix for ZF-BD. Executing QR decomposition alone for a given PCM provides null space for the target user. Second, a partial MSQRD (PMSQRD) algorithm, which adopts MSQRD only for a target user to provide improvement in bit rate and BER performance for the user, is proposed. Some numerical simulations are performed, and the results show improvement in sum rate performance of the total system. In addition, appropriate bit allocation improves the bit error rate (BER) performance in each equivalent SU-MIMO channel. A successive interference cancellation is applied to achieve further improvement in BER performance of user terminals.
Permutation codes are error-correcting codes over symmetric groups. We focus on permutation codes under Chebyshev (l∞) distance. A permutation code invented by Kløve et al. is of length n, size 2n-d and, minimum distance d. We denote the code by φn,d. This code is the largest known code of length n and minimum Chebyshev distance d > n/2 so far, to the best of the authors knowledge. They also devised efficient encoding and hard-decision decoding (HDD) algorithms that outperform the bounded distance decoding. In this paper, we derive a tight upper bound of decoding error probability of HDD. By factor graph formalization, we derive an efficient maximum a-posterior probability decoding algorithm for φn,d. We explore concatenating permutation codes of φn,d=0 with binary outer codes for more robust error correction. A naturally induced pseudo distance over binary outer codes successfully characterizes Chebyshev distance of concatenated permutation codes. Using this distance, we upper-bound the minimum Chebyshev distance of concatenated codes. We discover how to concatenate binary linear codes to achieve the upper bound. We derive the distance distribution of concatenated permutation codes with random outer codes. We demonstrate that the sum-product decoding performance of concatenated codes with outer low-density parity-check codes outperforms conventional schemes.
Jaeseong JEONG Chang Heon KIM Namhun KOO Soonhak KWON Sumin LEE
The differential uniformity, the boomerang uniformity, and the extended Walsh spectrum etc are important parameters to evaluate the security of S (substitution)-box. In this paper, we introduce efficient formulas to compute these cryptographic parameters of permutation polynomials of the form xrh(x(2n-1)/d) over a finite field of q=2n elements, where r is a positive integer and d is a positive divisor of 2n-1. The computational cost of those formulas is proportional to d. We investigate differentially 4-uniform permutation polynomials of the form xrh(x(2n-1)/3) and compute the boomerang spectrum and the extended Walsh spectrum of them using the suggested formulas when 6≤n≤12 is even, where d=3 is the smallest nontrivial d for even n. We also investigate the differential uniformity of some permutation polynomials introduced in some recent papers for the case d=2n/2+1.
Kwon Kham SAI Giovanni VIGLIETTA Ryuhei UEHARA
We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We call this a cyclic shift puzzle. We first investigate a large class of graphs, which generalizes several classic cyclic shift puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.
Kosei SAKAMOTO Kazuhiko MINEMATSU Nao SHIBATA Maki SHIGERI Hiroyasu KUBO Takanori ISOBE
In spite of the research for a linear layer of Type-2 Generalized Feistel Network (Type-2 GFN) over more than 10 years, finding a good 32-branch permutation for Type-2 GFN is still a very hard task due to a huge search space. In terms of the diffusion property, Suzaki and Minematsu investigated the required number of rounds to achieve the full diffusion when the branch number is up to 16. After that, Derbez et al. presented a class of 32-branch permutations that achieves the 9-round full diffusion and they prove that this is optimal. However, this class is not suitable to be used in Type-2 GFN because it requires a large number of rounds to ensure a sufficient number of active S-boxes. In this paper, we present how to find a good class of 32-branch permutations for Type-2 GFN. To achieve this goal, we convert Type-2 GFN into a LBlock-like structure, and then we evaluate the diffusion property and the resistance against major attacks, such as differential, linear, impossible differential and integral attacks by an MILP. As a result, we present a good class of 32-branch permutations that achieves the 10-round full diffusion, ensures differentially/linearly active S-boxes of 66 at 19 round, and has the 18/20-round impossible differential/integral distinguisher, respectively. The 32-branch permutation used in WARP was chosen among this class.
You GAO Yun-Fei YAO Lin-Zhi SHEN
Permutation polynomials over finite fields have been widely studied due to their important applications in mathematics and cryptography. In recent years, 2-to-1 mappings over finite fields were proposed to build almost perfect nonlinear functions, bent functions, and the semi-bent functions. In this paper, we generalize the 2-to-1 mappings to m-to-1 mappings, including their construction methods. Some applications of m-to-1 mappings are also discussed.
Yanjun LI Haibin KAN Jie PENG Chik How TAN Baixiang LIU
Permutation polynomials and their compositional inverses are crucial for construction of Maiorana-McFarland bent functions and their dual functions, which have the optimal nonlinearity for resisting against the linear attack on block ciphers and on stream ciphers. In this letter, we give the explicit compositional inverse of the permutation binomial $f(z)=z^{2^{r}+2}+alpha zinmathbb{F}_{2^{2r}}[z]$. Based on that, we obtain the dual of monomial bent function $f(x)={ m Tr}_1^{4r}(x^{2^{2r}+2^{r+1}+1})$. Our result suggests that the dual of f is not a monomial any more, and it is not always EA-equivalent to f.
Computing the weight distribution of a code is a challenging problem in coding theory. In this paper, the weight distributions of (256, k) extended binary primitive BCH codes with k≤71 and k≥187 are given. The weight distributions of the codes with k≤63 and k≥207 have already been obtained in our previous work. Affine permutation and trellis structure are used to reduce the computing time. Computer programs in C language which use recent CPU instructions, such as SIMD, are developed. These programs can be deployed even on an entry model workstation to obtain the new results in this paper.
Radomir S. STANKOVIĆ Milena STANKOVIĆ Claudio MORAGA Jaakko T. ASTOLA
Binary bent functions have a strictly specified number of non-zero values. In the same way, ternary bent functions satisfy certain requirements on the elements of their value vectors. These requirements can be used to specify six classes of ternary bent functions. Classes are mutually related by encoding of function values. Given a basic ternary bent function, other functions in the same class can be constructed by permutation matrices having a block structure similar to that of the factor matrices appearing in the Good-Thomas decomposition of Cooley-Tukey Fast Fourier transform and related algorithms.
Yi LIU Wei QIN Jinhui ZHANG Mengmeng LI Qibin ZHENG Jichuan WANG
Multi-objective evolutionary algorithms are widely used in many engineering optimization problems and artificial intelligence applications. Ant lion optimizer is an outstanding evolutionary method, but two issues need to be solved to extend it to the multi-objective optimization field, one is how to update the Pareto archive, and the other is how to choose elite and ant lions from archive. We develop a novel multi-objective variant of ant lion optimizer in this paper. A new measure combining Pareto dominance relation and distance information of individuals is put forward and used to tackle the first issue. The concept of time weight is developed to handle the second problem. Besides, mutation operation is adopted on solutions in middle part of archive to further improve its performance. Eleven functions, other four algorithms and four indicators are taken to evaluate the new method. The results show that proposed algorithm has better performance and lower time complexity.
Dong-Ah LEE Eui-Sub KIM Junbeom YOO
Two structural coverage criteria, toggle coverage and modified condition/decision coverage, for FBD (Function Block Diagram) simulation are proposed in the previous study. This paper empirically evaluates how effective the coverage criteria are to detect faults in an FBD program using the mutation analysis.
Mengmeng LI Xiaoguang REN Yanzhen WANG Wei QIN Yi LIU
Feature selection is important for learning algorithms, and it is still an open problem. Antlion optimizer is an excellent nature inspired method, but it doesn't work well for feature selection. This paper proposes a hybrid approach called Ant-Antlion Optimizer which combines advantages of antlion's smart behavior of antlion optimizer and ant's powerful searching movement of ant colony optimization. A mutation operator is also adopted to strengthen exploration ability. Comprehensive experiments by binary classification problems show that the proposed algorithm is superiority to other state-of-art methods on four performance indicators.
Jiaqi ZHAI Jian LIU Lusheng CHEN
Aggregate signature (AS) schemes enable anyone to compress signatures under different keys into one. In sequential aggregate signature (SAS) schemes, the aggregate signature is computed incrementally by the sighers. Several trapdoor-permutation-based SAS have been proposed. In this paper, we give a constructions of SAS based on the first SAS scheme with lazy verification proposed by Brogle et al. in ASIACRYPT 2012. In Brogle et al.'s scheme, the size of the aggregate signature is linear of the number of the signers. In our scheme, the aggregate signature has constant length which satisfies the original ideal of compressing the size of signatures.
In this paper, we propose a notion for high-dimensional generalizations of mutually orthogonal Latin squares (MOLS) and mutually orthogonal diagonal Latin squares (MODLS), called mutually dimensionally orthogonal d-cubes (MOC) and mutually dimensionally orthogonal diagonal d-cubes (MODC). Systematic constructions for MOC and MODC by using polynomials over finite fields are investigated. In particular, for 3-dimensional cubes, the results for the maximum possible number of MODC are improved by adopting the proposed construction.
Takanori ISOBE Kyoji SHIBUTANI
In this paper, we explore the security of single-key Even-Mansour ciphers against key-recovery attacks. First, we introduce a simple key-recovery attack using key relations on an n-bit r-round single-key Even-Mansour cipher (r-SEM). This attack is feasible with queries of DTr=O(2rn) and $2^{rac{2r}{r + 1}n}$ memory accesses, which is $2^{rac{1}{r + 1}n}$ times smaller than the previous generic attacks on r-SEM, where D and T are the number of queries to the encryption function EK and the internal permutation P, respectively. Next, we further reduce the time complexity of the key recovery attack on 2-SEM by a start-in-the-middle approach. This is the first attack that is more efficient than an exhaustive key search while keeping the query bound of DT2=O(22n). Finally, we leverage the start-in-the-middle approach to directly improve the previous attacks on 2-SEM by Dinur et al., which exploit t-way collisions of the underlying function. Our improved attacks do not keep the bound of DT2=O(22n), but are the most time-efficient attacks among the existing ones. For n=64, 128 and 256, our attack is feasible with the time complexity of about $2^{n} cdot rac{1}{2 n}$ in the chosen-plaintext model, while Dinur et al.'s attack requires $2^{n} cdot rac{{ m log}(n)}{ n} $ in the known-plaintext model.
Minoru KURIBAYASHI Takuya FUKUSHIMA Nobuo FUNABIKI
The spaces between words and paragraphs are popular places for embedding data in data hiding techniques for text documents. Due to the low redundancy in text documents, the payload is limited to be small. As each bit of data is independently inserted into specific spaces in conventional methods, a malicious party may be able to modify the data without causing serious visible distortions. In this paper, we regard a collection of space lengths as a one-dimensional feature vector and embed watermark into its frequency components. To keep the secrecy of the embedded information, a random permutation and dither modulation are introduced in the operation. Furthermore, robustness against additive noise is enhanced by controlling the payload. In the proposed method, through experiments, we evaluated the trade-off among payload, distortion, and robustness.