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.

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).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

We explore ways to optimize online, permutation-based authenticated encryption (AE) schemes for lightweight applications. The lightweight applications demand that AE schemes operate in resource-constrained environments, which raise two issues: 1) implementation costs must be low, and 2) ensuring proper use of a nonce is difficult due to its small size and lack of randomness. Regarding the implementation costs, recently it has been recognized that permutation-based (rather than block-cipher-based) schemes frequently show advantages. However, regarding the security under nonce misuse, the standard permutation-based duplex construction cannot ensure confidentiality. There exists one permutation-based scheme named APE which offers certain robustness against nonce misuse. Unfortunately, the APE construction has several drawbacks such as ciphertext expansion and bidirectional permutation circuits. The ciphertext expansion would require more bandwidth, and the bidirectional circuits would require a larger hardware footprint. In this paper, we propose new constructions of online permutation-based AE that require less bandwidth, a smaller hardware footprint and lower computational costs. We provide security proofs for the new constructions, demonstrating that they are as secure as the APE construction.

We propose new key recovery attacks on the two-round single-key n-bit Even-Mansour ciphers (2SEM) that are secure up to 22n/3 queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 245 known plaintexts to 226 chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 262, the required data is further reduced to 28, and DT=270, where DT is the product of data and time complexities. We show that our data-optimized attack requires DT=2n+6 in general cases. Since the proved lower bound on DT for the single-key one-round n-bit Even-Mansour ciphers is 2n, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.

Generation of secure signatures suitable for spread-spectrum video watermarking is proposed. The method embeds a message, which is a two-dimensional binary pattern, into a three-dimensional volume, such as video, by addition of a signature. The message can be a mark or a logo indicating the copyright information. The signature is generated by shuffling or permuting random matrices along the third or time axis so that the message is extracted when they are accumulated after demodulation by the correct key. In this way, a message is hidden in the signature having equal probability of decoding any variation of the message, where the key is used to determine which one to extract. Security of the proposed method, stemming from the permutation, is evaluated as resistance to blind estimation of secret information. The matrix-based permutation allows the message to survive the spatial down-sampling without sacrificing the security. The downside of the proposed method is that it needs more data or frames to decode a reliable information compared to the conventional spread-spectrum modulation. However this is minimized by segmenting the matrices and applying permutation to sub-matrices independently. Message detectability is theoretically analyzed. Superiority of our method in terms of robustness to blind message estimation and down-sampling is verified experimentally.

This paper proposes a block-permutation-based encryption (BPBE) scheme for the encryption-then-compression (ETC) system that enhances the color scrambling. A BPBE image can be obtained through four processes, positional scrambling, block rotation/flip, negative-positive transformation, and color component shuffling, after dividing the original image into multiple blocks. The proposed scheme scrambles the R, G, and B components independently in positional scrambling, block rotation/flip, and negative-positive transformation, by assigning different keys to each color component. The conventional scheme considers the compression efficiency using JPEG and JPEG 2000, which need a color conversion before the compression process by default. Therefore, the conventional scheme scrambles the color components identically in each process. In contrast, the proposed scheme takes into account the RGB-based compression, such as JPEG-LS, and thus can increase the extent of the scrambling. The resilience against jigsaw puzzle solver (JPS) can consequently be increased owing to the wider color distribution of the BPBE image. Additionally, the key space for resilience against brute-force attacks has also been expanded exponentially. Furthermore, the proposed scheme can maintain the JPEG-LS compression efficiency compared to the conventional scheme. We confirm the effectiveness of the proposed scheme by experiments and analyses.

Many linear codes with two or three weights have recently been constructed due to their applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. In this paper, two classes of p-ary linear codes with two or three weights are presented. The first class of linear codes with two or three weights is obtained from a certain non-quadratic function. The second class of linear codes with two weights is obtained from the images of a certain function on $mathbb{F}_{p^m}$. In some cases, the resulted linear codes are optimal in the sense that they meet the Griesmer bound.