Yanjun LI Jinjie GAO Haibin KAN Jie PENG Lijing ZHENG Changhui CHEN
In this letter, we give a characterization for a generic construction of bent functions. This characterization enables us to obtain another efficient construction of bent functions and to give a positive answer on a problem of bent functions.
Yingzhong ZHANG Xiaoni DU Wengang JIN Xingbin QIAO
Boolean functions with a few Walsh spectral values have important applications in sequence ciphers and coding theory. In this paper, we first construct a class of Boolean functions with at most five-valued Walsh spectra by using the secondary construction of Boolean functions, in particular, plateaued functions are included. Then, we construct three classes of Boolean functions with five-valued Walsh spectra using Kasami functions and investigate the Walsh spectrum distributions of the new functions. Finally, three classes of minimal linear codes with five-weights are obtained, which can be used to design secret sharing scheme with good access structures.
Zeyao LI Niu JIANG Zepeng ZHUO
In this paper, we study the properties of the sum-of-squares indicator of vectorial Boolean functions. Firstly, we give the upper bound of $sum_{uin mathbb{F}_2^n,vin mathbb{F}_2^m}mathcal{W}_F^3(u,v)$. Secondly, based on the Walsh-Hadamard transform, we give a secondary construction of vectorial bent functions. Further, three kinds of sum-of-squares indicators of vectorial Boolean functions are defined by autocorrelation function and the lower and upper bounds of the sum-of-squares indicators are derived. Finally, we study the sum-of-squares indicators with respect to several equivalence relations, and get the sum-of-squares indicator which have the best cryptographic properties.
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.
Zhiyao YANG Pinhui KE Zhixiong CHEN
In 2017, Tang et al. provided a complete characterization of generalized bent functions from ℤ2n to ℤq(q = 2m) in terms of their component functions (IEEE Trans. Inf. Theory. vol.63, no.7, pp.4668-4674). In this letter, for a general even q, we aim to provide some characterizations and more constructions of generalized bent functions with flexible coefficients. Firstly, we present some sufficient conditions for a generalized Boolean function with at most three terms to be gbent. Based on these results, we give a positive answer to a remaining question proposed by Hodžić in 2015. We also prove that the sufficient conditions are also necessary in some special cases. However, these sufficient conditions whether they are also necessary, in general, is left as an open problem. Secondly, from a uniform point of view, we provide a secondary construction of gbent function, which includes several known constructions as special cases.
Jiawei DU Xiaoni DU Wengang JIN Yingzhong ZHANG
Linear codes with a few-weight have important applications in combinatorial design, strongly regular graphs and cryptography. In this paper, we first construct a class of Boolean functions with at most five-valued Walsh spectra, and determine their spectrum distribution. Then, we derive two classes of linear codes with at most six-weight from the new functions. Meanwhile, the length, dimension and weight distributions of the codes are obtained. Results show that both of the new codes are minimal and among them, one is wide minimal code and the other is a narrow minimal code and thus can be used to design secret sharing scheme with good access structures. Finally, some Magma programs are used to verify the correctness of our results.
In this letter, we will prove that chaotic binary sequences generated by the tent map and Walsh functions are i.i.d. (independent and identically distributed) and orthogonal to each other.
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.
Qinglan ZHAO Dong ZHENG Xiangxue LI Yinghui ZHANG Xiaoli DONG
As a with-carry analog (based on modular arithmetic) of the usual Walsh-Hadamard transform (WHT), arithmetic Walsh transform (AWT) has been used to obtain analogs of some properties of Boolean functions which are important in the design and analysis of cryptosystems. The existence of nonzero linear structure of Boolean functions is an important criterion to measure the weakness of these functions in their cryptographic applications. In this paper, we find more analogs of linear structures of Boolean functions from AWT. For some classes of n-variable Boolean functions f, we find necessary and sufficient conditions for the existence of an invariant linear structure and a complementary linear structure 1n of f. We abstract out a sectionally linear relationship between AWT and WHT of n-variable balanced Boolean functions f with linear structure 1n. This result show that AWT can characterize cryptographic properties of these functions as long as WHT can. In addition, for a diagonal Boolean function f, a recent result by Carlet and Klapper says that the AWT of f can be expressed in terms of the AWT of a diagonal Boolean function of algebraic degree at most 3 in a larger number of variables. We provide for the result a complete and more modular proof which works for both even and odd weights (of the parameter c in the Corollary 19 by Carlet and Klapper (DCC 73(2): 299-318, 2014).
Qianjian XING Zhenguo MA Feng YU
This letter presents a novel memory-based architecture for radix-2 fast Walsh-Hadamard-Fourier transform (FWFT) based on the constant geometry FWFT algorithm. It is composed of a multi-function Processing Engine, a conflict-free memory addressing scheme and an efficient twiddle factor generator. The address for memory access and the control signals for stride permutation are formulated in detail and the methods can be applied to other memory-based FFT-like architectures.
Lei SUN Fang-Wei FU Xuan GUANG
Recent research has shown that the class of rotation symmetric Boolean functions is beneficial to cryptographics. In this paper, for an odd prime p, two sufficient conditions for p-variable rotation symmetric Boolean functions to be 1-resilient are obtained, and then several concrete constructions satisfying the conditions are presented. This is the first time that resilient rotation symmetric Boolean functions have been systematically constructed. In particular, we construct a class of 2-resilient rotation symmetric Boolean functions when p=2m+1 for m ≥ 4. Moreover, several classes of 1-order correlation immune rotation symmetric Boolean functions are also got.
Isao MIYAGAWA Yukinobu TANIGUCHI
We propose a practical method that acquires dense light transports from unknown 3D objects by employing orthogonal illumination based on a Walsh-Hadamard matrix for relighting computation. We assume the presence of color crosstalk, which represents color mixing between projector pixels and camera pixels, and then describe the light transport matrix by using sets of the orthogonal illumination and the corresponding camera response. Our method handles not only direct reflection light but also global light radiated from the entire environment. Tests of the proposed method using real images show that orthogonal illumination is an effective way of acquiring accurate light transports from various 3D objects. We demonstrate a relighting test based on acquired light transports and confirm that our method outputs excellent relighting images that compare favorably with the actual images observed by the system.
Qianjian XING Feng YU Xiaobo YIN Bei ZHAO
In this letter, we present a radix-R regular interconnection pattern family of factorizations for the WHT-FFT with identical stage-to-stage interconnection pattern in a unified form, where R is any power of 2. This family of algorithms has identical sparse matrix factorization in each stage and can be implemented in a merged butterfly structure, which conduce to regular and efficient memory managing scalable to high radices. And in each stage, the butterflies with same twiddle factor set are aggregated together, which can reduce the twiddle factor evaluations or accesses to the lookup table. The kinds of factorization can also be extended to FFT, WHT and SCHT with identical stage-to-stage interconnection pattern.
In this paper, we propose an efficient channel estimation scheme in bi-directional wireless orthogonal frequency division multiplexing (OFDM) relay systems applying analog network coding (ANC). In the relay systems applying ANC, channel separation is needed to estimate each of the bi-directional channels simultaneously from the combined received signal. In the conventional channel estimation schemes, relatively higher-ratio pilots are needed to obtain accurate channels. In contrast, we propose a channel estimation scheme with sparse pilots, while maintaining high accuracy for channel estimation. In the proposed scheme, Walsh codes are inserted as the pilot symbols at both end nodes, and the individual channels are obtained by correlation processing from the combined signals. The improved bit error rate (BER) and throughput performances of the proposed scheme are shown through computer simulations.
Single-packet attack can be tracked with logging-based IP traceback approaches, whereas DDoS attack can be tracked with marking-based approaches. However, both approaches have their limits. Logging-based approaches incur heavy overhead for packet-digest storage as well as time overhead for both path recording and recovery. Marking-based approaches incur little traceback overhead but are unable to track single packets. Simply deploying both approaches in the same network to deal with single-packet and DDoS attacks is not an efficient solution due to the heavy traceback overhead. Recent studies suggest that hybrid approaches are more efficient as they consume less router memory to store packet digests and require fewer attack packets to recover attack paths. Thus, the hybrid single packet traceback approach is more promising in efficiently tracking both single-packet and DDoS attacks. The major challenge lies in reducing storage and time overhead while maintaining single-packet traceback capability. We present in this paper a new hybrid approach to efficiently track single-packet attacks by designing a novel path fragment encoding scheme using the orthogonality of Walsh matrix and the degree distribution characteristic of router-level topologies. Compared to HIT (Hybrid IP Traceback), which, to the best of our knowledge, is the most efficient hybrid approach for single-packet traceback, our approach has three advantages. First, it reduces the overhead by 2/3 in both storage and time for recording packet paths. Second, the time overhead for recovering packet paths is also reduced by a calculatable amount. Finally, our approach generates no more than 2/3 of the false-positive paths generated by HIT.
This paper presents an integer discrete cosine transform (IntDCT) with only dyadic values such as k/2n (k, n∈ in N). Although some conventional IntDCTs have been proposed, they are not suitable for lossless-to-lossy image coding in low-bit-word-length (coefficients) due to the degradation of the frequency decomposition performance in the system. First, the proposed M-channel lossless Walsh-Hadamard transform (LWHT) can be constructed by only (log2M)-bit-word-length and has structural regularity. Then, our 8-channel IntDCT via LWHT keeps good coding performance even if low-bit-word-length is used because LWHT, which is main part of IntDCT, can be implemented by only 3-bit-word-length. Finally, the validity of our method is proved by showing the results of lossless-to-lossy image coding in low-bit-word-length.
Kanji TANAKA Ken-ichi SAEKI Mamoru MINAMI Takeshi UEDA
This paper presents a novel approach for robot localization using landmark maps. With recent progress in SLAM researches, it has become crucial for a robot to obtain and use large-size maps that are incrementally built by other mapper robots. Our localization approach successfully works with such incremental and large-size maps. In literature, RANSAC map-matching has been a promising approach for large-size maps. We extend the RANSAC map-matching so as to deal with incremental maps. We combine the incremental RANSAC with an incremental LSH database and develop a hybrid of the position-based and the appearance-based approaches. A series of experiments using radish dataset show promising results.
This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.
Hiroaki TEZUKA Takao NISHITANI
This paper describes a multiresolutional Gaussian mixture model (GMM) for precise and stable foreground segmentation. A multiple block sizes GMM and a computationally efficient fine-to-coarse strategy, which are carried out in the Walsh transform (WT) domain, are newly introduced to the GMM scheme. By using a set of variable size block-based GMMs, a precise and stable processing is realized. Our fine-to-coarse strategy comes from the WT spectral nature, which drastically reduces the computational steps. In addition, the total computation amount of the proposed approach requires only less than 10% of the original pixel-based GMM approach. Experimental results show that our approach gives stable performance in many conditions, including dark foreground objects against light, global lighting changes, and scenery in heavy snow.
This paper is concerned with timing synchronization of high rates UWB signals operating in a dense multipath environment, where access must tackle inter-frame interference (IFI), inter-symbol interference (ISI) and even multi-user interference (MUI). A training-based joint timing and channel estimation scheme is proposed, which is resilient to IFI, ISI, MUI and pulse distortion. A low-complexity detection scheme similar to transmit-reference (TR) scheme comes out as a by-product. For saving the training symbols, we further develop an extended decision-directed (DD) scheme. A lower bound on the probability of correct detection is derived which agrees well with the simulated result for moderate to high SNR values. The results show that the proposed algorithm achieves a significant performance gain in terms of mean square error and bit error rate in comparison to the "timing with dirty templates" (TDT) algorithms.