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.
Takanori ISOBE Kyoji SHIBUTANI
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.
Guangkui XU Xiwang CAO Jian GAO Gaojun LUO
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.
Taekeun PARK Koohong KANG Daesung MOON
In this paper, we propose a scalable and seamless connection migration scheme for moving target defense in legacy networks. The main idea is that a host is allowed to receive incoming packets with a destination address that is either its current IP address or its previous IP address for a period of time because the host does not physically move into another network. Experimental results show that our scheme outperforms the existing connection migration mechanism regardless of the number of active connections in the host.
Takahiro FUJITA Kohei HATANO Shuji KIJIMA Eiji TAKIMOTO
We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.
Yuji HASHIMOTO Koji NUIDA Kazumasa SHINAGAWA Masaki INAMURA Goichiro HANAOKA
In the research area of card-based secure computation, one of the long-standing open problems is a problem proposed by Crépeau and Kilian at CRYPTO 1993. This is to develop an efficient protocol using a deck of physical cards that generates uniformly at random a permutation with no fixed points (called a derangement), where the resulting permutation must be secret against the parties in the protocol. All the existing protocols for the problem have a common issue of lacking a guarantee to halt within a finite number of steps. In this paper, we investigate feasibility and infeasibility for the problem where both a uniformly random output and a finite runtime is required. First, we propose a way of reducing the original problem, which is to sample a uniform distribution over an inefficiently large set of the derangements, to another problem of sampling a non-uniform distribution but with a significantly smaller underlying set. This result will be a base of a new approach to the problem. On the other hand, we also give (assuming the abc conjecture), under a certain formal model, an asymptotic lower bound of the number of cards for protocols solving the problem using uniform shuffles only. This result would give a supporting evidence for the necessity of dealing with non-uniform distributions such as in the aforementioned first part of our result.
Yuji HASHIMOTO Kazumasa SHINAGAWA Koji NUIDA Masaki INAMURA Goichiro HANAOKA
We consider a problem, which we call secure grouping, of dividing a number of parties into some subsets (groups) in the following manner: Each party has to know the other members of his/her group, while he/she may not know anything about how the remaining parties are divided (except for certain public predetermined constraints, such as the number of parties in each group). In this paper, we construct an information-theoretically secure protocol using a deck of physical cards to solve the problem, which is jointly executable by the parties themselves without a trusted third party. Despite the non-triviality and the potential usefulness of the secure grouping, our proposed protocol is fairly simple to describe and execute. Our protocol is based on algebraic properties of conjugate permutations. A key ingredient of our protocol is our new techniques to apply multiplication and inverse operations to hidden permutations (i.e., those encoded by using face-down cards), which would be of independent interest and would have various potential applications.
Jie PENG Chik How TAN Qichun WANG Jianhua GAO Haibin KAN
Research on permutation polynomials over the finite field F22k with significant cryptographical properties such as possibly low differential uniformity, possibly high nonlinearity and algebraic degree has attracted a lot of attention and made considerable progress in recent years. Once used as the substitution boxes (S-boxes) in the block ciphers with Substitution Permutation Network (SPN) structure, this kind of polynomials can have a good performance against the classical cryptographic analysis such as linear attacks, differential attacks and the higher order differential attacks. In this paper we put forward a new construction of differentially 4-uniformity permutations over F22k by modifying the inverse function on some specific subsets of the finite field. Compared with the previous similar works, there are several advantages of our new construction. One is that it can provide a very large number of Carlet-Charpin-Zinoviev equivalent classes of functions (increasing exponentially). Another advantage is that all the functions are explicitly constructed, and the polynomial forms are obtained for three subclasses. The third advantage is that the chosen subsets are very large, hence all the new functions are not close to the inverse function. Therefore, our construction may provide more choices for designing of S-boxes. Moreover, it has been checked by a software programm for k=3 that except for one special function, all the other functions in our construction are Carlet-Charpin-Zinoviev equivalent to the existing ones.
Shanqi PANG Miao FENG Xunan WANG Jing WANG
Bent functions have been applied to cryptography, spread spectrum, coding theory, and combinatorial design. Permutations play an important role in the design of cryptographic transformations such as block ciphers, hash functions and stream ciphers. By using the Kronecker product this paper presents a general recursive construction method of permutations over finite field. As applications of our method, several infinite classes of permutations are obtained. By means of the permutations obtained and M-M functions we construct several infinite families of bent functions.
Peng ZHAO Jianjun MU Yucheng HE Xiaopeng JIAO
Codes over permutations and multipermutations have received considerable attention since the rank modulation scheme is presented for flash memories. Deletions in multipermutations often occur due to data synchronization errors. Based on the interleaving of several single-deletion-correcting multipermutation codes, we present a construction of multipermutation codes for correcting a burst of at most t deletions with shift magnitude one for t ≥2. The proposed construction is proved with including an efficient decoding method. A calculation example is provided to validate the construction and its decoding method.
Yuqiang CAO Weiguo GONG Bo ZHANG Fanxin ZENG Sen BAI
Block compressed sensing with random permutation (BCS-RP) has been shown to be very effective for image Encryption-then-Compression (ETC) applications. However, in the BCS-RP scheme, the statistical information of the blocks is disclosed, because the encryption is conducted within each small block of the image. To solve this problem, a two-dimension compressed sensing (2DCS) with 2D random permutation (2DRP) strategy for image ETC applications is proposed in this letter, where the 2DRP strategy is used for encrypting the image and the 2DCS scheme is used for compressing the encrypted image. Compared with the BCS-RP scheme, the proposed approach has two benefits. Firstly, it offers better security. Secondly, it obtains a significant gain of peak signal-to-noise ratio (PSNR) of the reconstructed-images.
Yuqiang CAO Weiguo GONG Bo ZHANG Fanxin ZENG Sen BAI
Block compressed sensing (CS) with optimal permutation is a promising method to improve sampling efficiency in CS-based image compression. However, the existing optimal permutation scheme brings a large amount of extra data to encode the permutation information because it needs to know the permutation information to accomplish signal reconstruction. When the extra data is taken into consideration, the improvement in sampling efficiency of this method is limited. In order to solve this problem, a new optimal permutation strategy for block CS (BCS) is proposed. Based on the proposed permutation strategy, an improved optimal permutation based BCS method called BCS-NOP (BCS with new optimal permutation) is proposed in this paper. Simulation results show that the proposed approach reduces the amount of extra data to encode the permutation information significantly and thereby improves the sampling efficiency compared with the existing optimal permutation based BCS approach.
In this paper, we propose a group theoretic representation suitable for the rank-modulation (RM) scheme over the multi-cell ranking presented by En Gad et al. By introducing an action of the group of all permutation matrices on the set of all permutations, the scheme is clearly reformulated. Moreover, we introduce the concept of r-dominating sets over the multi-cell ranking, which is a generalization of conventional dominating sets, in the design of rank-modulation rewriting codes. The concept together with the proposed group theoretic representation yields an explicit formula of an upper bound on the size of the set of messages that can be stored in the memory by using RM rewriting codes over multi-cell ranking. This bound enables us to consider the trade-off between the size of the storable message set and the rewriting cost more closely. We also provide a concrete example of RM rewriting code that is not available by conventional approaches and whose size of the storable message set can not be achieved by conventional codes.
Peng ZHAO Jianjun MU Xiaopeng JIAO
In this letter, three types of constructions for multipermutation codes are investigated by using interleaving technique and single-deletion permutation codes to correct a predetermined number of adjacent deletions. The decoding methods for the proposed codes are provided in proofs and verified with examples. The rates of these multipermutation codes are also compared.
Masayuki ISATO Koichiro SAWA Takahiro UENO
Many DC commutator motors are widely used in automobiles. In recent years, as compact and high output DC motors have been developed due to advanced technology, the faster the rotational speed is required and the commutation arc causes a high rate of wear/erosion of brush and commutator. Therefore, it is important how the motor speed influences commutation phenomena such as arc duration, residual current and erosion and wear of commutator and brush in order to achieve high reliability and extensive lifespan. In this paper waveforms of commutation voltage and current are measured at the rotation speed of 1000 to 5000min-1and the relation between rotation speed and arc duration / residual current is obtained. In addition long term tests are carried out at the rotation speed of 1000 to 5000min-1 the change of arc duration and effective commutation period is examined during the test of 20hours. Further, brush wear is evaluated by the difference of brush length between before and after test. Consequently, it can be made clear that as the speed increases, the effective commutation period decreases and the arc duration is almost same at the speed up to 3000min-1 and is around 42µsec.
Jiang LIU Hongqi ZHANG Zhencheng GUO
Focused on network reconnaissance, eavesdropping, and DoS attacks caused by static routing policies, this paper designs a random routing mutation architecture based on the OpenFlow protocol, which takes advantages of the global network view and centralized control in a software-defined network. An entropy matrix of network traffic characteristics is constructed by using volume measurements and characteristic measurements of network traffic. Random routing mutation is triggered according to the result of network anomaly detection, which using a wavelet transform and principal component analysis to handle the above entropy matrix for both spatial and temporal correlations. The generation of a random routing path is specified as a 0-1 knapsack problem, which is calculated using an improved ant colony algorithm. Theoretical analysis and simulation results show that the proposed method not only increases the difficulty of network reconnaissance and eavesdropping but also reduces the impact of DoS attacks on the normal communication in an SDN network.
Naoto SASAOKA James OKELLO Masatsune ISHIHARA Kazuki AOYAMA Yoshio ITOH
We propose a pre-filtering system for blind equalization in order to separate orthogonal frequency division multiplexing (OFDM) symbols in a multiple-input multiple-output (MIMO) - OFDM system. In a conventional blind MIMO-OFDM equalization without the pre-filtering system, there is a possibility that originally transmitted streams are permutated, resulting in the receiver being unable to retrieve desired signals. We also note that signal permutation is different for each subcarrier. In order to solve this problem, each transmitted stream of the proposed MIMO-OFDM system is pre-filtered by a unique allpass filter. In this paper, the pre-filter is referred to as transmit tagging filter (TT-Filter). At a receiver, an inverse filter of the TT-filter is used to blindly equalize a MIMO channel without permutation problem. Further, in order to overcome the issue of phase ambiguity, this paper introduces blind phase compensation.
Yuyin YU Lishan KE Zhiqiang LIN Qiuyan WANG
Permutation polynomials over Zpn are useful in the design of cryptographic algorithms. In this paper, we obtain an equivalent condition for polynomial functions over Zpn to be permutations, and this equivalent condition can help us to analysis the randomness of such functions. Our results provide a method to distinguish permutation polynomials from random functions. We also introduce how to improve the randomness of permutation polynomials over Zpn.