A secret key agreement framework involving three users is considered in which each of the users 1 and 2 intends to share a secret key with user 3 and users 1 and 2 are eavesdroppers with respect to each other. There is a generalized discrete memoryless multiple access channel (GDMMAC) from users 1 and 2 to user 3 where the three users receive outputs from the channel. Furthermore, there is a feedback channel from user 3 to users 1 and 2 through which user 3 sends information extracted from the received output from the GDMMAC to increase the key rates. We consider both noiseless and noisy feedback. In the case of noiseless feedback, a public channel of unlimited capacity from user 3 to users 1 and 2 is used only once. In the case of noisy feedback, a noisy broadcast channel (BC) from user 3 to users 1 and 2 can be repeatedly used, like GDMMAC. In both setups, inner bounds of the secret key capacity region are derived. The secret key capacity region is derived in some special cases where the channel inputs and outputs form Markov chains in certain orders. For illustration, the corresponding results are also derived and discussed for Gaussian channels. The cases with noiseless feedback, noisy feedback, and no feedback at all are compared with each other.

In this paper, a generalized multiple access channel (MAC) model for secret key sharing between three terminals is considered. In this model, there are two transmitters and a receiver where all three terminals receive noisy channel outputs. In addition, there is a one-way public channel from the transmitters to the receiver. Each of the transmitters intends to share a secret key with the receiver by using the MAC and the public channel, where the transmitters are eavesdroppers with respect to each other. Two strategies for secret key sharing are considered, namely, the pregenerated key strategy and the two-stage key strategy. For both of them, inner and outer bounds of the secret key capacity region are derived. Furthermore, the effect of the public channel is discussed and the two strategies are compared. In both strategies, it is assumed that the channel outputs at the transmitters are only used for eavesdropping and not as inputs to the encoders. The effect of this assumption in the presence of the public channel is analyzed for some Gaussian MACs.

In this paper, a new, soft two-level approach for the generation of multiple and revocable biometric keys, adapted to the analog nature of biometric signals, is proposed. It consists of a novel randomized soft code-offset construction for the Euclidean metric, at the first level, and a code-redundancy construction for the Hamming metric, possibly based on a Reed-Solomon code, at the second level. The Shannon entropy analysis shows that the new construction achieves optimal security with respect to biometric template protection, whereas the previously proposed constructions for the Euclidean metric are shown to be insecure in the multiple-key setting. In addition, a general code-offset construction for the Hamming metric is analyzed in terms of the Shannon entropy instead of the usual min entropy. This allows a nice characterization of the codes that provide biometric template protection in the multiple-key scenario as well as a further differentiation among these codes with respect to the achievable security level.

Exact analytical expressions for various probability distributions in a type of stream ciphers known as memoryless combiners are derived. They relate to arbitrary linear functions and subvectors of output bits as well as to arbitrary linear functions and subvectors of input bits when the output sequence is assumed to be given. Practical approximations to the exact expressions to be used in one-step and iterative fast correlation attacks and statistical distinguishers are proposed. More generally, the results also apply to arbitrary binary linear codes that are nonlinearly transformed by time-variant Boolean functions. For comparison, the corresponding probability distributions for linear block codes on a memoryless time-variant binary symmetric channel are also determined and some practical consequences pointed out.

A new method for digital true random number generation based on asynchronous logic circuits with feedback is introduced. In particular, a concrete technique using the so-called Galois and Fibonacci ring oscillators is developed and analyzed both theoretically and experimentally. The generated random binary sequences may have a very high speed and a higher and more robust entropy rate in comparison with previous proposals for digital random number generators. A new method for digital postprocessing of random data based on irregularly clocked nonautonomous synchronous logic circuits with feedback is also introduced and a concrete technique using a self-clock-controlled linear feedback shift register is proposed. The postprocessing can provide both randomness extraction and computationally secure speed increase of input random data

A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a constrained form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is defined. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail and the concept of divide-and-conquer algebraic attacks is introduced. Special properties of combiners with finite input memory, such as nonlinear filter generators, are also established. It is also pointed out that Groumlbner basis algorithms may be used for finding low-degree induced algebraic equations

A clock-controlled linear feedback shift register (LFSR) is a simple keystream generator consisting of an LFSR whose clock is controlled by another LFSR so that the output is an irregularly decimated LFSR sequence. Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the keystream sequence from a purely random sequence. Previously proposed statistical distinguishers for clock-controlled LFSRs are based on detecting binary linear relations in the keystream sequence that hold with a probability sufficiently different from one half. In this paper, a novel approach based on the correlation analysis of clock-controlled LFSRs is introduced. It significantly reduces the required computation time and essentially consists of a probabilistic reconstruction of bits in the regularly clocked LFSR sequence that satisfy the LFSR recurrence or any linear recurrence derived from low-weight multiples of the LFSR characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally. The new approach shows that there is no need to deal with the majority bits of blocks of LFSR bits as proposed recently. If individual bits or blocks of bits are considered instead, then the underlying probabilities can be computed theoretically instead of heuristically, which in turn allows a simple and general theoretical analysis of the keystream sequence length required

The edit distance correlation attack on the well- known alternating step generator for stream cipher applications was proposed by Golic and Menicocci. The attack can be successful only if the probability of the zero edit distance, the so-called embedding probability, conditioned on a given segment of the output sequence, decreases with the segment length, and if the decrease is exponential, then the required segment length is linear in the total length of the two linear feedback shift registers involved. The exponential decrease for the maximal value of the embedding probability, regarded as a function of the output segment, was estimated experimentally by Golic and Menicocci. In this paper, by using the connection with the interleaving and decimation operations, the embedding probability is analyzed theoretically. Exponentially small upper bounds on the maximal embedding probability are thus derived. An exact expression for the minimal embedding probability is also determined

A theoretical framework for correlation attacks based on edit distances and edit probabilities on binary keystream generators consisting of clock-controlled shift registers combined by a function with memory is introduced. Recursive algorithms for efficient computation of the proposed many-to-one string edit distances and statistically optimal edit probabilities are derived for both constrained and unconstrained irregular clocking. The distances and probabilities are based on mutually correlated linear transforms of input and output sequences in the corresponding regularly clocked combiner with memory. Linear transforms can also incorporate linear models of clock-controlled shift registers. The complexity of the recursive algorithms is exponential in the memory size of the input linear transform which can be considerably smaller than the memory size of combining function. This is demonstrated for a special type of combiners with memory based on a time-varying memoryless function. In addition, a decimation method for reducing the memory size of the input linear transform is proposed. The design criteria with respect to the introduced correlation attacks are also discussed.

The relation between fast correlation attacks on stream ciphers based on linear feedback shift registers (LFSRs) and the Hartmann-Rudolph (1976) algorithm for optimal symbol-by-symbol decoding of linear block codes is theoretically investigated. By iterating approximate versions of the HR algorithm, novel iterative probabilistic decoding algorithms for fast correlation attacks are developed. In particular, these algorithms can be applied when a large number of nonorthogonal parity checks are used. A number of properties of the proposed iterated versions of the HR algorithm including convergence conditions and critical bit error rates are derived.

A nonlinear filter generator is a basic keystream generator for stream cipher applications consisting of a single linear feedback shift register whose output is filtered by a nonlinear combining function. A binary nonlinear filter generator is viewed as a finite input memory automaton with one binary input and one binary output. The generalized inversion attack on a binary nonlinear filter generator is developed and analyzed by the theory of critical branching processes. Its objective is to recover the unknown input sequence from a given segment of the output sequence, provided that the filter function is known. Unlike the inversion attack, which requires that the filter function be linear in the first or the last input variable, this attack can be applied for any filter function. Both theory and systematic experiments show that its time complexity remains dose to 2/sup M/, which is the time complexity of the inversion attack, where M denotes the input memory size in bits.

A binary stream cipher consisting of three short linear-feedback shift registers (LFSRs) of total length 64 that are mutually clocked in the stop/go manner is cryptanalyzed in the known keystream sequence scenario. To reconstruct the internal state candidates at a known time from about 64 known keystream bits, two algorithms are developed. One is based on guessing a number of elements of the clock-control sequence and has a computational complexity of about 2/sup 40/ steps, where the average step complexity is comparable to the step complexity of the exhaustive search method. The other exploits a time-memory tradeoff based on the well-known birthday paradox and is successful if approximately T/spl middot/M/spl ges/2/sup 64/, where T is the required computational time in table lookups and M is the memory in 64-bit words. As the state-transition function is not one-to-one, to recover the initial state from the internal state candidates, two algorithms are introduced. One consists in guessing the number of clocks for each of the LFSRs. The other consists in the reversion of the internal states and is based on the theory of critical and subcritical branching processes.

A novel analytical approach to performance evaluation of soft-decoding algorithms for binary linear block codes based on probabilistic iterative error correction is presented. A convergence condition establishing the critical noise rate below which the expected bit-error probability tends to zero is theoretically derived. It explains the capability of iterative probabilistic decoding of binary linear block codes with sparse parity-check matrices to correct, with probability close to one, error patterns with the number of errors (far) beyond half the code minimum distance. Systematic experiments conducted on truncated simplex codes seem to agree well with the convergence condition. The method may also be interesting for the theoretical analysis of the so-called turbo codes.

For original paper see Feder and Merhav (IEEE Trans. Inform. Theory, vol.40, p.259-66, 1994 January). The present authors discuss the upper and lower bounds on the equivocation in terms of the Bayes error probability.

A keystream generator, known as RC4, consisting of a permutation table that slowly varies in time under the control of itself, is analyzed by the linear model approach. The objective is to find linear relations among the keystream bits that hold with probability different from one half by using the linear sequential circuit approximation method. To estimate the corresponding correlation coefficients, some interesting correlation properties of random Boolean functions are derived. It is thus shown that the second binary derivative of the least significant hit output sequence is correlated to 1 with the correlation coefficient close to 15/spl middot/2/sup -3n/ where n is the variable word size of RC4. The output sequence length required for the linear statistical weakness detection is then around 64/sup n//225. The result can be used to distinguish RC4 from other keystream generators and to determine the unknown parameter n, as well as for the plaintext uncertainty reduction if n is small.

A probabilistic analysis is conducted to determine conditional and unconditional correlation weaknesses of cascades of up/down clocked shift registers. Similar results are also obtained for cascades of stop/go clocked shift registers. It is theoretically explained how to use the derived properties for fast correlation attacks, whose objective is to recover the linear feedback shift-register initial states, and the conditions for their success are obtained. The analysis and computations conducted indicate that the attacks are feasible in the practical case of relatively short cascades composed of long shift registers.

Periods of interleaved and nonuniformly decimated integer sequences are analyzed. A characterization of the period of an interleaved sequence in terms of the constituent periodic integer sequences is first derived. This is then used to generalize the result of Blakley and Purdy (1981) on the period of a decimated integer sequence obtained by a periodic nonuniform decimation. The technique developed and results may be interesting for analyzing the period of various pseudorandom sequences, especially in stream cipher and spread-spectrum applications.

An exponentially small upper bound on the probability that a given binary string of length n can be embedded into a uniformly distributed random binary string of length $2n$ by inserting at most one bit between any two successive bits and an arbitrary number of bits at the end is analytically derived. This probability is important for a cryptanalytic problem of the initial state reconstruction of a binary clock-controlled shift register that is clocked either once or twice per each output symbol, given a segment of its output sequence. The developed approach may also be interesting for other problems of sequence comparison as well, especially for the codes for correcting synchronization errors.

It is shown that an arbitrary binary keystream generator with M bits of memory can be linearly modeled as a non-autonomous linear feedback shift register of length at most M with an additive input sequence of nonbalanced identically distributed binary random variables. The sum of the squares of input correlation coefficients over all the linear models of any given length proves to be dependent on a keystream generator. The minimum and maximum values of the correlation sum along with the necessary and sufficient conditions for them to be achieved are established. An effective method for the linear model determination based on the linear sequential circuit approximation of autonomous finite-state machines is developed. Linear models for clock controlled shift registers and arbitrary shift register based keystream generators are derived. Several examples including the basic summation generator, the clock-controlled cascade, and the shrinking generator are presented. Linear models are the basis for a general structure-dependent and initial-state-independent statistical test. They may also be used for divide and conquer correlation attacks on the initial state. Security against the corresponding statistical attack appears hard to control in practice and generally hard to achieve with simple keystream generator schemes.

A concept of constrained many-to-one string edit distances, with or without memory, based on edit operations of deletion and substitution is introduced, and the recursive algorithms for their efficient computation are derived. Their use for correlation attacks on clock-controlled shift register based keystream generators is proposed, the divide and conquer effect is examined, and the generalized reducibility property of functions with memory is pointed out as a design criterion.

Starting from a memory-based nonlinear generator due to P.R. Geffe (1973), a binary sequence generator (MEM-BSG), consisting of three linear feedback shift registers and a variable memory, is defined and analyzed. The MEM-BSG is shown to be convenient for generating fast binary sequences of large period and linear complexity, which may be useful in spread-spectrum and cryptographic applications.>

It is proved that the product of arbitrary periodic GF(q) sequences attains maximum linear complexity if their periods are pairwise coprime. The necessary and sufficient conditions are derived for maximum linear complexity of the product of two periodic GF(q) sequences with irreducible minimal characteristic polynomials. For a linear combination of products of arbitrary periodic GF(q) sequences, it is shown that maximum linear complexity is achieved if their periods are pairwise coprime and the polynomial x-1 does not divide any of their minimal characteristic polynomials; assuming only that their periods are pairwise coprime, the author establishes a lower bound on the linear complexity which is of the same order of magnitude as maximum linear complexity. Boolean functions are derived that are optimal with respect to the maximum linear complexity. Possible applications of the results in the design of sequence generators are discussed.>

A lower bound is derived on the probability that when a PN-sequence of period N=2/sup n/-1 is nonuniformly decimated by means of a sequence whose period divides M, the decimated sequence will have maximum linear complexity nM. It is shown that by choosing M and n appropriately, this probability can be made arbitrarily close to one with nM arbitrarily large.>

The concepts of efficiency measures of multicategory information systems and similarity measures between two efficiency measures are introduced and developed. The relationship between two efficiency measures is defined by the corresponding setD, and the appropriate marginal functions are introduced. An earlier work of Ben-Bassat's dealing with the ranking of features according to feature selection criteria is generalized and refined. Consequently, a general similarity measure between two efficiency measures is established. It is analyzed in the case of monotonic marginal functions and, especially, when the setDis convex. Some important sufficient conditions forDto be convex are also given. Finally, two other similarity measures are defined and interpreted.

The concept of efficiency measures of multicategory information systems as well as the concepts of the relationship and the similarity measures between two efficiency measures have been recently introduced and developed. In this paper, the concave measures as a general class of efficiency measures and the information measures as a special class of concave measures are defined and investigated. The relationship between any concave measure, information measure in particular, and the Bayes probability of errorP_{B}is determined for any2\leq Q < \infty, whereQdenotes the number of categories in a multicategory information system. The so-called\epsilon_{ }0 and\epsilon_{m}criteria are proposed as the similarity measures between the information measures andP_{B}. The problems of determination, for any2 \leq Q < \infty, of all the information measures with minimal\epsilon_{0}and\epsilon_{m}criteria, called\epsilon_{0}-optimal and\epsilon_{m}-optimal, are formulated and completely solved, respectively. Additionally, the minimal values of\epsilon_{0}and\epsilon_{m}criteria are evaluated as well. It is pointed out that the well-known average conditional quadratic entropy is for all2 \leq Q < \inftyvery close to the\epsilon_{0}-optimal and\epsilon_{m}-Optimal information measures with respect to\epsilon_{0}and\epsilon_{m}criteria, respectively.

The information measures, as a special class of efficiency measures of muiticategory information systems, and their relations to the Bayes probability of errorP_{B}have been recently defined and investigated. Another class of efficiency measures called the separability measures is introduced in this paper. The relationship between any separability measure andP_{B}is determined for any2 \leq Q < \infty, whereQdenotes the number of categories in a multicategory information system. As before,\epsilon_{0}and\epsilon_{m}criteria are proposed as the similarity measures between the separability measures andP_{B}. The problems of determination, for any2 \leq Q < \infty, of all the separability measures with minimal\epsilon_{0}and\epsilon_{m}criteria, called\epsilon_{0}-optimal and\epsilon_{m}-Optimal, are defined and completely solved, respectively. The minimal values of\epsilon_{0}and\epsilon_{m}criteria are evaluated as well. It is proved that the information measures are for each3 \leq Q < \inftymore similar toP_{B}than the separability measures with respect to the minimal values of both\epsilon_{0}and\epsilon_{m}criteria. It is pointed out that the average conditional quadratic entropy is not only an information measure but also a separability measure, which is, for each3\leq Q < \infty, \epsilon_{0}-optimal and very close to\epsilon_{m}-optimal separability measures with respect to the\epsilon_{m}criterion.

A necessary and sufficient condition for the most likely letter of any discrete source to be coded by a single symbol with aD-ary Huffman code,2 \leq D < \infty, is derived. As a consequence, a lower bound on the redundancy of aD-ary Huffman code is established.