Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 7th International Conference on Sequences and Their Applications, SETA 2012, held in Waterloo, Canada, in June 2012. The 28 full papers presented together with 2 invited papers in this volume were carefully reviewed and selected from 48 submissions. The papers are grouped in topical sections on perfect sequences; finite fields; boolean functions; Golomb 80th birthday session; linear complexity; frequency hopping; correlation of sequences; bounds on sequences, cryptography; aperiodic correlation; and Walsh transform.

Inhaltsverzeichnis

Frontmatter

Perfect Sequences

Odd Perfect Sequences and Sets of Spreading Sequences with Zero or Low Odd Periodic Correlation Zone

Abstract
In this paper, we apply shift sequences defined by difference balanced function with d-form property to construct (almost) perfect or odd perfect sequences, which is a generalization of the construction given by Krengel in 2004. We then propose new signal sets with flexible parameters and zero odd periodic correlation zone or low odd periodic correlation zone property, by interleaving an odd perfect sequence or a sequence with low odd periodic correlation. Furthermore, we show that the parameters of some constructed signal sets are optimal with respect to the odd periodic correlation bound.
Yang Yang, Guang Gong, Xiaohu Tang

Nonexistence of Certain Almost p-ary Perfect Sequences

Abstract
We prove nonexistence of almost p-ary perfect sequences of period n + 1, where n ∈ {50, 76, 94, 99, 100} and p is an odd prime dividing n − 1. This answers a question of Chee, Tan and Zhou.
Ferruh Özbudak, Oğuz Yayla, C. Cengiz Yıldırım

Finite Fields

New Families of Differentially 4-Uniform Permutations over ${\mathbb F}_{2^{2k}}$

Abstract
Differentially 4-uniform permutations over \({\mathbb F}_{2^{2k}}\), especially those with high nonlinearity and high algebraic degree, are cryptographically significant mappings as they are good choices for the substitution boxes (S-boxes) in many symmetric ciphers. For instance, the currently endorsed Advanced Encryption Standard (AES) uses the inverse function, which is a differentially 4-uniform permutation. However, up to now, there are only five known infinite families of such mappings which attain the known maximal nonlinearity. Most of these five families have small algebraic degrees and only one family can be defined over \({\mathbb F}_{2^{2k}}\) for any positive integer k. In this paper, we apply the powerful switching method on the five known families to construct differentially 4-uniform permutations. New infinite families of such permutations are discovered from the inverse function, and some sporadic examples are found from the others by using a computer. All newly found infinite families can be defined over fields \({\mathbb F}_{2^{2k}}\) for any k and their algebraic degrees are 2k − 1. Furthermore, we obtain a lower bound for the nonlinearity of one infinite family.
Yin Tan, Longjiang Qu, Chik How Tan, Chao Li

Dickson Polynomials, Hyperelliptic Curves and Hyper-bent Functions

Abstract
In this paper, we study the action of Dickson polynomials on subsets of finite fields of even characteristic related to the trace of the inverse of an element and provide an alternate proof of a not so well-known result. Such properties are then applied to the study of a family of Boolean functions and a characterization of their hyper-bentness in terms of exponential sums recently proposed by Wang et al.Finally, we extend previous works of Lisoněk and Flori and Mesnager to reformulate this characterization in terms of the number of points on hyperelliptic curves and present some numerical results leading to an interesting problem.
Jean-Pierre Flori, Sihem Mesnager

Invited Paper

Variable Weight Sequences for Adaptive Scheduled Access in MANETs

Abstract
Scheduling access to a shared channel in mobile ad hoc networks must address numerous competing requirements, for example on throughput, delay, and fairness. It must address disparate and dynamic traffic demands as well as losses due to collisions with neighbouring transmitters. It must address changes in the topology of the network that arise from mobility. Topology transparent scheduling schemes have been proposed as a means to support reasonable delay guarantees, minimum throughput guarantees, and to a lesser extent fairness concerns. Sequences based on codes and combinatorial designs have been explored that support topology transparent scheduling for mobile ad hoc networks. However, all of the schemes proposed provide every node with the same (or essentially the same) channel access, by assigning each node a transmission frame in which the number of transmission slots (‘weight’) is the same. In order to mitigate effects of losses due to collision, it is important to limit the set of frame schedules that are permitted; but at the same time, using frames with differing weights can improve throughput without sacrificing fairness. Combinatorial requirements for variable weight frame schedules are determined based on these observations.
Jonathan Lutz, Charles J. Colbourn, Violet R. Syrotiuk

Boolean Functions

Arithmetic Walsh Transform of Quadratic Boolean Functions

(Extended Abstract)
Abstract
Recently an arithmetic or “with carry” analog of the Walsh-Hadamard transform of Boolean functions was defined. In this paper we compute the arithmetic Walsh transforms of quadratic functions. We find that, as with traditional Walsh-Hadamard transform, the arithmetic Walsh spectrum of quadratic functions is very flat.
Andrew Klapper

Characterizing Negabent Boolean Functions over Finite Fields

Abstract
We consider negabent Boolean functions that have Trace representation. To the best of our knowledge, this is the first ever work on negabent functions with such representation. We completely characterize negabent quadratic monomial functions. We also present necessary and sufficient condition for a Maiorana-McFarland bent function to be a negabent function. As a consequence of that result we present a nice characterization of a bent-negabent Maiorana-McFarland function which is based on the permutation \(x \mapsto x^{2^i}\).
Sumanta Sarkar

Computing the Weight of a Boolean Function from Its Algebraic Normal Form

Abstract
We present an algorithm that computes the weight of a Boolean function from its Algebraic Normal Form (ANF). For functions acting on high number of variables (n > 30) and having low number of monomials in its ANF, the algorithm is advantageous over the standard method of computing weight which requires the transformation of function’s ANF to its truth table with a complexity of \(\mathcal{O}(n2^n)\) operations. A relevant attempt at computing the Walsh coefficients of a function from its ANF by Gupta and Sarkar required the function to be composed of high degree monomials [1]. The proposed algorithm overcomes this limitation for particular values of n, enabling the weight and Walsh coefficient computation for functions that could be of more interest for practical applications.
Çağdaş Çalık, Ali Doğanaksoy

Boolean Functions Derived from Pseudorandom Binary Sequences

Abstract
We study measures used to assess Boolean functions, where the functions are understood to be derived from binary sequences. We prove relations between two complexity measures for these Boolean functions and the correlation measure of order k of the corresponding sequence. More precisely, we study sparsity and combinatorial complexity of the Boolean function. Moreover, for a sequence with ’typical’ values of the correlation measure of order k we apply these relations to derive bounds on the complexity measures for the corresponding Boolean function. Finally, we apply our results to Sidelnikov sequences for which nice upper bounds on the correlation measure are known.
Gottlieb Pirsic, Arne Winterhof

Golomb 80th Birthday Session (I)

Infinite Sequences with Finite Cross-Correlation-II

Abstract
This extends a study in [1], from SETA-2010. We consider two infinite sequences of positive integers, \(A= \{a_k\} ^\infty_{k=1}\) and \(B = \{b_k\}_{k=1}^\infty\), and the related sequences \(\bar{A} = \{\alpha_j\}_{j=1}^\infty\) and \(\bar{B} = \{\beta_j\}_{j=1}^\infty\), where α j  = 1 if j ∈ A, α j  = 0 if j ∉ A, and β j  = 1 if j ∈ B, β j  = 0 if j ∉ B. We call C AB (τ) the cross-correlation of A and B where C AB (τ) is the un-normalized infinite-domain cross-correlation of \(\bar{A}\) and \(\bar{B}\), i.e.
$$ C_{AB}(\tau) = \sum \limits_{i=1}^\infty \alpha_i\beta_{i+\tau},\: for all\: \tau \in Z. $$
(1)
Our interest is confined to sequence pairs A,B for which C AB (τ) is finite for all τ ∈ Z. Our interest is greater if C AB (τ) < K for some uniform bound K, for all τ ∈ Z, and especially great if K = 1. We are specifically interested in possible lower bounds on the rates of growth of A and B for a given value of K. This paper provides extensive data for the case K = 1.
Solomon W. Golomb

Irreducible Coefficient Relations

Abstract
The distribution of coefficients of irreducible polynomials over GF(2) has long been a subject of interest for coding theorists and researchers in related fields. In this paper, we prove that the only affine relations holding on these coefficients are essentially trivial. We also give an extension of this result to arbitrary finite fields GF(q), where “affine” is replaced by “degree at most q-1”.
Thomas J. Dorsey, Alfred W. Hales

Wavelength Isolation Sequence Pairs

Abstract
In the early 1950s, Golay studied binary sequence pairs whose autocorrelation properties are ideal for use in the design of multislit spectrometers. He found examples for some small lengths, but, unable to find more, he suggested that perhaps further examples do not exist and turned his attention to an alternative solution to the design problem (involving what are now called Golay complementary sequence pairs). The original sequence pairs that Golay sought appear to have been overlooked in the sixty years since. We present examples of these pairs, which we call wavelength isolation sequence pairs, for two new lengths. We provide structural constraints on these sequence pairs and describe a method whereby each of the currently known examples can be constructed from a perfect Golomb ruler.
Jonathan Jedwab, Jane Wodlinger

Index Tables of Finite Fields and Modular Golomb Rulers

Abstract
For a Galois field GF(2 n ) defined by a primitive element α with minimal polynomial f, the index table contains in row i the coordinates of α i in the polynomial basis α n − 1, α n − 2,…, α, 1. Each column i in this table equals the m-sequence with characteristic polynomial f, shifted cyclically by some offset h i .
In this paper we show that the set of the n shifts h i contains large subsets which are modular Golomb rulers modulo 2 n  − 1 (i.e. all the differences are different). Let D be the set of integers j such that the coefficient of x j in f is non-zero. We prove that the set H D of shifts corresponding to columns j ∈ D can be partitioned into two subsets (the columns in the left half of the table and the ones in the right half) each of which is a modular Golomb ruler. Based on this result and on computational data, we conjecture that in fact the whole set H D is a modular Golomb ruler.
We give a polynomial time algorithm for deciding if given a subset of column positions, the corresponding shifts are a modular Golomb ruler. These results are applied to filter generators used in the design of stream ciphers. Golić recommends that in order to withstand his inversion attack, one of the design requirements should be that the inputs of the non-linear filtering function are taken from positions of a Fibonacci LFSR which form a Golomb ruler. We propose using a Galois LFSR instead and selecting positions such that the corresponding shifts form a modular Golomb ruler. This would allow for a larger number of inputs to be selected (roughly n/2 rather than \(\sqrt{2n}\)) while still satisfying Golić’s requirement.
Ana Sălăgean, David Gardner, Raphael Phan

Golomb 80th Birthday Session (II)

On the Aperiodic Hamming Correlation of Frequency-Hopping Sequences from Norm Functions

Abstract
Frequency-hopping sequences (FHSs) are needed in frequency hopping code-division multiple-access (FH-CDMA) systems. Aperiodic Hamming correlation of FHSs matters in real applications, while it received little attraction in the literature compared with periodic Hamming correlation. In this paper, we study the aperiodic Hamming correlation of a family of FHSs via norm functions by Ding, Moisio and Yuan (IEEE Trans Inform Theory 53: 2606-2610, 2007). Bounds on their aperiodic Hamming correlation are established based on the calculation and estimation of some exponential sums over finite fields.
Zhengchun Zhou, Xiaohu Tang, Yang Yang, Udaya Parampalli

Perfect Sequences of Unbounded Lengths over the Basic Quaternions

Abstract
In this paper we show the existence of perfect sequences, of unbounded lengths, over the basic quaternions {1, − 1,i, − i,j, − j,k, − k}. Perfect sequences over the quaternion algebra were first introduced in 2009. One year later, a perfect sequence of length 5,354,228,880, over a quaternion alphabet with 24 elements, was shown. At this point two main questions were stated: Are there perfect sequences of unbounded lengths over the quaternion algebra? If so, is it possible to restrict the alphabet size to a small one? We answer these two questions by proving that any Lee sequence can always be converted into a sequence over the basic quaternions, which is an alphabet with 8 elements, and then by using the existence of Lee sequences of unbounded lengths to prove the existence of perfect sequences of unbounded lengths over the basic quaternions.
Santiago Barrera Acevedo, Thomas E. Hall

Linear Complexity

The Linear Complexity Deviation of Multisequences: Formulae for Finite Lengths and Asymptotic Distributions

Abstract
In the theory of stream ciphers, an important complexity measure to assess the (pseudo-)randomness of a stream generator is the linear complexity, essentially the complexity to approximate the sequence (seen as formal power series) by rational functions.
For multisequences with several, i.e. M, streams in parallel (e.g. for broadband applications), simultaneous approximation is considered.
This paper improves on previous results by Niederreiter and Wang, who have given an algorithm to calculate the distribution of linear complexities for multisequences, obtaining formulae for M = 2 and 3. Here, we give a closed formula numerically verified for M up to 8 and for M = 16, and conjectured to be valid for all M ∈ ℕ.
We model the development of the linear complexity of multisequences by a stochastic infinite state machine, the Battery–Discharge–Model, and we obtain the asymptotic probability for the linear complexity deviation d(n) : = L(n) − ⌈n·M/(M + 1)⌉ for M sequences in parallel as
$${prob}(d(n)=d)=\Theta\left(q^{-|d|(M+1)}\right),\forall M\in \mathbb N, \forall d\in\mathbb Z, \forall q=p^k.$$
The precise formula is given in the text.
Michael Vielhaber, Mónica del Pilar Canales Chacón

Linear Complexity of Binary Sequences Derived from Polynomial Quotients

Abstract
We determine the linear complexity of p 2-periodic binary threshold sequences derived from polynomial quotient, which is defined by the function \((u^w-u^{wp})/p \pmod p\). When w = (p − 1)/2 and \(2^{p-1}\not\equiv 1 \pmod{p^2}\), we show that the linear complexity is equal to one of the following values \(\left\{p^2-1,\ p^2-p,\ (p^2+p)/2+1,\ (p^2-p)/2\right \}\), depending whether \(p\equiv 1,\ -1,\ 3,\ -3\pmod 8\). But it seems that the method can’t be applied to the case of general w.
Zhixiong Chen, Domingo Gómez-Pérez

Word-Oriented Transformation Shift Registers and Their Linear Complexity

Abstract
We discuss the problem of counting the number of primitive transformation shift registers and its equivalent formulation in terms of Singer cycles in a corresponding general linear group. We also introduce the notion of word-oriented nonlinearly filtered primitive transformation shift registers based on a Langford arrangement and study their linear complexity.
Sartaj Ul Hasan, Daniel Panario, Qiang Wang

Frequency Hopping

Low-Hit-Zone Frequency-Hopping Sequence Sets with New Parameters

Abstract
In quasi-synchronous frequency-hopping multiple-access systems, low-hit-zone frequency-hopping sequence (LHZ-FHS) sets are commonly employed to minimize multiple-access interferences. In this paper, we present (near-)optimal LHZ-FHS sets with new parameters. We first analyze the Hamming correlation of frequency-hopping sequences (FHSs) constructed by the Cartesian product. We then present a new optimal LHZ-FHS set with respect to the Peng-Fan-Lee bound, which is obtained from the Cartesian product of two one-coincidence FHS sets. We also construct a near-optimal LHZ-FHS set from Kumar’s FHS set.
Jin-Ho Chung, Kyeongcheol Yang

New Optimal Low Correlation Sequences for Wireless Communications

Abstract
This paper presents three new sets of frequency hopping sequences, which are converted into sequences for CDMA. One of the CDMA sequence families is optimal with respect to the Welch bound, and two are nearly optimal. Our sequences are available for more lengths, and have much higher linear complexity than other CDMA sequences. They have a similar structure to the small Kasami set, but are balanced. The CDMA sequences are constructed using a composition method, which combines new shift sequences with pseudonoise columns to form an array. The array dimensions are relatively prime, so it is unfolded using the Chinese Remainder Theorem.
Each of our constructions gives rise to two additional families with larger family sizes but worse correlation as explained in Section 4.2.
Oscar Moreno, Andrew Tirkel

Correlation of Sequences

Autocorrelation Properties of Some Pulse Compression Codes Derived from P3 and P4 Codes

Abstract
In the paper, we survey autocorrelation properties of E_P3 and E_P4 codes derived from the P3 and P4 codes. In particular, analytical expressions for the aperiodic autocorrelation function and the peak sidelobe level of these codes are presented. We show that the considered codes are able to provide much smaller sidelobe level and relatively sharp mainlobe shape in comparison with the other known techniques that use the P3 and P4 codes. Due to their good autocorrelation properties, the E_P3 and E_P4 codes can be applied in radar and sonor systems.
Evgeny I. Krengel

On the d-ary Generalized Legendre-Sidelnikov Sequence

Abstract
We generalize the Legendre-Sidelnikov sequence to d-ary balanced sequence by using multiplicative character, where d is a common divisor of p − 1 and q − 1; p is an odd prime and q a power of an odd prime, and \(\gcd(p,q-1)=1\). Then with character sums we analyze some important pseudorandomness measures including (aperiodic) autocorrelation, power correlation of measure of order k, and linear complexity profile. Results show that aperiodic autocorrelation and power correlation measure of order 2 are ideal in terms of order of magnitude of a good pseudorandom sequence.
Ming Su

Invited Paper

Cyclotomy, Gauss Sums, Difference Sets and Strongly Regular Cayley Graphs

Abstract
We survey recent results on constructions of difference sets and strongly regular Cayley graphs by using union of cyclotomic classes of finite fields. Several open problems are raised.
Qing Xiang

Bounds on Sequences

Partial Fourier Codebooks Associated with Multiplied Golay Complementary Sequences for Compressed Sensing

Abstract
A new (N, K) partial Fourier codebook is constructed, associated with a binary sequence obtained by an element-wise multiplication of a pair of binary Golay complementary sequences. In the codebook, N = 2 m for a positive integer m, and K is approximately \(\frac{N}{4}\). It is shown that the maximum magnitude of inner products between distinct code vectors is nontrivially bounded in the codebook, which is approximately up to \(\sqrt{6}\) times the Welch bound equality for large N = 2 m with odd m. Finally, the new codebook is employed as a deterministic sensing matrix for compressed sensing, where its recovery performance is tested through numerical experiments.
Xiao Bian, Nam Yul Yu

Welch Bound for Bandlimited and Timelimited Signals

Abstract
Synchronisation must be established in any communication systems. In multicarrier communications, time and frequency offsets are taken into account. We use cross-ambiguity function to evaluate synchronisation performance and the interference in a CDMA system with such two-dimensional offsets. Welch bound for one dimensional and discrete time cross correlation function is extended to the one for two dimensional and continuous time cross ambiguity functions. This bound is compared with an ambiguity function for continuous time signal generated from discrete time signal with rectangular chip waveforms.
Yutaka Jitsumatsu, Tohru Kohda, Kazuyuki Aihara

Cryptography

Linear Weaknesses in T-functions

Abstract
We find linear (as well as quadratic) relations in a very large class of T-functions. The relations may be used in analysis of T-function-based stream ciphers.
Tao Shi, Vladimir Anashin, Dongdai Lin

Solving Compressed Right Hand Side Equation Systems with Linear Absorption

Abstract
In this paper we describe an approach for solving complex multivariate equation systems related to algebraic cryptanalysis. The work uses the newly introduced Compressed Right Hand Sides (CRHS) representation, where equations are represented using Binary Decision Diagrams (BDD). The paper introduces a new technique for manipulating a BDD, similar to swapping variables in the well-known sifting-method. Using this technique we develop a new solving method for CRHS equation systems. The new algorithm is successfully tested on systems representing reduced variants of Trivium.
Thorsten Ernst Schilling, Håvard Raddum

Aperiodic Correlation

On Random Binary Sequences

Abstract
A binary sequence A = (a 0,a 1,…,a n − 1) of length n is an element of { − 1,1} n and its autocorrelation at shift u is C u (A) = ∑  j a j a j + u . We use the ℓ r norm of (C 1(A),C 2(A),…,C n − 1(A)) to measure the collective smallness of the autocorrelations and, when A is drawn uniformly from { − 1,1} n , determine the asymptotic behaviour, as n → ∞, of the expectation of these norms and prove asymptotic concentration around the expected value. For integral r, we also give exact expressions for the expectation of the rth power of these ℓ r norms. This complements results of Borwein and Lockhart for r = 2 and the present author for r = ∞ and extends partial results of Mercer for even integral r.
Kai-Uwe Schmidt

The Density of Ternary Barker Sequences

Abstract
Ternary Barker sequences are sequences whose elements are in -1,0,1 for which every aperiodic offset autocorrelation has magnitude at most 1. Despite promising properties, they have received little attention from both the signals and mathematics communities. In this paper, we demonstrate the existence of ternary Barker sequences to answer a question of Millar. We enumerate ternary Barker sequences of length up to 44 and summarize some features of these sequences. Of primary interest is the density, or proportion of nonzero entries in a sequence. We also briefly examine the relation between density and merit factor.
Tomas Boothby

Walsh Transform

New Three-Valued Walsh Transforms from Decimations of Helleseth-Gong Sequences

Abstract
Recently, starting from Helleseth-Gong sequences, Gong, Helleseth, and Hu found many decimation numbers which yield three-valued Walsh transforms by computer search. They proved two cases. In this paper, we prove two more cases with new observations.
Guang Gong, Tor Helleseth, Honggang Hu, Chunlei Li

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise