With the advancement of face manipulation technology, forgery images in multi-face scenarios are gradually becoming a more complex and realistic challenge. Despite this, detection and localization methods for such multi-face manipulations remain underdeveloped. Traditional manipulation localization methods either indirectly derive detection results from localization masks, resulting in limited detection performance, or employ a naive two-branch structure to simultaneously obtain detection and localization results, which cannot effectively benefit the localization capability due to limited interaction between the two tasks. This paper proposes a new framework, namely MoNFAP, specifically tailored for multi-face manipulation detection and localization. The MoNFAP primarily introduces two novel modules: the Forgery-aware Unified Predictor (FUP) Module and the Mixture-of-Noises Module (MNM). The proposed FUP integrates detection and localization tasks using a token learning strategy and multiple forgery-aware transformers, which facilitates the use of classification information to enhance localization capability. Furthermore, to mitigate the interference from general semantic object information, we propose the MNM that leverages multiple noise extractors based on the mixture of experts concept. This allows the MNM to learn semantic-agnostic forgery features from general RGB features, further boosting the performance of our proposed framework. Finally, we establish a comprehensive benchmark for multi-face detection and localization, and the proposed MoNFAP achieves significant performance. The code is available: https://github.com/miaoct/MoNFAP.

As Deepfake content proliferates online, advancing face manipulation forensics has become crucial. To combat this emerging threat, previous methods mainly focus on studying how to distinguish authentic and manipulated face images. Although impressive, image-level classification lacks explainability and is limited to specific application scenarios, spurring recent research on pixel-level prediction for face manipulation forensics. However, existing forgery localization methods suffer from exploring frequency-based forgery traces in the localization network. In this paper, we observe that multi-frequency spectrum information is effective for identifying tampered regions. To this end, a novel Multi-spectral Class Center Network (MSCCNet) is proposed for face manipulation localization. Specifically, we design a Multi-spectral Class Center (MSCC) module to learn more generalizable and multi-frequency features. Based on the features of different frequency bands, the MSCC module collects multi-spectral class centers and computes pixel-to-class relations. Applying multi-spectral class-level representations suppresses the semantic information of the visual concepts which is insensitive to manipulated regions of forgery images. Furthermore, we propose a Multi-level Features Aggregation (MFA) module to employ more low-level forgery artifacts and structural textures. Meanwhile, we conduct a comprehensive localization benchmark based on pixel-level FF++ and Dolos datasets. Experimental results quantitatively and qualitatively demonstrate the effectiveness and superiority of the proposed MSCCNet. We expect this work to inspire more studies on pixel-level face manipulation localization. The codes are available.

In recent years, face forgery detectors have aroused great interest and achieved impressive performance, but they are still struggling with generalization and robustness. In this work, we explore taking full advantage of the fine-grained forgery traces in both spatial and frequency domains to alleviate this issue. Specifically, we propose a novel High-Frequency Fine-Grained Transformer (F2Trans) network which contains two important components, namely Central Difference Attention (CDA) and High-frequency Wavelet Sampler (HWS). The premier CDA module is capable of capturing invariant fine-grained manipulation patterns by aggregating both pixel-level intensity and gradient information of the query to generate key and value pairs. Subsequently, the proposed HWS discards the low-frequency components of wavelet transformation and hierarchically explores high-frequency forgery cues of feature maps, which prevents model confusion caused by low-frequency components and pays attention to local frequency information. In addition, HWS can be employed as a special pooling layer for the F2Trans architecture to produce hierarchical feature representations in the spatial-frequency domain. Extensive experiments on multiple popular benchmarks demonstrate the generalization and robustness of the specially designed F2Trans framework is well-tailored for face forgery detection when confronting the cross-dataset, cross-manipulation, and unseen perturbations.

In 2018, Pott et al. investigated vectorial functions with maximal number of bent components. They found one class of binomial functions attaining the upper bound. They also proposed an open problem regarding monomial functions that have the maximal number of bent components. In this paper, we solve this open problem. Specifically, we prove that if$k\geq 2$, then$x^{s(2^{k}+1)}$are the only monomial functions over$\mathbb {F}_{2^{2k}}$that have the maximal number of bent components, where$s\in \{1, 2, 2^{2}, \ldots, 2^{k-1}\}$. As a consequence, we also solve an open problem of Ness and Helleseth about the cross-correlation function between two sequences in 2006.

Fibonacci and Galois are two different kinds of configurations in stream ciphers. Although many transformations between two configurations have been proposed, there is no sufficient analysis of their FPGA performance. Espresso stream cipher provides an ideal sample to explore such a problem. The 128-bit secret key Espresso is designed in Galois configuration, and there is a Fibonacci-configured Espresso variant proved with the equivalent security level. To fully leverage the efficiency of two configurations, we explore the hardware optimization approaches toward area and throughput, respectively. In short, the FPGA-implemented Fibonacci cipher is more suitable for extremely resource-constrained or high-throughput applications, while the Galois cipher compromises both area and speed. To the best of our knowledge, this is the first work to systematically compare the FPGA performance of cipher configurations under relatively fair cryptographic security. We hope this work can serve as a reference for the cryptography hardware architecture research community.

Fruit-80, which emerged as an ultra-lightweight stream cipher with 80-bit secret key, is oriented toward resource-constrained devices in the Internet of Things. In this article, we propose area and speed optimization architectures of Fruit-80 on FPGAs. Our implementations include both serial and parallel structure and optimize area, power, speed, and throughput, respectively. The area optimization architecture aims to achieve the most suitable ratio of look-up-tables and flip-flops to fully utilize the reconfigurable unit. It also reuses NFSR and LFSR feedback functions to save resources for high throughput. The speed optimization architecture adopts a hybrid approach for parallelization and reduces the latency of long data paths by pre-generating primary feedback and inserting flip-flops. Besides, we recommend using the round key function to optimize serial or parallel implementations for Fruit-80 and using indexing and shifting methods for different throughput. In conclusion, our results show that the area optimization architecture occupies up to 35 slices on Xilinx Spartan-3 FPGA and 18 slices on Xilinx 7 series FPGA, smaller than that of Grain and other common stream ciphers. The optimal throughput/area ratio of the speed optimization architecture is 7.74 Mbps/slice, better than that of Grain v1, which is 5.98 Mbps/slice. The serial implementation of Fruit-80 with round key function occupies only 75 slices on Spartan-3 FPGA. To the best of our knowledge, the result sets a new record of the minimum area in lightweight cipher implementation on FPGA.

Fruit-80, an ultra-lightweight stream cipher with 80-bit secret key, is oriented toward resource constrained devices in the Internet of Things. In this paper, we propose area and speed optimization architectures of Fruit-80 on FPGAs. The area optimization architecture reuses NFSR&LFSR feedback functions and achieves the most suitable ratio of look-up-tables and flip-flops. The speed optimization architecture adopts a hybrid approach for parallelization and reduces the latency of long data paths by pre-generating primary feedback and inserting flip-flops. In conclusion, the optimal throughput-to-area ratio of the speed optimization architecture is better than that of Grain v1. The area optimization architecture occupies only 35 slices on Xilinx Spartan-3 FPGA, smaller than that of Grain and other common stream ciphers. To the best of our knowledge, this result sets a new record of the minimum area in lightweight cipher implementations on FPGA.

Persistent Fault Attack (PFA) is a recently proposed Fault Attack (FA) method in CHES 2018. It is able to recover full AES secret key in the Single-Byte-Fault scenario. It is demonstrated that classical FA countermeasures, such as Dual Modular Redundancy (DMR) and mask protection, are unable to thwart PFA. In this paper, we propose a fast-detection and fault-correction algorithm to prevent PFA. We construct a fixed input and output pair to detect faults rapidly. Then we build two extra redundant tables to store the relationship between the adjacent elements in the S-box, by which the algorithm can correct the faulty elements in the S-box. Our experimental results show that our algorithm can effectively prevent PFA in both Single-Byte-Fault and Multiple-Bytes-Faults scenarios. Compared with the classical FA countermeasures, our algorithm has a much better effect against PFA. Further, the time cost of our algorithm is 40% lower than the classical FA countermeasures.

In recent years, various deep learning techniques have been exploited in side channel attacks, with the anticipation of obtaining more satisfactory attack results. Most of them con-centrate on improving network architectures or putting forward novel metrics, assuming that there are adequate profiling traces available to train an appropriate neural network. However, in practical scenarios, profiling traces are probably insufficient, which makes the network learn deficiently and compromises attack performance. In this paper, we investigate a kind of data augmentation technique, called mixup, and first propose to exploit it in deep-learning based side channel attacks, for the purpose of expanding the profiling set and facilitating the chances of mounting a successful attack. We utilize mixup to generate new traces and perform Correlation Power Analysis for generated traces and original traces. The analysis reveals that the leakage location and leakage intensity between them are consistent. In view of this observation, we consider it feasible to add generated traces to the original profiling set. Our verifying experiments show that mixup is truly capable of enhancing attack performance especially for insufficient profiling traces. Specifically, when the size of the training set is decreased to 30% of the whole set, mixup can almost reduce required attacking traces to half. We test three mixup parameter values and conclude that generally all of them can bring about improvements. Besides, we compare three leakage models and surprisingly discover that least significant bit model, which is less frequently used in previous works, actually surpasses prevalent identity model and hamming weight model in terms of attack results.

With the outbreak of e-mail message leakage events, such as the Hillary Clinton’s Email Controversy, privacy and security of sensitive e-mail information have become users’ primary concern. Encrypted email seems to be a viable solution for providing security, but it will greatly limit their operations. Public encryption with keyword search (PEKS) scheme is a popular technology to incorporate security protection and favorable operability functions together, which can play an important role in searching over encrypted email in a cloud server. In this paper, we propose a practical PEKS scheme named as public-key multi-keyword searchable encryption with hidden structures (PMSEHS). It could enable e-mail receivers to do the multi-keyword and boolean search in the large encrypted email database as fast as possible, without revealing more information to the cloud server. We also give comparative experiments, which demonstrate that our scheme has a higher efficiency in multi-keyword search for encrypted emails.

Advances in signal processing in the encrypted domain and cloud computing have given rise to privacy‐preserving technologies. In recent years, reversible data hiding in encrypted images (RDH‐EI) has received attention from the research community because additional data can be embedded into an encrypted image without accessing its original content, and the encrypted image can be losslessly recovered after extracting the embedded data. Although the recent development of RDH‐EI compatible with homomorphic public key cryptosystems has intensified research interest, most of the existing mature RDH schemes cannot be transplanted to the encrypted domain due to the limitations of the underlying cryptosystems. In this paper, prediction error expansion based RDH‐ED using probabilistic and homomorphic properties of the Paillier cryptosystem is presented. This work implements non‐integer mean value computation in the encrypted domain without any interactive protocol between the content owner and the cloud server. This work presents mathematical detail of pixel prediction (mean), prediction error, error expansion and data embedding in the encrypted domain and data extraction and content recovery in the plain domain. Experimental results from standard test images reveal that the proposed scheme outperforms other state‐of‐the‐art encrypted domain schemes.

Due to its large storage facility and high-end computing capability, cloud computing has received great attention as a huge amount of personal multimedia data and computationally expensive tasks can be outsourced to the cloud. However, the cloud being third-party semi-trusted, is prone to information leakage, raising privacy risks. Signal processing in the encrypted domain has emerged as a new research paradigm on privacy-preserving processing over outsourced data by semi-trusted cloud. In this article, we propose a solution for non-integer mean value computation in the homomorphic encrypted domain without any interactive protocol between the client and the service provider. Using the proposed solution, various image processing operations, such as local smoothing filter, un-sharp masking, and histogram equalization, can be performed in the encrypted domain at the cloud server without any privacy concerns. Our experimental results from standard test images reveal that these image processing operations can be performed without pre-processing, without client-server interactive protocol, and without any error between the encrypted domain and the plain domain.

The Galois/Counter Mode of operation (GCM) is a widely used nonce-based authenticated encryption with associated data mode which provides the birthday-bound security in the nonce-respecting scenario; that is, it is secure up to about 2n/2 adversarial queries if all nonces used in the encryption oracle are never repeated, where n is the block size. It is an open problem to analyze whether GCM security can be improved by using some simple operations. This paper presents a positive response for this problem. Firstly, we introduce two close to optimally secure pseudorandom functions and derive their security bound by the hybrid technique. Then, we utilize these pseudorandom functions that we design and a universal hash function to construct two improved versions of GCM, called OGCM-1 and OGCM-2. OGCM-1 and OGCM-2 are, respectively, provably secure up to approximately 2n/67(n-1)2 and 2n/67 adversarial queries in the nonce-respecting scenario if the underlying block cipher is a secure pseudorandom permutation. Finally, we discuss the properties of OGCM-1 and OGCM-2 and describe the future works.

It has been an active research issue for many years to construct new bent functions. Fork odd with gcd(n, k) = 1 and a ∈ F3n*, the function f (x) = Tr1n(ax((3k+1)/2)) is weakly regular bent over F3n, where Tr1n(·) is the trace function from F3nto F3. This is the well-known Coulter-Matthews bent function. In this paper, we determine the dual function of f (x) completely. As a consequence, we find many classes of ternary bent functions not reported in the literature previously. Such bent functions √ are not quadratic if k > 1 and have (((1 + 5)/2)w+1- ((1 - √5)/2)w+1)/√5 or (((1 +√5)/2)n-w+1- ((1 - √5)/2)n-w+1)/√5 trace terms, where 0n- ((1 - 5)/2)n)/ 5; 2) for the case of k = (n + 1)/2, the number of trace terms is (((1 + 5)/2)n-1- ((1 - 5)/2)n-1)/ 5; 3) for the case of k = (n - 1)/2, the number of trace terms is (((1 + √5)/2)n-1- ((1 - √5)/2)n-1)/√5; 4) for the case of (n, k) = (5t + 4, 4t + 3) or (5t + 1, 4t + 1) with t ≥ 1, the number of trace terms is 8; and 5) for the case of (n, k) = (7t +6, 6t +5) or (7t +1, 6t +1) with t ≥ 1, the number of trace terms is 21. As a byproduct, we find new classes of ternary bent functions with only 8 or 21 trace terms.

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and gcd(n, k) = 1, it is known that the Coulter-Matthews bent function f(x) = T r (ax 3k+1/2) is weakly regular bent over F3n, where a ∈ F3n*, and T r (·) : F3n→ F3is the trace function. In this paper, we investigate the dual function of f (x), aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n = 3t + 1 and k = 2t + 1 with t ≥ 2, the dual function is given by Tr (- x32t+1+3t+1+2/a32t+1+3t+1+1) - x32t+1/a-32t+3t+1+ x2/a-32t+1+3t+1+1); and for the case of n = 3t + 2 and k = 2t + 1 with t≥2,the dual function is given by Tr (-x32t+2+1/a32t+2-3t+1+3- x2.32t+1+3t+1+1/a32t+2+3t+1+3+ x2/a-32t+2+3t+1+3) As a byproduct, we find two new classes of ternary bent functions with only three terms. Moreover, we also prove that in certain cases f (x) is regular bent.

The Transport Layer Security (TLS) protocol is by far the most widely deployed protocol for securing communications and the Internet Engineering Task Force (IETF) is currently developing TLS 1.3 as the next-generation TLS protocol. The TLS standard features multiple modes of handshake protocols and supports many combinational running of successive TLS handshakes over multiple connections. Although each handshake mode is now well-understood in isolation, their composition in TLS 1.2 remains problematic, and yet it is critical to obtain practical security guarantees for TLS. In this paper, we present the first formal treatment of multiple handshakes protocols of TLS 1.3 candidates. First, we introduce a multi-level&stage security model, an adaptation of the BellareRogaway authenticated key exchange model, covering all kinds of compositional interactions between different TLS handshake modes and providing reasonably strong security guarantees. Next, we prove that candidate handshakes of TLS 1.3 draft meet our strong notion of multiple handshakes security. Our results confirm the soundness of TLS 1.3 security protection design. Such a multi-level&stage approach is convenient for analyzing the compositional design of the candidates with different session modes, as they establish dependencies of multiple sessions. We also identify the triple handshake attack of Bhargavan et al. on TLS 1.2 within our multiple handshakes security model. We show generically that the proposed fixes (RFC 7627) for TLS 1.2 offer good protection against multiple handshakes attacks.

Signal processing in the encrypted domain becomes a desired technique to protect privacy of outsourced data in cloud. In this article, we propose a double-cipher scheme to implement nonlocal means (NLM) denoising in encrypted images. In this scheme, one ciphertext is generated by the Paillier scheme, which enables the mean filter, and the other is obtained by a privacy-preserving transform, which enables the nonlocal search. By the privacy-preserving transform, the cloud server can search the similar pixel blocks in the ciphertexts with the same speed as in the plaintexts; thus, the proposed method can be executed fast. To enhance the security, we randomly permutate both ciphertexts. To reduce the denoising complexity caused by random permutation, a random NLM method is exploited in the encrypted domain. The experimental results show that the quality of denoised images in the encrypted domain is comparable to that obtained in the plain domain.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal 2-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for this conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the Lin conjectured ternary sequences are Hadamard equivalent to ternary m-sequences.

We show that there is a very simple approach to determine the 2-adic complexity of periodic binary sequences with ideal two-level autocorrelation. This is the first main result by H. Xiong, L. Qu, and C. Li, IEEE Transactions on Information Theory, vol. 60, no. 4, pp. 2399–2406, Apr. 2014, and the main result by T. Tian and W. Qi, IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 450–454, Jan. 2010.

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal two-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for the conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger's theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the ternary sequences conjectured by Lin are Hadamard equivalent to ternary m-sequences.

An (N, K) codebook C is a set of N unit-norm complex vectors in \BBCK. Optimal codebooks meeting the Welch bound with equality are desirable in a number of areas. However, it is very difficult to construct such optimal codebooks. There have been a number of attempts to construct codebooks nearly meeting the Welch bound with equality, i.e., the maximal cross-correlation amplitude Imax(C) is slightly higher than the Welch bound equality, but asymptotically achieves it for large enough N. In this paper, using difference sets and the product of Abelian groups, we propose new constructions of codebooks nearly meeting the Welch bound with equality. Our methods yield many codebooks with new parameters. In some cases, our constructions are comparable to known constructions.

The Walsh transform of two-level autocorrelation sequences has played an important role in the construction of the set of sequences in which any two sequences are orthogonal. Forp-ary sequences, there are only two basic classes of two-level autocorrelation sequences with no subfield structures for an arbitrary odd primep. One is the class ofp-arym-sequences and the other is the class ofp-ary Helleseth-Gong sequences. In this paper, the Walsh transform of a subclass ofp-ary Helleseth-Gong sequences and the Walsh transform of their particular decimations are completely determined and are shown to be three-valued.

In 2006, Helleseth and Kholosha conjectured and partially proved the existence of a class of ternary weakly regular monomial bent functions and also the expression for the dual bent function up to the sign value. The bentness was finally proved later in 2009 using a complicated technique that employs Stickelberger's theorem. Extensively using the previously found results and approaches, in this paper, a surprisingly short proof for the conjectured expression of the dual is given but without resolving the sign ambiguity. Furthermore, we resolve the sign by finding the trace representation of the dual function.

Hummingbird is a recently proposed lightweight cryptographic algorithm for securing RFID systems. In 2011, Saarinen reported a chosen-IV, chosen-message attack on Hum- mingbird in FSE'll. In this paper, we propose a lightweight remedial scheme in response to the Saarinen's attack. The scheme is quite efficient both in software and hardware since only two cyclic shifts are involved. Using this simple tweak, we can keep the compact design of Hummingbird as well as enhance the security of Hummingbird. Readers are welcome to attack the remedial Hummingbird.

In this paper, some new results are presented on the selective discrete Fourier spectra attack introduced first as the Rønjom-Helleseth attack and the modifications due to Rønjom, Gong, and Helleseth. The first part of this paper fills some gaps in the theory of analysis in terms of the discrete Fourier transform (DFT). The second part introduces the new fast selective DFT attacks, which are closely related to the fast algebraic attacks in the literature. However, in contrast to the classical view that successful algebraic cryptanalysis of LFSR-based stream cipher depends on the degree of certain annihilators, the analysis in terms of the DFT spectral properties of the sequences generated by these functions is far more refined. It is shown that the selective DFT attack is more efficient than known methods for the case when the number of observed consecutive bits of a filter generator is less than the linear complexity of the sequence. Thus, by utilizing the natural representation imposed by the underlying LFSRs, in certain cases, the analysis in terms of DFT spectra is more efficient and has more flexibility than classical and fast algebraic attacks. Consequently, the new attack imposes a new criterion for the design of cryptographic strong Boolean functions, which is defined as the spectral immunity of a sequence or a Boolean function.

In this paper, we propose high-rate distributed space-time-frequency codes (DSTFCs) to exploit maximum achievable diversity gains over frequency-selective fading channels. The proposed designs achieve full-rate for any number of cooperative nodes, and allow channel variations over multiple OFDM blocks within one DSTFC codeword. We analyze diversity gains of DSTFCs through both conditional and average pairwise error probability (PEP), and we proposes better design criteria based on one-side channel conditional PEP. We show that the difference between the frequency-selective channel orders of source-to-relay and relay-to-destination links may provide extra diversity advantages, thus additional performance gains. Through Monte-Carlo simulations, we demonstrate that proposed high-rate DSTFCs provide notable diversity advantages over existing designs.

Pseudorandom sequences with good correlation properties are widely used in communications and cryptography. The search of new sequences with two-level autocorrelation has been a very interesting problem for decades. In 2002, Gong and Golomb proposed the iterative decimation-Hadamard transform (DHT) which is an useful tool to study two-level autocorrelation sequences. They showed that for all odd n ≤ 17, using the second-order decimation-Hadamard transform, and starting with a single binary m-sequence, all known two-level autocorrelation sequences of period 2n-1which have no subfield factorization can be obtained. In this paper, we present a new class of ternary or quaternary sequences with two-level autocorrelation using the second-order decimation-Hadamard transform. The period of such sequences is 2n-1.

Sequence families with zero or low correlation zone can be used in the quasi-synchronous code-division multiple-access (QS-CDMA) communication systems. Interleaving techniques are very useful for sequence design. In this paper, we present a general construction of sequence families with zero or low correlation zone using interleaving techniques and complex Hadamard matrices. The component sequences are perfect or ideal two-level. In two cases, we construct the shift sequences: 1) P|L; 2) P is even, and L ¿ P/2 ( mod P), which results in sequence families with zero or low correlation zone of parameters (NP, MP, L, P¿), where N is the period of component sequences, M is the number of inequivalent shift sequences, and ¿ = 0 or 1. The conditions are derived under which the new construction is optimal. Some examples are also given to specify the new construction.

Sequence families with zero or low correlation zone can be used in the quasi-synchronous code-division multiple-access (QS-CDMA) communication systems. Interleaving techniques are very useful for sequence design. In this paper, we present a general construction of sequence families with zero or low correlation zone using interleaving techniques and complex Hadamard matrices. The component sequences are perfect or ideal two-level. In two cases, we construct the shift sequences: 1) P|L; 2) P is even, and L ¿ P/2 (mod P). The conditions are derived under which the new construction is optimal. Some examples are also given to specify the new construction.

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and largek-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and thek-error linear complexity of a periodic sequence by Ding By considering the orders of the divisors ofxN-1 over\BBFq, we obtain three main results which hold for much largerkthan those of Niederreiter : a) sequences with maximal linear complexity and almost maximalk-error linear complexity with general periods; b) sequences with maximal linear complexity and maximalk-error linear complexity with special periods; c) sequences with maximal linear complexity and almost maximalk-error linear complexity in the asymptotic case with composite periods. Besides, we also construct some periodic sequences with low correlation and largek-error linear complexity.

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and large k-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and the k-error linear complexity of a periodic sequence by Ding et al.. Using the entropy function in coding theory, we obtain three main results which hold for much larger k than those of Niederreiter et al.: a) sequences with maximal linear complexity and almost maximal k-error linear complexity with general periods; b) sequences with maximal linear complexity and maximal k-error linear complexity with special periods; c) sequences with maximal linear complexity and almost maximal k-error linear complexity in the asymptotic case with composite periods.

A significant difference between the linear complexity and the 2-adic complexity of periodic binary sequences is pointed out in this correspondence. Based on this observation, we present the concept of the symmetric 2-adic complexity of periodic binary sequences. The expected value of the 2-adic complexity is determined, and a lower bound on the expected value of the symmetric 2-adic complexity of periodic binary sequences is derived. We study the variance of the 2-adic complexity of periodic binary sequences, and the exact value for it is given. Because the k-adic complexity of periodic binary sequences is unstable, we present the concepts of thekappa-error 2-adic complexity and the k-error symmetric 2-adic complexity, and lower bounds on them are also derived. In particular, we give tighter upper and lower bounds for the minimum k-adic complexity of l-sequences by substituting two symbols within one period.

In this correspondence, we construct some new quadratic bent functions in polynomial forms by using the theory of quadratic forms over finite fields. The results improve some previous work. Moreover, we solve a problem left by Yu and Gong in 2006.

Following the idea of Xing et al., we investigate a general method for constructing families of pseudorandom sequences with low correlation and large linear complexity from elliptic curves over finite fields in this correspondence. With the help of the tool of exponential sums on elliptic curves, we study their periods, linear complexities, linear complexity profiles, distributions of r-patterns, periodic correlation, partial period distributions, and aperiodic correlation in detail. The results show that they have nice randomness.

An upper bound for the incomplete exponential sums over Galois rings is derived explicitly. Based on the incomplete exponential sums, we analyze the partial period properties of some binary sequences derived from Z/sub 2//sup l/ in detail, such as the Kerdock-code binary sequences and the highest level sequences of primitive sequences over Z/sub 2//sup l/. The results show that the partial period distributions and the partial period independent r-pattern distributions of these binary sequences are asymptotically uniform. Nontrivial upper bounds for the aperiodic autocorrelation of these sequences are also given.

Recently Xing et al constructed some families of binary sequences with low correlation and large linear complexity by making use of the theory of Artin-Schreier extensions of function fields. In this paper, we present a new construction by using the theory of Kummer extensions of function fields. The analysis shows than they have large periods, large linear complexities, and low correlations. In some cases, our method is better than that of Xing et al