We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set$S$of linearly independent combinations of the sub-symbols of the lost symbol. When$S=\varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When$S$is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on$\vert S\vert$and not the content of$S$and construct a lower bound on the repair bandwidth of a linear repair scheme with side information$S$We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.

Motivated by the application of Reed-Solomon codes to recently emerging decentralized storage systems such as Storj and Filebase/Sia, we study the problem of designing compact repair groups for recovering multiple failures in a decentralized manner. Here, compactness means that the corresponding trace repair schemes of these groups of helpers can be generated from a single or a few seed repair schemes, thus saving the time and space required for finding and storing them. The goal is to design compact repair groups that can tolerate as many failures as possible. It turns out that the maximum number of failures a collection of repair groups can tolerate equals the size of a minimum hitting set of a collection of subsets of the finite field ${\mathbb{F}_{{q^\ell }}}$ minus one. When the repair groups for each symbol are generated from a single subspace, we establish a pair of asymptotically tight lower bound and upper bound on the size of such a minimum hitting set. Using Burnside’s Lemma and the Möbius inversion formula, we determine a number of subspaces that together attain the upper bound on the minimum hitting set size when the repair groups are generated from multiple subspaces.

The issue of repairing Reed-Solomon codes currently employed in industry has been sporadically discussed in the literature. In this work we carry out a systematic study of these codes and investigate important aspects of repairing them under the trace repair framework, including which evaluation points to select and how to implement a trace repair scheme efficiently. In particular, we employ different heuristic algorithms to search for low-bandwidth repair schemes for codes of short lengths with typical redundancies and establish three tables of current best repair schemes for [n, k] Reed-Solomon codes over GF(256) with 4 ≤ n ≤ 16 and r = n − k ∈ {2, 3, 4}. The tables cover most known codes currently used in the distributed storage industry.

The 3XORSUM problem aims to find (x, y, z) such that x + y + z = 0 over {0, 1}d, with each variable drawn from one of 3 randomly generated lists. In addition to being of interest in its own right, this problem has cryptographic applications including proof of stake methods in Blockchain.The 3XORSUM problem is also related to the integer 3SUM problem from theoretical computer science on which there is extensive recent literature. It is conjectured that the integer 3SUM problem has complexity $\tilde \Omega \left({{n^2}}\right)$ for lists of size O(n).Wagner [10] has presented an algorithm with complexity Õ(2d/3) for finding a 4XORSUM solution (x + y + z + w = 0) with each variable drawn from one of 4 randomly generated lists of size O(2d/3) with members from {0, 1}d.We present an algorithm which solves the 3XORSUM problem for randomly generated binary vectors from {0, 1}dwith time and memory complexity Õ(n) = Õ(2d/3). This substantially improves results from [1], [8]. Our algorithm has applications to blockchains and other cryptographic problems.

The design of code division multiple access sequence families dates back to the Gold sequences from the 1960s. Since then there has been a number of different such designs with good correlation properties, some optimal and some near-optimal. In this paper, we use the concept of plateaued functions with arbitrary degree, in order to compute their full correlation distributions. First, we give an explicit correlation distribution of a sequence family using a non-quadratic function. Then for the quadratic functions, we present a general classification of “Gold-like” sequence families for all possible characteristics p and degrees n of the Galois field Fpnused to define the sequences. We are able to obtain the full correlation distribution of the families we consider. This paper also uses techniques from the theory of algebraic curves in order to obtain some of the results.

Randomness is crucial to enabling secure and robust communications. Ideally one should harness high entropy physical processes, but this is difficult so pseudorandomness is usually substituted for randomness. We introduce improved complexity randomness tests and use them to judge three pseudorandom bit generators; the AES block cipher (standard, strongly believed to be secure), the Dragon stream cipher (eStream finalist), and the GNU C library function rand(). We also test the output from a quantum random bit generator (QRBG). While the two ciphers can easily be distinguished from the much inferior rand(), the output statistics of the two classical generators are similar to that of the QRBG, and both provide high-quality pseudorandom bits.

The design of CDMA sequence families using quadratic functions dates back to Gold sequences from the 1960s. Since then there have been a number of different such designs with good correlation properties, some optimal and some near-optimal, and the term “Gold-like” is usually used to denote such sequences. In this paper we use the concept of plateaued functions, not necessarily quadratic, in order to classify such sequence families and present some examples in this direction which depend on the characteristic p and degree n of the Galois field Fpnused to define the sequences.

In this paper we generalize a previous construction in order to design perfect autocorrelation sequences over the so-called PSK+ constellation defined by Boztaş and Udaya [2]. We give a number theoretic criterion for the existence of the new sequences with perfect autocorrelation, and discuss some preliminary numerical results on their aperiodic correlations and merit factors.

In this paper a new binary sequence family with 2n+ 1 cyclically distinct sequences each having length 2n- 1 is presented for an even integer n. The correlation distribution of the family is fully determined. The family has six-valued correlation distribution and its maximum correlation magnitude equals 1+2n/2+1.

The Levenshtein bound on aperiodic correlation, which is a function of the weight vector, is tighter than the Welch bound for sequence sets over the complex roots of unity when$M\geq 4$and$n\geq 2$, where$M$denotes the set size and$n$the sequence length. Although it is known that the tightest Levenshtein bound is equal to the Welch bound for$M\in\{1,2\}$, it is unknown whether the Levenshtein bound can be tightened for$M=3$, and Levenshtein, in his paper published in 1999, postulated that the answer may be negative. A new weight vector is proposed in this paper, which leads to a tighter Levenshtein bound for$M=3$,$n\geq 3$and$M\geq 4$,$n\geq 2$. In addition, the explicit form of the weight vector (which is derived by relating the quadratic minimization to the Chebyshev polynomials of the second kind) in Levenshtein's paper is given. Interestingly, this weight vector also yields a tighter Levenshtein bound for$M=3$,$n\geq 3$and$M\geq 4$,$n\geq\sqrt{M}$, a fact not noticed by Levenshtein.

The Levenshtein bound, as a function of the weight vector, is only known to be tighter than the Welch bound on aperiodic correlation for K ≥ 4, N ≥ 2, where K and N denoting the set size and the sequence length, respectively. A quadratic weight vector is proposed in this paper which leads to a tighter Levenshtein bound for K ≥ 4, N ≥ 2 and K = 3, N ≥ 4. The latter case was left open by Levensthein.

In this paper, we revisit a method to produce binary sequences using the most significant bit map fromZ4to the binary field. This method is useful for the construction of binary sequences with low correlation and large family size. There may be more cases where starting withZ4could help researchers design new low correlation sequences for code-division multiple access application.

We consider the oblivious distributed guessing of a random variable in three scenarios (single guessor, single constrained guessor, multiple guessors). The optimal guessing schemes in each case are obtained by means of a probability distribution which the guessor(s) use in order to determine their sequence of guesses. Some of the optimal distributions obtained have links to Renyi's generalization of Shannon's entropy, while one of them is related to the rthpower means from mathematical analysis.

The design of pseudorandom sequences with optimal correlation properties forms a crucial part of communications and radar engineering. With the increasingly crowded electromagnetic spectrum, interference between different systems is becoming more important. In this paper, we consider the Low Probability of Intercept properties of some commonly used sequence families, with respect to their triple correlation function. The binary families we consider include the Gold sequence family, the Gold-like sequence family with quadratic span, and the Bent Function sequence family.

The design of pseudorandom sequences with optimal correlation properties forms a crucial part of communications and radar engineering. Perfect autocorrelation sequences are however very rare. We recall a technique that yields examples of nonbinary sequences with perfect autocorrelation over enlarged PSK (PSK+) alphabets. It turns out that there are a large number of existing sequence constructions that we can utilize yield perfect correlation sequences, and that this affords a large number of choices for the length and alphabet of such sequences. We have also considered sequences with ideal autocorrelation with respect to their LPI/LPD properties and obtained initial results in this direction.

Abstract Fingerprint biometric authentication has particular advantages in a highly mobile environment. We investigate design issues involved in building authentication systems using minutia‐based fingerprint templates, where the template is protected during comparison as well as storage. Two popular bio‐cryptographic schemes based on the set difference metric, the Fuzzy Vault and PinSketch, are analysed with regard to theoretical bounds on the template sizes and decision thresholds. We define six different minutiae‐based templates and for each, quantisation parameters are determined that yield the best matching performance at a threshold where the probability of false match is zero. We then determine which, if any, of the representations satisfy the theoretical bounds proposed for each bio‐cryptographic construct. We implement a PinSketch‐based authentication system that uses a combination of a commonality and a set difference measure to securely compare two fingerprint templates, with negligible deterioration in accuracy. Our results indicate that to securely correct the degree of intra‐sample error observed in minutiae‐based templates, efficient commonality‐based error tolerant cryptographic constructs will be more suited than set difference based constructs. Copyright © 2010 John Wiley & Sons, Ltd.

The design of pseudorandom sequences with optimal correlation properties forms a crucial part of communications and radar engineering. Perfect autocorrelation sequences are however exceedingly rare. We discuss a technique that yields examples of such designs over enlarged PSK (PSK+) alphabets. We also design nearly perfect autocorrelation sequences over enlarged QAM (QAM+) alphabets, compatible with contemporary wireless transmission standards.

In this paper we revisit a method to produce binary sequences using a non-linear polynomial mapping from Z4to the binary field. This method is useful to construct binary sequences with low correlation with large sizes. We conclude that Z4may be the best starting ring to generate large binary families for code-division multiple access (CDMA) application.

We introduce a fast spectral algorithm for computing influences of variables for Boolean functions. The influence of variables, as defined in computer science has close relationships with some criteria used in cryptographic evaluation of boolean functions, especially resilience. Our spectral algorithm can also be utilized to compute the resilience of Boolean functions. The algorithm is also of independent interest as a generalization of the Walsh-Hadamard transform.

In the 1990s Chlamtac and Faragó introduced a Transmission Scheduling (TS) algorithm for wireless networks, called the (Proper Robust Scheduling) PRS algorithm, later generalized to ML-PRS by Boztas to support a set of multi-priority users, each with different transmission characteristics. More recently, this concept has been extended to TSMA (Time Spread Multiple Access) protocols-TDMA style protocols which are independent of network topology, subject to some global constraints, such as number of users, and maximum degree of the graph representing connectivity of the wireless network. We propose two improvements to TSMA protocols in this paper. The first one uses constant weight codes to reduce PRS framelength. The second one uses the coset structure of Galois fields to improve the ML-PRS algorithm by supporting more lower priority users for roughly comparable framelength.

We describe narrow, erasure, hybrid and wide attacks on fingerprinting schemes used for securing digital content, and introduce new classes of codes, namely vector space block design codes and /spl delta/-nonlinear codes, which can be used to defend against such attacks by means of traitor tracing.

We present a noiseless source coding problem in a broadcast environment and supply a simple solution to this problem. A transmitter wishes to transmit a binary random vector X/sub 1//sup n/ = (X/sub 1/, X/sub 2/, ..., X/sub n/) to n receivers, where receiver k is only interested in the component X/sub k/. A source encoding is a binary sequence f = (f/sub 1/, f/sub 2/, ...) which is chosen by the transmitter. The expected time at which the k/sup th/ receiver determines X/sub k/ is denoted l(f, k). This means that the initial segment (f/sub 1/, f/sub 2/, ..., f/sub l(f, k)/) of the encoding allows unique decoding of X/sub k/. We define the performance measure L(n) = min/sub f/ max/sup k/ l(f, k), where the minimization is over all possible encoding, and wish to approach it by practical schemes. For the case of independent but not necessarily identically distributed Bernoulli sources, we demonstrate encoding scheme f for which; lim /sub n/spl rarr//spl infin// [max/sub k/ l(f, k)/(n + 1)/2] = 1, where n+1/2 is the arithmetic mean of the values (l(f, K))/sub k=1//sup n/ obtained by the naive scheme f/sub k/ = X/sub k/. In the naive scheme, the worst case receiver learns its value only after n bits have been received, so this is a substantial improvement. In conclusion, we constructively establish that the inequality L(n) /spl les/ n+3/2 holds for stationary, ergodic and bitwise independent sources. We also generalize our results to the case where each receiver is interested in a block of data, as opposed to only one bit. The determination of flower bounds on L(n) is still open.

In the above paper by E. Arikan (see ibid., vol.42, no.1, p.99-105, 1996) an asymptotically tight upper bound on the /spl rho/th moment (/spl rho//spl ges/0) of the minimal number of guesses required to determine the value of a random variable was derived. We show that we can tighten this bound for the case of positive integer moments (when /spl rho/=1, the bound is improved by a factor of 2) and that the new bound also applies to a class of nonminimal guessing sequences.

A new construction of optimal binary sequences, identical to the well known family of Gold sequences in terms of maximum nontrivial correlation magnitude and family size, but having larger linear span is presented. The distribution of correlation values is determined. For every odd integer /spl tau//spl ges/3, the construction provides a family that contains 2/sup /spl tau//+1 cyclically distinct sequences, each of period 2/sup /spl tau//-1. The maximum nontrivial correlation magnitude equals 2(/spl tau/+1)/sup /2/+1, with one exception, each of the sequences in the family has linear span at least (/spl tau//sup 2/-/spl tau/)/2 (compared to 2/spl tau/ for Gold sequences). The sequences are easily implemented using a quaternary shift register followed by a simple feedforward nonlinearity.>

Two families of four-phase sequences are constructed using irreducible polynomials over Z/sub 4/. Family A has period L=2/sup r/-1. size L+2. and maximum nontrivial correlation magnitude C/sub max/>