paper develops the theory and constructions of polyphase zero-ambiguity-zone (ZAZ) sequences for ISAC waveforms, enabling the ZAZ shape to be designed over delay–Doppler regions of interest and supporting flexible (including multi-mode) sensing–communication operation. We first prove that a polyphase sequence with an optimal rectangular auto-ZAZ must be a member of some uncorrelated optimal ZCZ sequence family, and conversely, any member of an uncorrelated optimal ZCZ sequence family has an optimal rectangular auto-ZAZ (Theorems 1, 2 and 3). We generalize the optimality condition on the rectangular ZAZ to that on centrally symmetric convex ZAZs in general (Theorem 4). We propose some constructions of families of polyphase sequences with a strictly or asymptotically optimal rectangular ZAZ (Theorem 1), dual asymptotically optimal rectangular ZAZs (Theorems 5 and 6), and asymptotically optimal rhombic or hexagonal ZAZ (Remarks 5 and 6) from the flexible ZAZ configuration

The operation of computing$n$scalar multiplications in an elliptic curve group and then adding them together is called n-scalar multiplication.$n$-scalar multiplication is the essential operation for proof generation and verification in pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge protocols, which enable the privacy-preserving features in blockchain applications. This paper proposed a method to compute$n$-scalar multiplication taking advantage of$3n$precomputed points. When instantiating over BLS12-381 curve, for$n=2^{c}\ (10\leq c\leq 22)$, which covers the majority of our purported applications, the proposed method showed 2.59% ∼ 12.26% theoretical speed improvement and demonstrated 1.63% ∼ 11.54% experimental improvement against Pippenger's bucket method.

Bent functions have flat absolute Walsh-Hadamard spectra and negabent functions have flat absolute nega-Hadamard spectra. Those properties are wide applications in cryptography for constructing cryptographically strong functions and error correcting codes for better performance. In this paper, we present a new construction of quadratic and cubic negabent functions over finite fields. Those functions can be represented as the sum of the three components: one is the trace function of the monomial term λx3or it multiplying by the trace function of x; the second, the sum of all the quadratic monomial functions except for one; and the third, the product of two linear functions where the parameter λ and variable x belong to an arbitrary binary finite field of 2nelements for n odd.

In this paper, we further investigate the constructions of complementary sequence sets (CSSs) and complete complementary codes (CCCs) by Butson-type Hadamard matrices. By taking the algebraic structure of Butson-type Hadamard (BH) matrices into consideration, we obtain the explicit representation of the$\delta $-linear terms and$\delta $-quadratic terms, which are ingredients to construct CSSs and CCCs. In particular, we derive the$\delta $-quadratic terms determined by DFT matrices and BH matrices constructed from 2-level autocorrelation sequences, which yields two type of new contructions. We show that inequivalent BH matrices produce different CSSs and CCCs, which proves that our constructed CSSs and CCCs are new. As a consequence of the first type of the constructions, not only a large number of$p$-ary CSSs and CCCs of size$p$($p$prime) have been proposed, which were never reported in the literature, but also a theory linking these CSSs of$p$-ary sequences and the generalized Reed-Muller codes proposed by Kasami et al. is shown. These codes enjoy good error-correcting capability, tightly controlled PMEPR, and significantly extend the range of coding options for applications of OFDM using$p^{n}$subcarriers. As a consequence of the second type of the constructions, we reveal an extremely fascinating hidden connection between the sequences in aperiodic CSSs and CCCs and the sequences with ideal period 2-level autocorrelation, through their trace representations and permutation polynomials over finite fields.

The set of perfect sequences with optimal cross-correlation has applications in communication and radar systems. Many different constructions, which are called optimal sets of perfect sequences according to Sarwate bound, have been studied in the literature. However, Song et al. and Zhang et al. recently showed that the set size of these constructions can be improved, since the term related to size vanishes for perfect sequences in Sarwate bound. Until now, we don’t know whether the set size of these constructions is optimal, though they are all called optimal sets. We studied the problem of the set size of perfect sequences with optimal cross-correlation, and showed that the set size must be upper bounded by the length of the perfect sequences in this paper.

Abstract We present a new zero-knowledge succinct argument of knowledge (zkSNARK) scheme for Rank-1 Constraint Satisfaction (RICS), a widely deployed NP-complete language that generalizes arithmetic circuit satisfiability. By instantiating with different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range fromO(log2N) to O(N) O\left( {\sqrt N } \right) depending on the underlying polynomial commitment schemes when applied to anN-gate arithmetic circuit. All these schemes do not require a trusted setup. It is plausibly post-quantum secure when instantiated with a secure collision-resistant hash function. We report on experiments for evaluating the performance of our proposed system. For instance, for verifying a SHA-256 preimage (less than 23k AND gates) in zero-knowledge with 128 bits security, the proof size is less than 150kB and the verification time is less than 11ms, both competitive to existing systems.

The researches of Golay complementary sequences (GCSs) over 16 and 64 quadrature amplitude modulation (QAM) from 2001 to 2008 were generalized to$4^{q} $-QAM GCSs of length$2^{m}$by Li (the generalized cases I-III for$q\ge 2$) in 2010 and Liu et al. (the generalized cases IV-V for$q\ge 3$) in 2013. Those sequences are presented by the combination of the quaternary standard GCSs and compatible offsets. By providing new compatible offsets based on the factorization of the integer$q$, we propose two new constructions of$4^{q} $-QAM GCSs, which have the generalized cases I-V as special cases. The numbers of the proposed GCSs are equal to the product of the number of the quaternary standard GCSs and the number of the compatible offsets. Denote the number of prime factors of$q$counted with multiplicity by$\Omega (q)$. The number of new offsets in our first construction is lower bounded by a polynomial of$m$with degree$\Omega (q)$, while the numbers of offsets in the generalized cases I-III and IV-V are a linear polynomial and a quadratic polynomial of$m$, respectively. If$q$has a prime factor larger than 2, the number of new offsets in our second construction is lower bounded by a polynomial of$m$with degree$\Omega (q)+1$. As an example, the new offsets in our two constructions for$q=6$, whose number is bounded by a cubic polynomial, is also given. The proof in this paper implies that all the mentioned GCSs over QAM can be regarded as projections of Golay complementary arrays of size$2\times 2\times \cdots \times 2$.

Linear map commitments allow the prover to commit to a vector, with the ability to prove the image of a linear map acting on the vector. In this paper, we propose linear map commitments with updatable feature and perfectly hiding property. Updatable feature means that the prover can update the commitment more efficiently than recompute the commitment when some of the entries in the committed vector are changed. Perfectly hiding property ensures the commitment reveals no information about the committed vector before opening. Then we present the implementation of our updatable linear map commitment (ULMC) over the 256-bit BN curve recommended in the SM9 standard, which provides around 100-bit security. The implementation shows that our ULMC schemes are efficient enough to support the elementary database constructions that simultaneously permit batching membership test, linear combination test, updatable feature and authenticity. Finally, we show that the ULMC-powered elementary databases are capable of supporting various applications where privacy and trust are the first priority such as exam result management systems, Internet of Things (IoT) management systems and business operations between banks and enterprises.

A new method to construct q-ary complementary sequence sets (CSSs) and complete complementary codes (CCCs) of size N is proposed by using desired para-unitary (PU) matrices.The concept of seed PU matrices is introduced and a systematic approach on how to compute the explicit forms of the functions in constructed CSSs and CCCs from the seed PU matrices is given.A general form of these functions only depends on a basis of the functions from ZN to Zq and representatives in the equivalent class of Butson-type Hadamard (BH) matrices.Especially, the realization of Golay pairs from the our general form exactly coincides with the standard Golay pairs.The realization of ternary complementary sequences of size 3 is first reported here.For the realization of the quaternary complementary sequences of size 4, almost all the sequences derived here are never reported before.Generalized seed PU matrices and the recursive constructions of the desired PU matrices are also studied, and a large number of new constructions of CSSs and CCCs are given accordingly.From the perspective of this paper, all the known results of CSSs and CCCs with explicit GBF form in the literature (except non-standard Golay pairs) are constructed from the Walsh matrices of order 2.This suggests that the proposed method with the BH matrices of higher orders will yield a large number of new CSSs and CCCs with the exponentially increasing number of the sequences of low peak-to-mean envelope power ratio.

The previous constructions of quadrature amplitude modulation (QAM) Golay complementary sequences (GCSs) were generalized as 4q-QAM GCSs of length 2mby Li (the generalized cases I-III for q ≥ 2) in 2010 and Liu (the generalized cases IV-V for q ≥ 3) in 2013 respectively. Those sequences are given by the weighted sum of q quaternary standard GCSs, which is represented as q-dimensional vectorial generalized Boolean functions (V-GBFs). In this paper, we present a new construction for 4q-QAM GCSs of length 2m. The new construction includes the generalized cases I-III as special cases. If q is a composite number, a great number of new GCSs other than the sequences in the generalized cases I-V will arise. For the cases q = 4 and q = 6, we show that the ratios of the number of new GCSs and the generalized cases I-V are greater than seven and six respectively if m is large enough.

A binary de Bruijn sequence is a sequence of period 2n in which every binary n-tuple occurs exactly once in each period. A de Bruijn sequence has good randomness properties, such as long period, ideal tuple distribution, and high linear complexity, and can be generated by a nonlinear feedback shift register (NLFSR). Finding an efficient NLFSR that can generate a de Bruijn sequence with a long period is a significant challenge. “Composited construction” is a technique for constructing a de Bruijn sequence of period 2n+kby an NLFSR from a de Bruijn sequence of period 2nthrough a composition operation repeatedly applying k times. The goal of this article is to further investigate the composited construction of de Bruijn sequences with efficient hardware implementations, and determine randomness properties such as linear complexity. Our contributions in this article are as follows. First, we present a generalized construction of composited de Bruijn sequences that is constructed by adding a combination of conjugate pairs of different lengths in the feedback function of the composited construction, which results in generating a class of de Bruijn sequences of size 2k, whereas the original composited construction can generate only two sequences. Second, we investigate the linear complexity and the correlation property of the new class of de Bruijn sequences. We prove theoretically that the linear complexity of this class of de Bruijn sequences is optimal or close to optimal. Interestingly, we also prove that the linear complexities of all the sequences of this class are equal, which strengthens Etzion's conjecture (JCTA 1985, IEEE-IT 1999) about the number of de Bruijn sequences with equal linear complexity. This is the first known construction of de Bruijn sequences of an arbitrarily long period whose linear complexities are determined theoretically. Finally, we implement our construction in hardware to demonstrate its practicality. We synthesize our implementations for a 65 nm ASIC and a Xilinx Spartan FPGA and present hardware areas, and performances of de Bruijn sequences of periods in the range of 2160to 21056. For instance, a class of de Bruijn sequences of period 2160(resp. 2288) can be implemented with an area of 3.43 (resp. 6.71) kGEs in 65 nm ASIC, and 83 (resp. 229) slices in Spartan6 FPGA.

In this paper, we study a class of binary nonlinear feedback shift register sequences generated by cascaded feedback registers, one is an LFSR and the other one generates a de Bruijn sequence. The cycle structure (in particular, the initial state of each cycle) is determined by solving a system of linear equations. As an application, we can generate de Bruijn sequences of large period algorithmically.

Abstract A major line of research on blockchains is geared towards enhancing the privacy of transactions through anonymity using generic non-interactive proofs. However, there is a good cluster of application scenarios where complete anonymity is not desirable and accountability is in fact required. In this work, we utilize non-interactive proofs of knowledge of elliptic curve discrete logarithms to present membership and verifiable encryption proof, which offers plausible anonymity when combined with the regular signing process of the blockchain transactions. The proof system requires no trusted setup, both its communication and computation complexities are linear in the number of set members, and its security relies on the discrete logarithm assumption. As a use-case for this scenario, we present Mesh which is a blockchain-based framework for supply chain management using RFIDs. Finally, the confidentiality of the transacted information is realized using a lightweight key chaining mechanism implemented on RFIDs. We formally define and prove the main security features of the protocol, and report on experiments for evaluating the performance of the modified transactions for this system.

Complementary sequence sets (CSSs) and complete complementary codes (CCCs) have many applications in science and engineering, especially in wireless communications. A construction of CSS and CCC, having size M = 2mand length MK, where m and K are positive integers, is presented. The proposed construction is a generalized paraunitary (PU) algorithm that greatly increases the number of permutations from K! to (mK)! compared to those of previous PU constructions. Moreover, this new construction can be generalized to the case M = pm, where p is a positive integer. The increase in the number of permutations means that a wide range of CCCs and CSSs can be obtained.

This paper explores tower field constructions and hardware optimizations for the WG-16 stream cipher. The constructions${\mathbb {F}}_{(((2^2)^2)^2)^2}$and${\mathbb {F}}_{(2^{4})^4}$were chosen because their small subfields enable high speed arithmetic implementations and their regularity provides flexibility in pipeline granularity. A design methodology is presented where the tower field constructions guide how to proceed systematically from algebraic optimizations, through initial hardware implementation, selection of submodules, pipelining, and finally detailed hardware optimizations to increase clock speed. The highest frequency WG(16, 32) keystream generator, obtained for the 65 nm ASIC library, reached a clock speed of 2.44 GHz at 26.3 kGE, and the smallest area keystream generator achieved a clock speed of 0.33 GHz at 9.9 kGE. The highest frequency FPGA implementation on a Xilinx Spartan 6 reached a clock speed of 256 MHz using 631 slices. In addition, the paper demonstrates that LFSR feedback polynomials can be optimized to increase security without hurting performance, and retiming optimizations can be used to increase clock speed without increasing area.

The security of highly resource constrained applications is often viewed in the literature from a single aspect of a specific cryptographic primitive. More precisely, most of the proposed lightweight cryptographic primitives focus on providing a single functionality within the available hardware area dedicated for security purposes. In this paper, we argue that for such applications, a cryptographic primitive that follows the cryptographic minimal design strategy maybe the only realistically adopted security solution where there is a constrained GE budget for all security functionalities. Indeed, it is reasonable, if not desirable, for the adopted cryptographic design to have well justified building components and to provide minimal overhead for multiple cryptographic functionalities including encryption, hashing, authentication, and pseudorandom bit generation. Following such a strategy, we propose the sLiSCP family of lightweight cryptographic permutations which employs two of the most hardware efficient and extensively cryptanalyzed constructions, namely a 4-subblock Type-2 Generalized Feistel-like Structure (GFS) and round-reduced unkeyed Simeck. In addition to the hardware efficiency, we follow restrictive security design goals which enable us to provide resistance against differential and linear cryptanalysis, as well as guaranteed resistance to diffusion-based, algebraic, and self-symmetry distinguishers, and accordingly, we claim that there exist no structural distinguishers for sLiSCP-b with a complexity below 2b=2 where b is the state size. Moreover, we present the sLiSCP duplex sponge mode to illustrate how the permutations can be used in a unified design that provides (authenticated) encryption, hashing, and pseudorandom bit generation functionalities. Finally, we report two efficient parallel hardware implementations for the sLiSCP unified duplex sponge mode when using sLiSCP-192 (resp. sLiSCP-256) in CMOS 65 nm ASIC with area of 2289 (resp. 3039) GE and a throughput of 29.62 (resp. 44.44) kbps, and their areas in CMOS 130 nm are 2498 (resp. 3319) GE.

The emerging areas in which highly resource constrained devices are interacting wirelessly to accomplish tasks have led manufacturers to embed communication systems in them. Tiny low-end devices such as sensor networks nodes and Radio Frequency Identification (RFID) tags are of particular importance due to their vulnerability to security attacks, which makes protecting their communication privacy and authenticity an essential matter. In this work, we present a lightweight do-it-all cryptographic design that offers the basic underlying functionalities to secure embedded communication systems in tiny devices. Specifically, we revisit the design approach of the sLiSCP family of lightweight cryptographic permutations, which was proposed in SAC 2017. sLiSCP is designed to be used in a unified duplex sponge construction to provide minimal overhead for multiple cryptographic functionalities within one hardware design. The design of sLiSCP follows a 4-subblock Type-2 Generalized Feistel-like Structure (GFS) with unkeyed round-reduced Simeck as the round function, which are extremely efficient building blocks in terms of their hardware area requirements. In S L I SCP-light, we tweak the GFS design and turn it into an elegant Partial Substitution-Permutation Network construction, which further reduces the hardware areas of the S L I SCP permutations by around 16% of their original values. The new design also enhances the bit diffusion and algebraic properties of the permutations and enables us to reduce the number of steps, thus achieving a better throughput in both the hashing and authentication modes. We perform a thorough security analysis of the new design with respect to its diffusion, differential and linear, and algebraic properties. For S L I SCP-light-192, we report parallel implementation hardware areas of 1,820 (respectively, 1,892)GE in CMOS 65 nm (respectively, 130 nm ) ASIC. The areas for S L I SCP-light-256 are 2,397 and 2,500GE in CMOS 65 nm and 130 nm ASIC, respectively. Overall, the unified duplex sponge mode of S L I SCP-light-192, which provides (authenticated) encryption and hashing functionalities, satisfies the area (1,958GE), power (3.97μ W ), and throughput (44.4kbps) requirements of passive RFID tags.

In this paper, we present some fundamental concepts and theoretical advances attributable to Solomon Golomb, together with the history and applications of this paper to communications, coding, and cryptography, along with some long-standing conjectures. Examples include the first engineering problem relating to feedback shift-register sequences that Sol Golomb was asked to solve in the mid-1950s. This paper covers m-sequences and Golomb's three randomness postulates, the cross-correlation of m-sequences, the exp-Golomb code, the Golomb ruler, Costas arrays, Golomb invariants, polyominoes, the distribution of prime numbers, and irreducible polynomials.

In this paper, the discrete Fourier transform (DFT) of Boolean functions over the complex field is introduced and the locations of zero-valued Fourier spectrum are studied. Then a Fourier spectral characterization of correlation immune and resilient Boolean functions is investigated. It is shown that a Boolean function f is mth-order correlation immune if and only if the Fourier spectrum of f under any permutation of variables (or the equivalence class of f defined by Golomb in 1959) vanishes at a specified location. This is an analog of using Walsh-Hadamard spectra to characterize correlation immunity of the Boolean functions. In particular, if f is a symmetric function, f is correlation immune if and only if its Fourier spectrum vanishes at a specified location. Similarly, zero-valued Fourier spectrum can also be used to characterize resilient functions. The application of the Fourier spectral analysis on studying the peak-to-mean envelope power ratio of the sequences is also addressed.

Real world physical shopping offers customers the privilege of maintaining their privacy by giving them the option of using cash, and thus providing no personal information such as their names and home addresses. On the contrary, electronic shopping mandates the use of all sorts of personally identifiable information for both billing and shipping purposes. Cryptocurrencies such as Bitcoin have created a stimulated growth in private billing by enabling pseudonymous payments. However, the anonymous delivery of the purchased physical goods is still an open research problem. In this work, we present a blockchain-based physical delivery system called Lelantos1 that within a realistic threat model, offers customer anonymity, fair exchange and merchant-customer unlinkability. Our system is inspired by the onion routing techniques which are used to achieve anonymous message delivery. Additionally, Lelantos relies on the decentralization and pseudonymity of the blockchain to enable pseudonymity that is hard to compromise, and the distributed consensus mechanisms provided by smart contracts to enforce fair irrefutable transactions between distrustful contractual parties.

A binary de Bruijn sequence with period 2nis a sequence in which every tuple of n bits occurs exactly once. De Bruijn sequence generators have randomness properties that make them attractive for pseudorandom number generators and as building blocks for stream ciphers. Unfortunately, it is very difficult to find de Bruijn sequence generators with long periods (e.g., 2128) and most known de Bruijn sequence generators are computationally quite expensive. In this article, we present “OcDeb-k-n” and the first hardware implementation of de Bruijn sequence generators. OcDeb-k-n efficiently computes a composited de Bruijn sequence where k levels of composition are added to a de Bruijn sequence of period 2n. Numerically, OcDeb reduces the bit operations used for computing the feedback function significantly from Θ(k2+ nk) to Θ(k log k + logn). Furthermore, it enables efficient parallelization and hardware retiming. Comprehensive result analysis is conducted for 65 nm ASIC technology. For example, OcDeb-32-32 has an area of 643 GE with 1.45 Gbps performance, and with parallelization it generates up to 25.4 Gbps at the cost of 4,787 GE. The area of OcDeb-512-32 generating a de Bruijn sequence of period 2544is 7,304 GE and the performance is 1.25 Gbps.

In this paper, we propose a secure transmission protocol for two users exchanging their respective information in an n-hop MIMO Ad hoc network. By exploiting the properties of the transmission medium in the physical layer, three channel models are utilized to provide secure transmission, namely one-way relay channel, two-way untrusted relay channel, and multiple access channel. Using these channel models, we design a basic protocol with a minimized time slot cost, i.e. n+1. Based on this basic protocol, we show that the attacker, either untrusted relay or external eavesdropper, can only obtain a summed signal in each time slot, and this summed signal cannot be decomposed to recover the individual information from the users. We then present cryptographic analysis for the first time to identify a weakness which is common for all known security schemes based on the summed signal. Thirdly, we introduce an evolutionary protocol proposed with two rounds of interlaced information exchange, which defeats this weakness. Finally, the simulation is performed to demonstrate the theoretical analysis.

Abstract After the concept of the active wiretapper was proposed, integrity protection became more important than ever before. Therefore, message authentication code, a method that protects the message from being modified in an undetectable way, attracts more attention nowadays. In this paper, we propose two new message authentication codes based on almost perfect nonlinear functions and stream ciphers. The security of both new constructions is proved by giving upper bounds of the probability of the successful substitution forgery attacks against our new message authentication codes, and these upper bounds are negligible. We implement our algorithms and compare their time consumption with the time consumption of EIA1, the message authentication code used in the 4G LTE system. The results show that our algorithms are overwhelmingly faster than EIA1. Moreover, our new constructions are resistant to cycling and linear forgery attacks, which can be applied to EIA1. Copyright © 2016 John Wiley & Sons, Ltd.

A binary de Bruijn sequence of order$n$is a sequence of zeros and ones of period$2^n$that contains every binary$n$-tuple exactly once in a period of the sequence. A composited construction of a de Bruijn sequence is a construction of a nonlinear feedback shift register (NLFSR) that generates a de Bruijn sequence where the composited feedback function of the NLFSR is the sum of a feedback function with$k$th order composition and a sum of$(k+1)$product-of-sum terms. The goals of this article are to perform a profound analysis of composited de Bruijn sequences for use in cryptography and find an efficient implementation of the composited feedback function. We first determine the lower bound of the linear complexity of a composited de Bruijn sequence and then conduct a profound analysis on the composited construction by introducing the notion of the higher order$D$-morphic preimages of a binary sequence. Our analysis aims at the reconstruction of a composited de Bruijn sequence from a segment known as$k$th order$D$-morphic order$n$de Bruijn preimages ($(n,k)$-DMDPs) of length$(2^n+k)$and$k$th order$D$-morphic order$n$$m$-sequence preimages ($(n,k)$-DMMPs) of length$(2n+k)$for a nonlinearly and linearly generated composited de Bruijn sequence, respectively. We also provide the success probability of finding an$(n,k)$-DMMP/DMDP from a composited de Bruijn sequence for the reconstruction. Furthermore, we develop a new iterative technique with its parallel extension for computing the feedback function and the new technique is faster than other known techniques for producing de Bruijn sequences of long period. In addition, we present three instances of composited de Bruijn sequences of period$2^{64}$together with their software implementations and performances.

With the advent of ubiquitous computing and the Internet of Things (IoT), the security and privacy issues for various smart devices such as radio-frequency identification (RFID) tags and wireless sensor nodes are receiving increased attention from academia and industry. A number of lightweight cryptographic primitives have been proposed to provide security services for resource-constrained smart devices. As one of the core primitives, a cryptographically secure pseudorandom number generator (PRNG) plays an important role for lightweight embedded applications. The most existing PRNGs proposed for smart devices employ true random number generators as a component, which generally incur significant power consumption and gate count in hardware. In this article, we present Warbler family, a new pseudorandom number generator family based on nonlinear feedback shift registers (NLFSRs) with desirable randomness properties. The design of the Warbler family is based on the combination of modified de Bruijn blocks together with a nonlinear feedback Welch-Gong (WG) sequence generator, which enables us to precisely characterize the randomness properties and to flexibly adjust the security level of the resulting PRNG. Some criteria for selecting parameters of the Warbler family are proposed to offer the maximum level of security. Two instances of the Warbler family are also described, which feature two different security levels and are dedicated to EPC C1 Gen2 RFID tags and wireless sensor nodes, respectively. The security analysis shows that the proposed instances not only can pass the cryptographic statistical tests recommended by the EPC C1 Gen2 standard and NIST but also are resistant to the cryptanalytic attacks such as algebraic attacks, cube attacks, time-memory-data tradeoff attacks, Mihaljević et al.’s attacks, and weak internal state and fault injection attacks. Our ASIC implementations using a 65nm CMOS process demonstrate that the proposed two lightweight instances of the Warbler family can achieve good performance in terms of speed and area and provide ideal solutions for securing low-cost smart devices.

In this paper, we present a generalized framework for active eavesdropping in a frequency hopping spread spectrum passive radio frequency identification system. In our model, there exists an adversarial reader who is able to transmit its own continuous wave signal outside the frequency band of the legitimate reader. Due to the fact that under backscatter modulation, the tag cannot distinguish different frequencies and simply sets the impedance in its circuitry to either low or high to reflect a bit of 1 or 0, and the adversarial reader's received signal is a weighted sum of the response to both its own signal and the legitimate reader's signal. Using this model, we provide a theoretical analysis of the capability of the adversarial reader in terms of the decoding error probability for slow frequency and fast frequency hopping systems. We derive analytic formulas and conduct experiments using software defined radios that act as the legitimate reader, the adversarial reader, and Intel Wireless Identification Sensing Platform tags with parameters as specified in EPC Gen2. Simulations are also used to validate our findings. We find from the theoretical analysis as well the experimental results that the active eavesdropper can achieve a better decoding error rate than a conventional passive eavesdropper, even in the case that the eavesdropper's signal is a low power signal.

We propose two practical and provably secure password hashing algorithms, Pleco and Plectron. They are built upon well-understood cryptographic algorithms, and combine advantages of symmetric and asymmetric primitives. By employing the Rabin cryptosystem, we prove that the one-wayness of Pleco is at least as strong as the hard problem of integer factorization. In addition, both password hashing algorithms are designed to be sequential memory-hard, in order to thwart large-scale password cracking by parallel hardware, such as GPUs, FPGAs, and ASICs. Moreover, the total computation and memory consumptions of Pleco and Plectron are tunable through their cost parameters.

Abstract In 1992, a non‐interactivek‐securem‐conference protocol based on anm‐variate polynomial has been proposed. Each user needs to store a (m − 1)‐polynomial having degreekas a private share. A secret conference key involvingmusers can be computed by each conference member non‐interactively using each private share. There is no overhead to exchange information in order to establish a conference key. However, the storage space of each user is exponentially proportional to the group size of the conference. In this paper, we propose a key establishment protocol using a multivariate polynomial inZN, whereNis a RSA modulus. One unique feature of using this special type of polynomials for conference key protocol is that the storage space of each user is fixed and is independent to the group size of the conference. User can use their shares obtained from a key generation center initially to establish conference keys consisting of different users. Furthermore, we propose two applications to demonstrate the importance of using this special type of polynomials to design solutions. One is the private reconstruction of secret in a secret sharing scheme over network, and the other is the secure group communication. Copyright © 2014 John Wiley & Sons, Ltd.

The WG stream ciphers are based on the WG (Welch-Gong) transformation and possess proved randomness properties. In this paper we propose nine new hardware designs for the two classes of WG(29,11) and WG-16. For each class, we design and implement three versions of standard, pipelined and serial. For the first time, we use the polynomial basis (PB) representation to design and implement the WG(29,11) and WG-16. We consider traditional PB multiplier for the WG(29,11), and, the traditional and Karatsuba multipliers for the WG-16. For efficient field operations, we propose an irreducible trinomial for the WG(29,11). For the WG-16, a new formulation of its permutation which requires only 8 multipliers is introduced. In these designs, the multipliers in the transforms are further reduced by utilizing a novel computation for the trace of the multiplication of two field elements. We have implemented the proposed designs in ASIC using CMOS 65 nm technology. The results show that the proposed standard WG(29,11) consumes less area and slightly enhances the normalized throughput, compared to the existing counterparts. For the WG-16, throughput of the proposed pipelined instance outperforms the previous designs. Moreover, the speed of the proposed WG-16 designs meet the peak bit rates for the 4 G specifications.

In this paper, we propose a new encryption scheme for OFDM systems. The reason for physical layer approach is that it has the least impact on the system and is the fastest among all layers. This scheme is computationally secure against the adversary. It requires less key streams compared with other approaches. The idea comes from the importance of orthogonality in OFDM symbols. Destroying the orthogonality create intercarrier interferences. This in turn cause higher bit and symbol decoding error rate. The encryption is performed on the time domain OFDM symbols, which is equivalent to performing nonlinear masking in the frequency domain. Various attacks are explored in this paper. These include known plaintext and ciphertext attack, frequency domain attack, time domain attack, statistical attack and random guessing attack. We show our scheme is resistant against these attacks. Finally, simulations are conducted to compare the new scheme with the conventional cipher encryption.

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.

An important and well-studied problem with many applications in communication systems is to find sequences with good correlation property that means auto- and cross-correlations of the sequences are all very small comparing with their periods. This paper focuses on sequences of period 2r- 1(r>> 1) with infinite third depth and shows that the difference operator really works with the interleaving technique on producing sequences with good correlation property and long period N = 22r-2r+1+1, which are constructed from 2-level autocorrelation sequences of period 2r- 1 except m-sequences. The method is lightweight since the computational complexity is O(p√N) and only the XOR logical operator is used.

By leveraging and modifying ciphertext-policy attribute based encryption (CP-ABE) and OAuth, we propose a new authorization scheme, called fuzzy authorization, to facilitate an application registered with one cloud party to access data residing in another cloud party. The new proposed scheme enables the fuzziness of authorization to enhance the scalability and flexibility of file sharing by taking advantage of the one-to-one correspondence between linear secret-sharing scheme (LSSS) and generalized Reed Solomon (GRS) code. Furthermore, by conducting attribute distance checking and distance adjustment, operations like sending attribute sets and satisfying an access tree are eliminated. In addition, the automatic revocation is realized with update of TimeSlot attribute when data owner modifies the data. The security of the fuzzy authorization is proved under the d-BDHE assumption. In order to measure and estimate the performance of our scheme, we have implemented the protocol flow of fuzzy authorization with OMNET++ 4.2.2 and realized the cryptographic part with pairing-based cryptography (PBC) library. Experimental results show that fuzzy authorization can achieve fuzziness of authorization among heterogeneous clouds with security and efficiency.

Frequency-hopping sequences (FHSs) are employed to mitigate the interferences caused by the hits of frequencies in frequency-hopping spread spectrum systems. In this paper, we present two new constructions for FHS sets. We first give a new construction for FHS sets of length nN for two positive integers n and N with gcd(n, N) = 1. We then present another construction for FHS sets of length (q - 1)N, where q is a prime power satisfying gcd(q - 1, N) = 1. By these two constructions, we obtain infinitely many new optimal FHS sets with respect to the Peng-Fan bound as well as new optimal FHSs with respect to the Lempel-Greenberger bound, which have length nN or n(q -1)N. As a result, a great deal of flexibility may be provided in the choice of FHS sets for a given frequency-hopping spread spectrum system.

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.

In this paper, some questions on the distribution of the peak-to-mean envelope power ratio (PMEPR) of standard binary Golay sequences are solved. For n odd, we prove that the PMEPR of each standard binary Golay sequence of length 2nis exactly 2, and determine the location(s), where peaks occur for each sequence. For n even, we prove that the envelope power of such sequences can never reach 2n+1at time points t ∈ {(v/2u)|0 ≤ v ≤ 2u, v,u ∈ N}. We further identify eight sequences of length 24and eight sequences of length 26that have PMEPR exactly 2, and raise the question whether, asymptotically, it is possible for standard binary Golay sequences to have PMEPR less than 2 - ϵ, where, ϵ > 0.

This paper presents two new hardware designs of the Welch-Gong (WG)-128 cipher, one for the multiple output WG (MOWG) version, and the other for the single output version WG based on type-II optimal normal basis representation. The proposed MOWG design uses signal reuse techniques to reduce hardware cost in the MOWG transformation, whereas it increases the speed by eliminating the inverters from the critical path. This is accomplished through reconstructing the key and initial vector loading algorithm and the feedback polynomial of the linear feedback shift register. The proposed WG design uses properties of the trace function to optimize the hardware cost in the WG transformation. The application-specific integrated circuit and field-programmable gate array implementations of the proposed designs show that their areas and power consumptions outperform the existing implementations of the WG cipher.

Sequences with desirable correlation properties have wide applications in today's communication systems. In this paper, we first extend the known results on zero autocorrelation zone of Golay sequences to 4q-QAM Golay sequences and show three constructions of 4q-QAM Golay sequences with a large zero periodic autocorrelation zone, where q ≥ 2 is an arbitrary integer. We then determine the Golay pairs which have large zero periodic crosscorrelation zone.

In this paper, we concentrate on the security issues of the integrity protection of LTE. EIA1 and EIA3, two integrity protection algorithms of LTE, are insecure if the initial value (IV) can be repeated twice during the life cycle of an integrity key (IK). Especially for EIA1, because of its linearity, given two valid Message Authentication Codes (MACs) our algorithm can forge up to 232 valid MACs. Thus, the probability of finding a valid MAC is dramatically increased. Although the combination of IV and IK never repeats in the ordinary case, in our well-designed scenario, the attacker can make the same combination occur twice. The duplication provides the opportunity to conduct our linear forgery attack, which may harm the security of communication. To test our linear forgery attack algorithm, we generated two counter check messages and successfully forged the third one. We also examined the attack timing by simulating real communication. From the experimental results, our attack is applicable.

Golay sequences have been studied for more than five decades since Golay first discovered those sequences. However, the periodic autocorrelation of a single Golay sequence is unknown. In this paper, for H≥ 2 being an arbitrary even integer, we show there exist three different constructions of H-ary Golay sequences with a zero autocorrelation zone (ZACZ) of length approximately an half, a quarter or one eighth of their period. Those new discoveries on Golay sequences can be explored during synchronization and detection at the receiver end and thus improve the performance of the communication system. We present the application of binary Golay sequences with ZACZ for intersymbol interference (ISI) channel estimation. Compared with m-sequences, Golay-sequence-aided channel estimation has perfect autocorrelations within the zone. Compared with Frank-Zadoff-Chu sequences, Golay-sequence-aided channel estimation requires much lower hardware and computational complexity. We also discuss the performance of Golay-sequence-aided channel estimation in terms of its error variance. Finally, simulations are conducted to show the performance of our proposed scheme against m-sequences and FZC sequences in terms of symbol error rate. The simulations also confirm with our theoretical results.

The simple, computationally efficient HB-like entity authentication protocols based on the learning parity with noise (LPN) problem have attracted a great deal of attention in the past few years due to the broad application prospect in low-cost RFID tags. However, all previous protocols are vulnerable to a man-in-the-middle attack discovered by Ouafi, Overbeck, and Vaudenay. In this paper, we propose a lightweight authentication protocol named LCMQ and prove it secure in a general man-in-the-middle model. The technical core in our proposal is a special type of circulant matrix, for which we prove the linear independence of matrix vectors, present efficient algorithms on matrix operations, and describe a secure encryption against ciphertext-only attack. By combining all of those with LPN and related to the multivariate quadratic problem, the LCMQ protocol not only is provably secure against all probabilistic polynomial-time adversaries, but also transcends HB-like protocols in terms of tag's computation overhead, storage expense, and communication cost.

In this paper, the sequence families of which maximum correlation is determined by the Weil bound of exponential sums are revisited. Using the same approach, two new constructions with large family sizes and low maximum correlation are given. The first construction is an analog of one recent result derived from the interleaved structure of Sidel'nikov sequences. For a primepand an integerM|(p-1), the newM-ary sequence families of periodpare obtained from irreducible quadratic polynomials and known power residue-based sequence families. The new sequence families increase family sizes of the known power residue-based sequence families, but keep the maximum correlation unchanged. In the second construction, the sequences derived from the Weil representation are generalized, where each new sequence is the elementwise product of a modulated Sidel'nikov sequence and a modulated trace sequence. For positive integersdpandM|(pn-1), the new family consists of (M-1)pndsequences with periodpn-1, alphabet sizeMp, and the maximum correlation bounded by (d+1)√{pn}+3.

Wireless sensor networks are vulnerable to the node clone, and several distributed protocols have been proposed to detect this attack. However, they require too strong assumptions to be practical for large-scale, randomly deployed sensor networks. In this paper, we propose two novel node clone detection protocols with different tradeoffs on network conditions and performance. The first one is based on a distributed hash table (DHT), by which a fully decentralized, key-based caching and checking system is constructed to catch cloned nodes effectively. The protocol performance on efficient storage consumption and high security level is theoretically deducted through a probability model, and the resulting equations, with necessary adjustments for real application, are supported by the simulations. Although the DHT-based protocol incurs similar communication cost as previous approaches, it may be considered a little high for some scenarios. To address this concern, our second distributed detection protocol, named randomly directed exploration, presents good communication performance for dense sensor networks, by a probabilistic directed forwarding technique along with random initial direction and border determination. The simulation results uphold the protocol design and show its efficiency on communication overhead and satisfactory detection probability.

Outsourcing data to cloud servers, while increasing service availability and reducing users' burden of managing data, inevitably brings in new concerns such as data privacy, since the server may be honest-but-curious. To mediate the conflicts between data usability and data privacy in such a scenario, research of searchable encryption is of increasing interest. Motivated by the fact that a cloud server, besides its curiosity, may be selfish in order to save its computation and/or download bandwidth, in this paper, we investigate the searchable encryption problem in the presence of a semi-honest-but-curious server, which may execute only a fraction of search operations honestly and return a fraction of search outcome honestly. To fight against this strongest adversary ever, a verifiable SSE (VSSE) scheme is proposed to offer verifiable searchability in additional to the data privacy, both of which are further confirmed by our rigorous security analysis. Besides, we treat the practicality/efficiency as a central requirement of a searchable encryption scheme. To demonstrate the lightweightness of our scheme, we implemented and tested the proposed VSSE on a laptop (serving as the server) and a mobile phone running Android 2.3.4 (serving as the end user). The experimental results optimistically suggest that the proposed scheme satisfies all of our design goals.

Sequences with good correlation properties have been widely used in modern communications, radar and sonar applications. In this paper, we consider the autocorrelation property of the single binary and quaternary Golay sequences, with special focus on their zero periodic autocorrelation zone. Some examples along with one case of the proof will be given in order to demonstrate this zero periodic autocorrelation zone. This finding on Golay sequences can be explored during synchronization and detection at the receiver end and thus improve the performance of the orthogonal frequency-division multiplexing (OFDM) system where Golay sequences are employed for the peak-to-average power reduction.

Sequences with good correlation properties have been widely adopted in modern communications, radar and sonar applications. In this paper, we present that a single H-ary Golay sequence or 4q-QAM Golay sequence has a large zone of zero odd periodic autocorrelation, where H ≡ 0 (mod 4) is a positive integer and q ≥ 2 is an arbitrary integer. The conditions on the permutations employed in the boolean functions are the same as those for the sequences with a large zone of zero (even) periodic autocorrelation. More importantly, sequences with large odd periodic autocorrelations centered around the origin could be used to reduce the multipath interference at the receiver end and thus improve the performance of the communication system.

A well-known operator of vectors over finite field is the derivative, which is used to investigate the complexity of vectors in game theory, communication theory and cryptography. According to the operator, a corresponding complexity of the vector is called (the first) depth, which also contributes to two other definitions (the second and the third depths) by using polynomial factor and high order difference, respectively. For an n-dimensional vector over Fq(a finite field with q elements and characteristic p), the three depths are the same as its linear complexity if n = pr(r ≥ 0). In this paper, by investigation on vectors s of length n (or equivalent sequences of period n) with infinite third depth, and the cyclic-left-shift-difference operator E-1 on s, long least ultimate period sequences {(E-1)i(s)}i≥0are constructed with high probability over big alphabet using lightweight calculation. Furthermore, distributions of sequences s with period n = pr-1 (r >; 0), are described in terms of the least ultimate periods of {(E-1)i(s)}i≥0. In addition, we depict circulant matrix structure of the operator (E - 1)ifor 0i(s)}i≥0and a method to determine the least ultimate period are provided. The least ultimate period presents an adversary a sufficient condition to win the rotating-table game with rapid counteraction (RGRC).

The large operation range of passive RFID systems and the ubiquitous deployment of passive tags introduce growing security and privacy threats such as tag skimming/tracking/cloning, in which eavesdropping the communication between the legitimate reader and the victim tag to obtain raw data is a basic tool for the adversary. However, given the fundamentality of eavesdropping, there are limited work investigating its intension/extension for passive RFID systems. In this work, we identify a brand-new attack at physical layer, called Unidirectional Active Eavesdropping, which defeats the customary impression that eavesdropping is a “passive” attack. In this attack, the adversary transmits an un-modulated carrier at a certain frequency, while a valid reader and a tag interacts at another frequency. When a passive tag modulates the amplitude of reader's signal, it causes fluctuations on the blank carrier as well. By carefully examining the amplitude of the backscattered version of both blank carrier and reader's carrier, the eavesdropper is able to recognize tag's responses more confidently. Besides the formalization and the theoretic analysis, we set out to fill the literature's gap by demonstrating this new attack towards a popular family of passive RFID systems, namely EPCglobal UHF Class-1 Gen-2, using software-defined radio devices and a programmable passive tag. Our empirically results further confirm that the active eavesdropping achieves a significant improvement in the reliability of the intercepted communication.

The HB-like entity authentication protocols for low-cost pervasive devices have attracted a great deal of attention because of their simplicity, computational efficiency and solid security foundation on a well-studied hard problem–learning parity with noise. By far, the most efficient protocol is HB#, which is provably resistant to the GRS attack under the conjecture that it is secure in the DET-model. However, in order to achieve 80-bit security, a typical HB# authentication key comprises over 1000 bits, which imposes considerable storage burdens on resource-constrained devices. In this study, the authors propose a new HB-like protocol: HB. The protocol makes use of a special type of circulant matrix, in contrast to the Toeplitz matrix in HB#, to significantly reduce storage consumption and overcome a subtle security proof inefficacy in HB#. In addition, the authors introduce a masking technique that substantially increases noise level from an adversary's standpoint, and thus improves protocol performance. The authors demonstrate that 613-bit authentication key suffices for 80-bit security in the HB protocol, which is quite competitive and more appealing for low-cost devices.

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.

In GLOBECOM'10, Adamo et. al. proposed an interesting encryption scheme, called Error Correction-Based Cipher (ECBC), working at the physical layer. This scheme, together with its ancestor, Secret Error Correcting Code (SECC), belongs to the family of Joint Encryption and Error Correction (JEEC), which combines error correction and data encryption as one process to enable efficient implementations. In this paper, we provide rigorous investigation on the security of ECBC and SECC to unveil their cryptographic strengths under chosen-plaintext attacks. For ECBC, we found a 3-stage differential-style attack, which breaks the scheme with O(k × 2deg(f)+ 2k) effort, where deg(f) is the degree of the core cryptographic function f. For SECC, we found a similar attack of complexity O(k × 2k+1). Both of the attacks are significantly improved from exhaustive search, e.g., O(22k+kn+n × 2k) for ECBC and O(2kn+ (k+n) × 2k) for SECC. In addition, we exhibit that f used in ECBC's implementation is particularly vulnerable to our attack, which allows the attacker to recover the secret generator matrix in O(1). To mitigate this vulnerability, we propose a secure yet lightweight construction of f achieving the maximum degree. Finally, the core part of our attack against ECBC has been implemented utilizing GPU acceleration and demonstrated on a cluster GPU instance provided by Amazon EC2. Experimental results confirm that the original implementation of ECBC scheme can be broken in (almost) constant time (<;0.4 second) regardless of k, whereas the ECBC scheme enhanced by our proposed f can withstand this attack to the maximum extent.

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.

Let$p=ef+1$be an odd prime for some$e$and$f$, and let$F_{p}$be the finite field with$p$elements. In this paper, we explicitly describe the trace representations of the binary characteristic sequences (of period$p$) of all the cyclic difference sets$D$which are some union of cosets of$e$th powers$H_{e}$in$F_{p}^{\ast }(\triangleq F_{p}\backslash \{0\})$for$e\leq 12$. For this, we define$e$th power residue sequences of period$p$, which include all the binary characteristic sequences mentioned above as special cases, and reduce the problem of determining their trace representations to that of determining the values of the generating polynomials of cosets of$H_{e}$in$F_{p}^{\ast }$at some primitive$p$th root of unity, and some properties of these values are investigated. Based on these properties, the trace representation and linear complexity not only of the characteristic sequences of all the known$e$th residue difference sets, but of all the sixth power residue sequences are determined. Furthermore, we have determined the linear complexity of a nonconstant$e$th power residue sequence for any$e$to be either$p-1$or$p$whenever$(e,(p-1)/n)=1$, where$n$is the order of 2 mod$p$.

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.

A new elementary expression of the construction first proposed by Gurevich, Hadani, and Sochen is given, which avoids the explicit use of the Weil representation. The sequences in this signal set are given by both multiplicative character and additive character of finite field$\BBF_{p}$. Such a signal set consists of$p^{2}(p-2)$time-shift distinct sequences, the magnitude of the two-dimensional autocorrelation function (i.e., the ambiguity function) in both time and phase of each sequence is upper bounded by$2\sqrt {p}$at any shift not equal to (0, 0). Furthermore, the magnitude of their Fourier transform spectrum is less than or equal to 2. For a subset consisting of$p(p-2)$phase-shift distinct sequences in this signal set, the magnitude of the ambiguity function of any pair is upper bounded by$4\sqrt {p}$. A proof is given through finding a new expression of the sequences in the finite harmonic oscillator system. An open problem for directly establishing these assertions without involving the Weil representation is addressed.

New families of near-complementary sequences are presented for peak power control in multicarrier communications. A framework for near-complementary sequences is given by an explicit Boolean expression and an equivalent matrix structure. The framework transforms seed pairs to near-complementary sequences by the aid of Golay complementary sequences. New families of near-complementary sequences of various lengths and PMEPR <; 4 are then presented, where the sequences are constructed by the framework employing the seeds of shortened and extended Golay complementary pairs. The families present in a constructive way a large number of sequences of PMEPR <; 4 for the lengths (<; 100) of 24, 28, 30, 34, 36, 48, 56, 60, 62, 66, 68, 72, and 96 where no Golay pairs have been reported. The sequence families can find potential applications for peak power control requiring codewords or sequences of various lengths as well as low peak-to-mean envelope power ratio (PMEPR).

The family of WG stream ciphers has good randomness properties. In this paper, we parameterize WG-7 stream cipher for RFID tags, where the modest computation/storage capabilities and the necessity to keep their prices low present a challenging problem that goes beyond the well-studied cryptography. The rigorous security analysis of WG-7 indicates that it is secure against time/memory/data trade off attack, differential attack, algebraic attack, correlation attack and Discrete Fourier Transform (DFT) attack. Furthermore, we offer efficient implementation of WG-7 on the 4-bit microcontroller ATAM893-D and the 8-bit microcontroller ATmega8 from ATmel. The experimental results show that WG-7 outperforms most of previous proposals in terms of throughput and implementation complexity. Moreover, we propose a mutual authentication protocol based on WG-7, which provides the untraceability, resistance of tag impersonation and reader impersonation. With its verified cryptographic properties, low implementation complexity and ideal throughput, WG-7 is a promising candidate for RFID applications.

The wireless networks lack a physical boundary due to the broadcasting nature of wireless transmissions. The security has become a critical concern in the physical layer of wireless networks. In this work, we present a cross-layer security scheme for STBC system. By introducing a distort signal set the sender randomly flip-flops between the distort signal set and the orthogonal code set to confuse the attacker. The physical-layer security is enhanced as a result. In the proposed scheme the physical-layer may rely on upper-layer encryption techniques for security, which results in a cross-layer security scheme.

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.

For prime p and a positive integer m, it is shown that M-ary Sidelnikov sequences of period p2m- 1, if M | pm- 1, can be equivalently generated by the operation of elements in a finite field GF(pm), including a pm-ary m-sequence. The equivalent representation over GF(pm) requires low complexity for implementing the Sidelnikov sequences. Moreover, a (pm- 1)×(pm+1) array structure is introduced for the Sidelnikov sequences. From the array structure, it is found that about a half of the column sequences of length pm- 1 and their constant multiples have the low correlation magnitude bounded by 3√(pm+ 1).

In this paper, generalized constructions of polyphase sequence families from the shift and addition of power residue and Sidelnikov sequences are presented. Initially, ψ(0) = 1 is assumed for multiplicative characters ψ to represent power residue and Sidelnikov sequences in a simple form. The Weil bound on multiplicative character sums is refined for the assumption, where the character sums are equivalent to the correlations of sequences represented by multiplicative characters. Generalized constructions are then presented by the addition of multiple cyclic shifts of power residue and Sidelnikov sequences. The refined Weil bound is employed to provide efficient proofs on the maximum correlation magnitudes of the generalized sequence families.

Public-key provision in on Internet scale is crucial for securing peer-to-peer (P2P) applications. This paper proposes a framework for a self-organizing and self-healing certificate authority (CA) in a Content Addressable Network (CAN) that can provide certificates without a centralized Trusted Third Party (TTP). In our framework, a CA group is initialized by bootstrapping nodes and then grows to a mature state by itself. Based on our group management policies, the membership in the CA group is dynamic and has a uniform distribution over the P2P community. Meanwhile, the honest majority of the CA group is maintained by a Byzantine agreement algorithm, and all shares of the CA group are refreshed gradually and continuously. A security analysis shows that the framework enables key registration and certificate issue with resistance to man-in-the-middle (MITM), collusion, and node impersonation attacks.

The paper introduces a novel message authentication framework over broadcast channels, where a symmetric cryptography-based physical layer assisted message authentication (PLAA) scheme is introduced in wireless networks. The proposed framework integrate the conventional message authentication schemes and the physical layer authentication mechanisms by taking advantage of temporal and spatial uniqueness in physical layer channel responses, aiming to achieving fast authentication while minimising the packet transmission overhead. Our claims through extensive analysis and simulation will be verified via comparing with public key infrastructure-based PLAA scheme and traditional upper layer authentication schemes.

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.

In this paper, we give three new constructions of binary sequences of period AN with optimal autocorrelation value or optimal autocorrelation magnitude using N × 4 interleaved sequences. Yu and Gong recently found any binary sequence of period AN with optimal autocorrelation value constructed from an almost difference set by Arasu et al. is an N × 4 interleaved sequence for which all four columns in its N × 4 array are shift equivalent up to the complement. We found that it is not necessary that four columns are shift equivalent. Instead, it could be a pair of related sequences together with their shifts as the column sequences. The first construction is to use a generalized GMW sequence of period N = 2k- 1 and its modified version, the second construction is to use a twin prime sequence of length N = p(p + 2) and its modified version, and the third construction, a pair of Legendre sequences of period N = p (p odd prime) with their respective first terms complementary (the 2-level autocorrelation property is not needed for the Legendre sequence). The comparison with the known constructions are given. For the new sequences with optimal autocorrelation value, their corresponding new almost difference sets are also derived.

For primepand a positive integerm, it is shown thatM-ary Sidelnikov sequences of periodp2m-1, ifM|pm-1, can be equivalently generated by the operation of elements in a finite fieldGF(pm), including apm-arym-sequence. From the(pm-1) ×(pm+1) array structure of the sequences, it is then found that a half of the column sequences and their constant multiples have low correlation enough to construct newM-ary sequence families of periodpm-1. In particular, newM-ary sequence families of periodpm-1 are constructed from the combination of the column sequence families and known Sidelnikov-based sequence families, where the new families have larger family sizes than the known ones with the same maximum correlation magnitudes. Finally, it is shown that the newM-ary sequence family of periodpm-1 and the maximum correlation magnitude2√{pm}+6 asymptotically achieves√2times the equality of the Sidelnikov's lower bound whenM=pm-1 for odd primep.

Power residue and Sidelnikov sequences are polyphase sequences with low correlation and variable alphabet sizes, represented by multiplicative characters. In this paper, sequence families constructed from the shift and addition of the polyphase sequences are revisited. Initially, ψ(0)=1 is assumed for multiplicative characters ψ to represent power residue and Sidelnikov sequences in a simple form. The Weil bound on multiplicative character sums is refined for the assumption, where the character sums are equivalent to the correlations of sequences represented by multiplicative characters. General constructions of polyphase sequence families that produce some of known families as the special cases are then presented. The refined Weil bound enables the efficient proofs on the maximum correlation magnitudes of the sequence families. From the constructions, it is shown that M-ary known sequence families with large size can be partitioned into (M+1) disjoint subsequence families with smaller maximum correlation magnitudes. More generalized constructions are also considered by the addition of multiple cyclic shifts of power residue and Sidelnikov sequences.

In this paper, we introduce a novel framework for physical layer assisted message authentication (PAA) under public key infrastructure (PKI) in vehicular communication networks. The proposed framework takes advantage of temporal and spatial uniqueness in physical layer channel responses for each transmission pair, in which a trust between two vehicles can be maintained by comparing the current estimated channel response and the previous estimated channel response. We will show that the proposed message authentication framework can achieve extremely high efficiency and minimal authentication delay without compromising the security requirements, which is further verified through both analysis and simulation.

New families of near-complementary sequences are presented for peak power control in multicarrier communications. A framework for near-complementary sequences is given by the explicit Boolean expression and the equivalent array structure. The framework transforms the seed pairs to the near-complementary sequences by the aid of Golay complementary sequences. As the examples, new families of near-complementary sequences with the peak-to-mean envelope power ratio (PMEPR) < 4 are presented, where the sequences provide various lengths by employing the seeds of shortened or extended Golay complementary pairs. The sequence families can find the potential applications for peak power control requiring codewords or sequences of various lengths as well as low PMEPR.

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.

Node clone attack, that is, the attempt by an adversary to add one or more nodes to the network by cloning captured nodes, imposes a severe threat to wireless sensor networks. Several distributed detection protocols have been proposed against this attack. However, all of them rely on too strong assumptions and cannot be efficiently applied to most of sensor networks. In this paper, we propose an innovative randomly directed exploration protocol to detect the node clone. Each node need only know its neighbors' information, and then collaborates to forward claiming messages, trying to find out clone. No any specific routing protocols or infrastructures are demanded in the proposed protocol. Therefore, it is highly practical in the general sensor network applications. In addition, the memory requirement of the protocol is almost optimal. Furthermore, the protocol consumes relatively low communication overload, which is not inferior to any previous schemes. The simulation results show that the protocol can achieve high detection probability. Overall, the proposed protocol outweighs previous approaches in terms of practicability and performance.

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.

The algebraic immunity of an S-box depends on the number and type of linearly independent multivariate equations it satisfies. In this paper, techniques are developed to find the number of linearly independent, multivariate, bi-affine, and quadratic equations for S-boxes based on power mappings. These techniques can be used to prove the exact number of equations for any class of power mappings. Two algorithms to calculate the number of bi-affine and quadratic equations for any$(n,n)$S-box based on power mapping are also presented. The time complexity of both algorithms is only$O(n^2)$. To design algebraically immune S-boxes, four new classes of S-boxes that guarantee zero bi-affine equations and one class of S-boxes that guarantees zero quadratic equations are presented. The algebraic immunity of power mappings based on Kasami, Niho, Dobbertin, Gold, Welch, and inverse exponents are discussed along with other cryptographic properties and several cryptographically strong S-boxes are identified. It is conjectured that a known Kasami-like highly nonlinear power mapping is differentially$4$-uniform. Finally, an open problem to find an$(n,n)$bijective nonlinear S-box with more than$5n$quadratic equations is solved.

This paper is devoted to the classification of hyperbent functions, i.e., bent functions which are bent up to a primitive root change. We first exhibit an infinite class of monomial functions which are not hyperbent. It implies notably that Kloosterman sums at point 1 on F2mcannot be zero, unless m = 4. Further, we show that hyperbent functions with multiple trace terms can be described by means of Dickson polynomials.

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.

The absence of an online trusted authority makes the issue of key revocation in mobile ad hoc networks (MANETs) particularly challenging. In this paper, we present a novel self-organized key revocation scheme based on the Dirichlet multinomial model and identity-based cryptography (IBC). Our key revocation scheme offers a theoretically sound basis for a node in MANETs to predict the behavior of other nodes based on its own observations and reports from peers. In our scheme, each node keeps track of three categories of behavior defined and classified by an external trusted authority, and updates its knowledge about other nodespsila behavior with 3-dimension Dirichlet distribution. Differentiating between suspicious behavior and malicious behavior enables nodes to make multilevel response by either revoking keys of malicious nodes or ceasing the communication with suspicious nodes for some time to gather more information for making further decision. Furthermore, we also analyze the attack-resistant properties of our key revocation scheme through extensive simulations in the presence of adversaries.

This paper is devoted to the study of hyperbent functions in n variables, i.e., bent functions which are bent up to a change of primitive roots in the finite field GF(2n). Our main purpose is to obtain an explicit trace representation for some classes of hyperbent functions. We first exhibit an infinite class of monomial functions which is not hyperbent. This result indicates that Kloosterman sums on F2mcannot be zero at some points. For functions with multiple trace terms, we express their spectra by means of Dickson polynomials. We then introduce a new tool to describe these hyperbent functions. The effectiveness of this new method can be seen from the characterization of a new class of binomial hyperbent functions.

New binary sequences of period N = 4(2m- 1) for even m ges 4 are found, where the sequences are described by a 4 X (2m- 1) array structure. The new sequences are almost balanced and have four- valued autocorrelation, i.e., {N, 0, plusmn4}, which is optimal with respect to autocorrelation magnitude. The complete autocorrelation distribution and the exact linear complexity of the sequences are mathematically derived. Finally, it is shown that the sequences are implemented by a combination of linear feedback shift registers and a simple logic.

By interleaving one length-N perfect sequence or ideal sequence according to elaborate phases, a new method of construction of zero correlation zone (ZCZ) and low correlation zone (LCZ) sequence sets is presented. The resultant sequence sets are optimal or almost optimal with respect to Tang, Fan, and Matsufuji bound. Furthermore, the new method provides flexible choice for the ZCZ and LCZ lengths.

In this paper, we introduce a concept of correlation of multiple shift-distinct signal sets, and make a connection between constructions of multiple binary signal sets with low maximum correlation and constructions of a binary signal set with larger size and low maximum correlation. We then present one construction for multiple shift-distinct binary signal sets with low maximum correlation using Kasami (small) signal sets (or generalized Kasami signals sets). We show that the constructed m Kasami signal sets, in which each sequence has periodN= 22m- 1, satisfies the tth-order shift-distinct property, which is a new concept introduced in this paper. As a by-product, this construction also yields some new pairs ofm-sequences with different periods and three-valued crosscorrelation.

This paper investigates how irreducibility and primitivity can be preserved when the unitary group acts on irreducible or primitive polynomials. Applying these operators to sequences and their discrete Fourier spectra, the weight preserving property is obtained. Some new randomness criteria are introduced in terms of these operators, which are suitable for measuring unpredictibility of pseudo-random sequences employed in stream ciphers.

Observing a phenomenon that the pre-image set of nonzero Hadamard spectra of the composition of a function and a trace function is independent of the function, a construction of multiple bent function signal sets using different bent functions is given. Their correlation and high-order shift-distinct property are discussed. As a by-product, the union of the multiple bent function signal sets produces a signal set with low correlation zone and much larger size of the other known constructions.

The ideal class groups of hyperelliptic curves (HECs) can be used in cryptosystems based on the discrete logarithm problem. Recent developments of computational technologies for scalar multiplications of divisor classes have shown that the performance of hyperelliptic curve cryptosystems (HECC) is compatible to that of elliptic curve cryptosystems. Especially, due to short operand sizes, genus 3 HECC are well suited for all kinds of embedded processor architectures, where resources such as storage, time or power are constrained. In the paper, the acceleration of the divisor class doubling for genus 3 HECs over binary fields is investigated and the number of field operations needed is analysed. By constructing birational transformations of variables, four types of curves which can lead to much faster divisor class doubling are found and the corresponding explicit formulae are given. In particular, for special genus 3 HECs over binary fields with h(X)=1, the fastest explicit doubling formula published so far which only requires one field inversion, ten field multiplications and eleven field squarings, is obtained. Furthermore, comparisons with the known results in terms of field operations and implementations of genus 3 HECC over three different binary fields on a Pentium-4 processor are provided.

The definition, the basic properties, and all the currently known systematic constructions for Costas arrays are presented, as well as a table of the number C(n) of Costas arrays of order n, for 2 les n les 26. It is proved that lim supnrarrinfinC(n) = infin, and the conjecture liminfnrarrinfinC(n) = 0 is discussed. A Costas array of order n is known to be equivalent to a permutation {1,2,...,n} for which the difference triangle contains no repeated elements in any row. A generalized Costas array of order n = q-1(or n=q -2) is defined as a permutation of the nonzero elements (or also excluding 1) of the q-element field for which the difference triangle contains no repeated elements in any row. Two new constructions for these generalized Costas arrays are described and illustrated.

In this correspondence, we present a connection between designing low-correlation zone (LCZ) sequences and the results of correlation of sequences with subfield decompositions presented in a recent book by the first two authors. This results in LCZ signal sets with huge sizes over three different alphabetic sets: finite field of size$q$, integer residue ring modulo$q$, and the subset in the complex field which consists of powers of a primitive$q$th root of unity. We show a connection between these sequence designs and “completely noncyclic” Hadamard matrices and a construction for those sequences. We also provide some open problems along this direction.

In this paper, we demonstrate the secure integration of a Diffie-Hellman (DH) key exchange into a digital signature scheme (DSS) using either LUC, XTR or GH as crypto schemes. The presented integrated DH-DSS protocols enable efficient and secure authenticated key exchange between two parties. The integration, as first proposed by Arazi, saves one costly computation step and significantly reduces the bandwidth. We prove that the integrated DH-DSS protocols introduced in this paper all resist the known-key attack that Nyberg and Rueppel presented on Arazi's scheme. The presented integrated protocols outperform all existing variants of Arazi's protocol and the combined DH-DSS protocol while providing the same or more security properties

Let p be an odd prime, q be a divisor of p - 1 and mu be a primitive root mod p. A g-ary PRS (power residue sequence) of period p is defined as s(n) = k if n isin Ckwhere Ck= {muqt+k|t = 0,1,2,...,T - 1} where T = (p - 1)/q. In this paper, we prove that the maximum absolute value of the periodic crosscorrelation of two distinct q-ary PRS's of period p is upper bounded by √ p + 2

For odd n=2l+1 and an integer /spl rho/ with 1/spl les//spl rho//spl les/l, a new family S/sub o/(/spl rho/) of binary sequences of period 2/sup n/-1 is constructed. For a given /spl rho/, S/sub o/(/spl rho/) has maximum correlation 1+2/sup n+2/spl rho/-1/2/, family size 2/sup n/spl rho//, and maximum linear span n(n+1)/2. Similarly, a new family of S/sub e/(/spl rho/) of binary sequences of period 2/sup n/-1 is also presented for even n=2l and an integer /spl rho/ with 1/spl les//spl rho/

In this correspondence, the constructions and enumerations of all bent functions represented by a polynomial form of f(x)=/spl Sigma//sub i=1//sup n/2-1/c/sub i/Tr(x/sup 1+2(i)/)+c/sub n/2/Tr/sub 1//sup n/ /sup /2/(x/sup 1+2(n/2)/), c/sub i//spl isin//sub 2/ F/sub 2/ are presented for special cases of n. Using an iterative approach, the construction of bent functions of n variables with degree n/2 is also provided using the constructed quadratic bent functions.

Multiple access interference (MAI) in CDMA system is related to the correlation of the transmitted signals from multiple users. In this work, we investigate the correlations of binary signal sets over fading channels, particularly the Gold and Kasami signal sets. A lower bound on the maximum correlation with fading is established. Moreover, an asymptotic bound depending on the length of the sequence and the first and second order statistics of the fading distribution is derived for independent fading channel, while an approximation to the maximum correlation is obtained for correlative fading channel. To analyze the fading effect on cross correlation, experimental results show that the distribution of cross correlation in slow fading environment is similar to the one without fading.

In this paper the impact of the more recent stream cipher attacks like time-memory-data trade-off attacks and algebraic attacks on filter function keystream generators are studied. The attacks succeed when the filter function is based on concatenation of linear functions. As an alternative, some known constructions based on finite fields which are not susceptible to these attacks are presented. Two new finite field constructions were also introduced, one based on the GMW construction and the other based on an efficient exhaustive search

Recently, identity-based cryptography (IBC) schemes are considered as a tool to secure ad hoc networks. In this work we focus on the role of the Trust Authority (TA) as a key escrow, a property that is inherent to all IBC schemes. We explore the special role of key escrow in ad hoc networks and show that this role significantly differs from key escrows in other networks. We introduce a series of adversary models for dishonest TAs in ad hoc networks, including a new model where a TA uses spy nodes that record communications in the network and report them to the TA. Our analytical results show that in many ad hoc network applications the TA can be prevented from being a key escrow.

This paper describes the asymptotic behavior of normalized linear complexity of ultimately nonperiodic binary sequence. The linear complexity of s/sup n/, L/sub s/(n), is defined as the length of the shortest linear feedback shift register which generates s/sup n/. The research method and results studied in this paper seem to be very useful in characterizing the purely random sequence and distinguishing a key stream generator from a uniformly random sequence.

This paper presents a efficient key agreement and signature schemes using compact representations in GF(p/sup 10/). We propose an analogous system using GF(p/sup 10/) which gives a 60% reduction in bandwidth from the canonical representation. We also present a signature scheme based on a new problem called the trace discrete log problem (Trace-DLP problem).

For an ultimately nonperiodic binary sequence s={s/sub t/}/sub t/spl ges/0/, it is shown that the set of the accumulation values of the normalized linear complexity, L/sub s/(n)/n, is a closed interval centered at 1/2, where L/sub s/(n) is the linear complexity of the length n prefix s/sup n/=(s/sub 0/,s/sub 1/,...,s/sub n-1/) of the sequence s. It was known that the limit value of the normalized linear complexity is equal to 0 or 1/2 if it exists. A method is also given for constructing a sequence to have the closed interval [1/2-/spl Delta/, 1/2+/spl Delta/](0/spl les//spl Delta//spl les/1/2) as the set of the accumulation values of its normalized linear complexity.

New designs for families of sequences over GF(p) with low cross correlation, balance property, and large linear span are presented. The key idea of the new designs is to use short p-ary sequences of period /spl upsi/ with the two-level autocorrelation function together with the interleaved structure to construct a set of long sequences with the desired properties. The resulting sequences are interleaved sequences of period /spl upsi//sup 2/. There are /spl upsi/ cyclically shift distinct sequences in each family. The maximal correlation value is 2/spl upsi/ + 3 which is optimal with respect to the Welch bound. Each sequence in the family is balanced and has large linear span. In particular, for binary case, cross/out-of-phase autocorrelation values belong to the set {1, -/spl upsi/, /spl upsi/ + 2, 2/spl upsi/ + 3, -2/spl upsi/ - 1}, any sequence where the short sequences are quadratic residue sequences achieves the maximal linear span. It is shown that some families of these sequences can be implemented efficiently in both hardware and software.

A new method to study and search for two-level autocorrelation sequences for both binary and nonbinary cases is developed. This method iteratively applies two operations: decimation and the Hadamard transform based on general orthogonal functions, referred to as the decimation-Hadamard transform (DHT). The second iterative DHT can transform one class of such sequences into another inequivalent class of such sequences, a process called realization. The existence and counting problems of the second iterative DHT are discussed. Using the second iterative DHT, and starting with a single binary m-sequence (when n is odd), we believe one can obtain all the known two-level autocorrelation sequences of period 2/sup n/-1 which have no subfield factorization. We have verified this for odd n/spl les/17. Interestingly, no previously unknown examples were found by this process for any odd n/spl les/17. This is supporting evidence (albeit weak) for the conjecture that all families of cyclic Hadamard difference sets of period 2/sup n/-1 having no subfield factorization are now known, at least for odd n. Experimental results are provided.

Welch-Gong (WG) transformation sequences are binary sequences of period 2/sup n/ - 1 with two-level autocorrelation. These sequences were discovered by Golomb, Gong, and Gaal (1998) and they verified the validity of their construction for 5 /spl les/ n /spl les/ 20. Later, No, Chung, and Yun (1998) found another way to construct the WG sequences and verified their result for 5 /spl les/ n /spl les/ 20. Dillon (1998) first proved this result for odd n, and, finally, Dobbertin and Dillon (1999) proved it for even n. In this paper, we investigate a two-faced property of the WG transformation sequences for application in stream ciphers and pseudorandom number generators. One is to present the randomness or unpredictability of the WG transformation sequences. The other is to exhibit the security properties of the WG transformations regarded as Boolean functions. In particular, we prove that the WG transformation sequences, in addition to the known two-level autocorrelation and three-level cross correlation with m-sequences, have the ideal 2-tuple distribution, and large linear span increasing exponentially with n. Moreover, it can be implemented efficiently. This is the first type of pseudorandom sequences with good correlation, statistic properties, large linear span, and efficient implementation. When WG transformations are regarded as Boolean functions, they have high nonlinearity. We derive a criterion for the Boolean representation of WG transformations to be r-resilient and show that they are at least 1-resilient under some basis of the finite field GF (2/sup n/). An algorithm to find such bases is given. The degree and linear span of WG transformations are presented as well.

We find new families of nonbinary sequences of period p/sup n/-1 with symbols from a finite field F/sub p/ for any prime p/spl ges/3. The sequences have two-level ideal autocorrelation and are generalizations of previously found ternary sequences with ideal autocorrelation. Difference sets with parameters ((p/sup n/-1)/(p-1), (p/sup n-1/-1)/(p-1), (p/sup n-2/-1)/(p-1)) can also be derived from these sequences in a natural way.

Periodic binary sequences with the "trinomial property" are considered. A conjecture of Golomb and Gong (see ibid., vol..45, p.1276-9, May 1999) concerning these sequences is disproved.

In a previous paper, No, Golomb, Gong, Lee and Gaal (see ibid., vol.44, p.814-17, 1998) conjectured that certain binary sequences having a simple trace description possess the ideal autocorrelation property. In the present paper it is shown that each such sequence is balanced and, moreover, that the dual of the linear cyclic code generated by the sequence and its cyclic shifts, is a triple-error correcting code having the same weight distribution as the triple-error correcting Bose-Chaudhuri-Hocquenghem (BCH) code. This cyclic code also contains a cyclic subcode that yields a new family of sequences having the same size and correlation parameters as does the family of Gold sequences.

Gordon-Mills-Welch (GMW) sequences (also called cascaded GMW sequences) have two-level autocorrelations. This property makes them widely used in various communication and cryptographic systems. The generation of q-ary GMW sequences of period q/sup n-1/ involves three types of parameters. To determine whether GMW sequences are cyclically shift-distinct for differing parameters has remained an open question until now. In this paper, we completely solve this problem for varying all three types of parameters. We find a criterion for cyclically shift-distinct q-ary GMW sequences of period q/sup n-1/, and obtain the number of such sequences. For the special case of q=2, this solution facilitates counting the number of cyclic Hadamard difference sets which correspond to binary GMW sequences of period 2/sup n-1/.

Periodic binary sequences with the "trinomial property" are considered. Some necessary and sufficient conditions for "trinomial pairs" of a nonlinear sequence of period 2/sup n/-1 as well as classifications for trinomial pairs are derived. Complete searches for trinomial pairs of sequences have been completed for 3/spl les/n/spl les/17. We list them here for n/spl les/12.

We derive the values of the Fourier spectrum, a decomposition, and an achievable upper bound on the linear span, for binary sequences with two-level autocorrelation.

Certain three-term sequences of period 2/sup n/-l are conjectured to have the two-level autocorrelation property. In this note, a formula involving Hadamard transforms of three-term sequences is presented. Its validity has been verified by computer on the range of 5/spl les/n/spl les/23.

The Data Encryption Standard (DES) can be regarded as a nonlinear feedback shift register (NLFSR) with input. From this point of view, the tools for pseudo-random sequence analysis are applied to the S-boxes in DES. The properties of the S-boxes of DES under the Fourier transform, Hadamard transform, extended Hadamard transform, and the Avalanche transform are investigated. Two important results about the S-boxes of DES are found. The first result is that nearly two-thirds of the total 32 functions from GF (2/sup 6/) to GF(2) which are associated with the eight S-boxes of DES have the maximal linear span G3, and the other one-third have linear span greater than or equal to 57. The second result is that for all S-boxes, the distances of the S-boxes approximated by monomial functions has the same distribution as for the S-boxes approximated by linear functions. Some new criteria for the design of permutation functions for use in block cipher algorithms are discussed.

The cryptographic properties of third-order linear feedback shift-register (LFSR) sequences over GF(p) are investigated. A fast computational algorithm for evaluating the kth term of a characteristic sequence of order 3 is presented. Based on these properties, a new public-key distribution scheme and an RSA-type encryption algorithm are proposed. Their security, implementation, information rate, and computational cost for the new schemes are discussed.

In this correspondence, we present five new classes of binary sequences of period 2/sup n/-1 with ideal autocorrelation. These sequences, which correspond to new cyclic Hadamard difference sets, were found by extensive computer search. Conjectures on the general construction of these sequences are formulated.

A new class of pseudo-random sequences (called cascaded GMW-type permutation polynomial (CGPP) sequences) over GP(q/sup n/) is constructed using a system of n orthogonal cascaded GMW functions in GF(q). Their statistical properties are given. Classification, evaluation, and implementation of the CGPP sequences are derived. A sequence generated by mapping elements of a CGPP sequence into GF(q) is also presented.

Cascaded GMW sequences over GF(q) of arbitrary characteristic are investigated. Their periods are derived. As compared with the existing results on such sequences, substantially extended and improved theorems concerning their linear spans and autocorrelation functions are obtained. A criterion and an algorithm for constructing cascaded GMW sequences that have much larger linear spans than GMW sequences with the same periods are given. These provide a new class of complex-valued sequences which have larger linear spans and two-valued autocorrelation functions.

A new class of q-ary sequences, called interleaved sequence, is introduced. Their periods, shift equivalence, linear spans, and autocorrelation functions are derived. The interleaved sequences include a large number of popular sequences, such as multiplexed sequences, clock-controlled sequences, Kasami (1966) sequences, GMW sequences, geometric sequences, and No (1989) sequences. A special class of the interleaved sequences is constructed by mapping GF(q/sup m/) sequences into GF(q) sequences in terms of different bases of GF(q/sup m/) over GF(q). As an application of the theory of interleaved sequences, some new families of binary pseudo-random sequences are constructed, which have large linear spans, optimal periodic cross/autocorrelation functions, balance, and the rapidly "hopped" properties. A complete comparison of the new family of sequences with the Gold sequence family, the Kasami (small and large set) sequence families, the Bent-function sequence family, and the No sequence family is discussed. This shows that the new sequence families have important advantages for use in spread-spectrum multiple-access communication systems.>

The construction of m-sequences over GF(q/sup n/) from known m-sequences over GF(q) is discussed. An algorithm is given which generates m-sequences over GF(q/sup n/) from m-sequences over GF(q), where n phase shifts of known m-sequences over GF(q) are determined by the iterative polynomials. It is shown that n shift distinct m-sequences over GF(q/sup n/) generated by the same m-sequences over GF(q) are unique when the elements of GF(q/sup n/) are represented by n-tuples of the elements from GF(q).>