Feifei YAN Pinhui KE Zuling CHANG
Recently, trace representation of a class of balanced quaternary sequences of period p from the classical cyclotomic classes was given by Yang et al. (Cryptogr. Commun.,15 (2023): 921-940). In this letter, based on the generalized cyclotomic classes, we define a class of balanced quaternary sequences of period pn, where p = ef + 1 is an odd prime number and satisfies e ≡ 0 (mod 4). Furthermore, we calculate the defining polynomial of these sequences and obtain the formula for determining their trace representations over ℤ4, by which the linear complexity of these sequences over ℤ4 can be determined.
You GAO Ming-Yue XIE Gang WANG Lin-Zhi SHEN
Mutually unbiased bases (MUBs) are widely used in quantum information processing and play an important role in quantum cryptography, quantum state tomography and communications. It’s difficult to construct MUBs and remains unknown whether complete MUBs exist for any non prime power. Therefore, researchers have proposed the solution to construct approximately mutually unbiased bases (AMUBs) by weakening the inner product conditions. This paper constructs q AMUBs of ℂq, (q + 1) AMUBs of ℂq-1 and q AMUBs of ℂq-1 by using character sums over Galois rings and finite fields, where q is a power of a prime. The first construction of q AMUBs of ℂq is new which illustrates K AMUBs of ℂK can be achieved. The second and third constructions in this paper include the partial results about AMUBs constructed by W. Wang et al. in [9].
Yanyan CHANG Wei ZHANG Hao WANG Lina SHI Yanyan LIU
This letter introduces a prime-factor Galois field Fourier transform (PF-GFFT) architecture to frequency domain decoding (FDD) of cyclic codes. Firstly, a fast FDD scheme is designed which converts the original single longer Fourier transform to a multi-dimensional smaller transform. Furthermore, a ladder-shift architecture for PF-GFFT is explored to solve the rearrangement problem of input and output data. In this regard, PF-GFFT is considered as a lower order spectral calculation scheme, which has sufficient preponderance in reducing the computational complexity. Simulation results show that PF-GFFT compares favorably with the current general GFFT, simplified-GFFT (S-GFFT), and circular shifts-GFFT (CS-GFFT) algorithms in time-consuming cost, and is nearly an order of magnitude or smaller than them. The superiority is a benefit to improving the decoding speed and has potential application value in decoding cyclic codes with longer code lengths.
In this paper, we describe the Galois dual of rank metric codes in the ambient space FQn×m and FQmn, where Q=qe. We obtain connections between the duality of rank metric codes with respect to distinct Galois inner products. Furthermore, for 0 ≤ s < e, we introduce the concept of qsm-dual bases of FQm over FQ and obtain some conditions about the existence of qsm-self-dual basis.
Qingjuan ZHANG Shanqi PANG Yuan LI
Variable strength orthogonal array, as a special form of variable strength covering array, plays an important role in computer software testing and cryptography. In this paper, we study the construction of variable strength orthogonal arrays with strength two containing strength greater than two by Galois field and construct some variable strength orthogonal arrays with strength l containing strength greater than l by Fan-construction.
Linyan YU Pinhui KE Zuling CHANG
In this letter, we give a new construction of a family of sequences of period pk-1 with low correlation value by using additive and multiplicative characters over Galois rings. The new constructed sequence family has family size (M-1)(pk-1)rpkr(e-1) and alphabet size Mpe. Based on the characters sum over Galois rings, an upper bound on the correlation of this sequence family is presented.
Lu ZHAO Bo XU Tianqing CAO Jiao DU
A unified construction for yielding optimal and balanced quaternary sequences from ideal/optimal balanced binary sequences was proposed by Zeng et al. In this paper, the linear complexity over finite field 𝔽2, 𝔽4 and Galois ring ℤ4 of the quaternary sequences are discussed, respectively. The exact values of linear complexity of sequences obtained by Legendre sequence pair, twin-prime sequence pair and Hall's sextic sequence pair are derived.
Milo&scaron M. RADMANOVIĆ Radomir S. STANKOVIĆ
Multiple-valued bent functions are functions with highest nonlinearity which makes them interesting for multiple-valued cryptography. Since the general structure of bent functions is still unknown, methods for construction of bent functions are often based on some deterministic criteria. For practical applications, it is often necessary to be able to construct a bent function that does not belong to any specific class of functions. Thus, the criteria for constructions are combined with exhaustive search over all possible functions which can be very CPU time consuming. A solution is to restrict the search space by some conditions that should be satisfied by the produced bent functions. In this paper, we proposed the construction method based on spectral subsets of multiple-valued bent functions satisfying certain appropriately formulated restrictions in Galois field (GF) and Reed-Muller-Fourier (RMF) domains. Experimental results show that the proposed method efficiently constructs ternary and quaternary bent functions by using these restrictions.
Akira ITO Rei UENO Naofumi HOMMA
This study presents a formal verification method for Galois-field (GF) arithmetic circuits with the characteristics of more than two values. The proposed method formally verifies the correctness of circuit functionality (i.e., the input-output relations given as GF-polynomials) by checking the equivalence between a specification and a gate-level netlist. We represent a netlist using simultaneous algebraic equations and solve them based on a novel polynomial reduction method that can be efficiently applied to arithmetic over extension fields $mathbb{F}_{p^m}$, where the characteristic p is larger than two. By using the reverse topological term order to derive the Gröbner basis, our method can complete the verification, even when a target circuit includes bugs. In addition, we introduce an extension of the Galois-Field binary moment diagrams to perform the polynomial reductions faster. Our experimental results show that the proposed method can efficiently verify practical $mathbb{F}_{p^m}$ arithmetic circuits, including those used in modern cryptography. Moreover, we demonstrate that the extended polynomial reduction technique can enable verification that is up to approximately five times faster than the original one.
The Galois hull of linear code is defined to be the intersection of the code and its Galois dual. In this paper, we investigate the Galois hulls of cyclic codes over Fqr. For any integer s≤r, we present some sufficient and necessary conditions that cyclic codes have l-dimensional s-Galois hull. Moreover, we prove that a cyclic code C has l-dimensional s-Galois hull iff C has l-dimensional (r-s)-Galois hull. In particular, we also present the sufficient and necessary condition for cyclic codes with 1-dimensional Galois hulls and the relationship between cyclic codes with 1-dimensional Galois hulls and cyclic codes with Galois complementary duals. Some optimal cyclic codes with Galois hulls are obtained. Finally, we explicitly construct a class of cyclic codes with 1-Galois linear complementary dual over Fq3.
Toshihiko WAKAHARA Toshitaka MAKI Noriyasu YAMAMOTO Akihisa KODATE Manabu OKAMOTO Hiroyuki NISHI
The Life Intelligence and Office Information System (LOIS) Technical Committee of the Institute of Electronics, Information and Communication Engineers (IEICE) dates its origin to May 1986. This Technical Committee (TC) has covered the research fields of the office related systems for more than 30 years. Over this time, this TC, under its multiple name changes, has served as a forum for research and provided many opportunities for not only office users but also ordinary users of systems and services to present ideas and discussions. Therefore, these advanced technologies have been diffused from big enterprises to small companies and home users responsible for their management and operation. This paper sums up the technology trends and views of the office related systems and services covered in the 30 years of presentations of the LOIS Technical Committees by using the new literature analysis system based on the IEICE Knowledge Discovery system (I-Scover system).
Rei UENO Naofumi HOMMA Takafumi AOKI Sumio MORIOKA
This paper presents an automatic hierarchical formal verification method for arithmetic circuits over Galois fields (GFs) which are dedicated digital circuits for GF arithmetic operations used in cryptographic processors. The proposed verification method is based on a combination of a word-level computer algebra procedure with a bit-level PPRM (Positive Polarity Reed-Muller) expansion procedure. While the application of the proposed verification method is not limited to cryptographic processors, these processors are our important targets because complicated implementation techniques, such as field conversions, are frequently used for side-channel resistant, compact and low power design. In the proposed method, the correctness of entire datapath is verified over GF(2m) level, or word-level. A datapath implementation is represented hierarchically as a set of components' functional descriptions over GF(2m) and their wiring connections. We verify that the implementation satisfies a given total-functional specification over GF(2m), by using an automatic algebraic method based on the Gröbner basis and a polynomial reduction. Then, in order to verify whether each component circuit is correctly implemented by combination of GF(2) operations, i.e. logic gates in bit-level, we use our fast PPRM expansion procedure which is customized for handling large-scale Boolean expressions with many variables. We have applied the proposed method to a complicated AES (Advanced Encryption Standard) circuit with a masking countermeasure against side-channel attack. The results show that the proposed method can verify such practical circuit automatically within 4 minutes, while any single conventional verification methods fail within a day or even more.
The minimum biclique cover problem is known to be NP-hard for general bipartite graphs. It can be solved in polynomial time for C4-free bipartite graphs, bipartite distance hereditary graphs and bipartite domino-free graphs. In this paper, we define the modified Galois lattice Gm(B) for a bipartite graph B and introduce the redundant parameter R(B). We show that R(B)=0 if and only if B is domino-free. Furthermore, for an input graph such that R(B)=1, we show that the minimum biclique cover problem can be solved in polynomial time.
Yohei HORI Toshihiro KATASHITA Hirofumi SAKANE Kenji TODA Akashi SATOH
Protecting the confidentiality and integrity of a configuration bitstream is essential for the dynamic partial reconfiguration (DPR) of field-programmable gate arrays (FPGAs). This is because erroneous or falsified bitstreams can cause fatal damage to FPGAs. In this paper, we present a high-speed and area-efficient bitstream protection scheme for DPR systems using the Advanced Encryption Standard with Galois/Counter Mode (AES-GCM), which is an authenticated encryption algorithm. Unlike many previous studies, our bitstream protection scheme also provides a mechanism for error recovery and tamper resistance against configuration block deletion, insertion, and disorder. The implementation and evaluation results show that our DPR scheme achieves a higher performance, in terms of speed and area, than previous methods.
Lu ZHAO Qiao-yan WEN Jie ZHANG
The linear complexity of quaternary sequences plays an important role in cryptology. In this paper, the minimal polynomial of a class of quaternary sequences with low autocorrelation constructed by generalized cyclotomic sequences pairs is determined, and the linear complexity of the sequences is also obtained.
In this letter, a low complexity decoder for non-binary low-density parity-check (LDPC) codes in a multiple-input and multiple-output (MIMO) channel is proposed employing Quasi-orthogonal space-time block code (QOSTBC). The complexity of the proposed decoding algorithm involved grows linearly with the number of transmit antennas and order of Galois Field.
Kenta KASAI Charly POULLIAT David DECLERCQ Kohichi SAKANIWA
In this paper, we study the average symbol and bit-weight distributions for ensembles of non-binary low-density parity-check codes defined on GF(2p). Moreover, we derive the asymptotic exponential growth rate of the weight distributions in the limit of large codelength. Interestingly, we show that the normalized typical minimum distance does not monotonically increase with the size of the field.
For decoding non-binary low-density parity-check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worth, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain.
Xueqin JIANG Moon Ho LEE Tae Chol SHIN
This letter presents an approach to the construction of multiple-rate quasi-cyclic (QC) low-density parity-check (LDPC) codes based on hyperplanes (µ-flats) of two different dimensions in Euclidean geometries. The codes constructed with this method have the same code length, multiple-rate and large stopping sets while maintaining the same basic hardware architecture. The code performance is investigated in terms of the bit error rate (BER) and compared with those of the LDPC codes which are proposed in IEEE 802.16e standard. Simulation results show that our codes perform very well and have low error floors over the AWGN channel.
Masayuki ARAI Satoshi FUKUMOTO Kazuhiko IWASAKI
Convolutional compactors offer a promising technique of compacting test responses. In this study we expand the architecture of convolutional compactor onto a Galois field in order to improve compaction ratio as well as reduce X-masking probability, namely, the probability that an error is masked by unknown values. While each scan chain is independently connected by EOR gates in the conventional arrangement, the proposed scheme treats q signals as an element over GF(2q), and the connections are configured on the same field. We show the arrangement of the proposed compactors and the equivalent expression over GF(2). We then evaluate the effectiveness of the proposed expansion in terms of X-masking probability by simulations with uniform distribution of X-values, as well as reduction of hardware overheads. Furthermore, we evaluate a multi-weight arrangement of the proposed compactors for non-uniform X distributions.