How Can Linear-feedback Shift Register Be Modified

Linear Feedback Shift Register

A linear feedback shift register (LFSR) linear feedback shift annals (LFSR) is a shift register whose input bit is the output of a linear function of two or more of its previous states (taps).

From: Cryptographic Boolean Functions and Applications , 2009

Fourier Analysis of Boolean Functions

Thomas W. Cusick Professor of Mathematics , Pantelimon Stanica Professor of Mathematics , in Cryptographic Boolean Functions and Applications (Second Edition), 2017

2.eleven LFSRs and Linear Complication

In digital circuits a shift register is a blazon of sequential logic circuit, mainly for storage of digital information, set up in a linear fashion which has its inputs connected to the outputs in such a way that the information is shifted down the line when the circuit is activated [289,536,627].

A linear feedback shift annals (LFSR) is a shift register whose input bit is the output of a linear function of ii or more of its previous states (taps). An LFSR of length m consists of thousand stages numbered $0,1,\dots ,m-1$ , each capable of storing one bit, and a clock controlling data commutation. A vector with entries ${\mathrm{southward}}_0,\dots ,{\mathrm{south}}_{m-\mathrm{ane}}$ would initialize the shift register. At time i, the following operations are performed [583, Department one.ane]:

1.

$s_i$ (the content of stage 0) forms role of the output;

2.

the content of stage i is shifted to phase $i-1$ , for $\mathrm{ane}\le i\le \mathrm{one\; thousand}-\mathrm{i}$ ;

3.

the new content (the feedback bit) of the stage $\mathrm{thousand}-1$ would exist obtained past xor-ing a subset of the content of the yard stages.

The initial input of an LFSR is called a seed. Since any register has a finite number of possible states, it must eventually be periodic. However, an LFSR with a well-chosen feedback function and seed can produce a sequence of bits which appears random (has skillful statistical properties) and which has a big period.

LFSRs can be applied in generating pseudo-random numbers, pseudo-dissonance sequences, fast digital counters, whitening sequences, cryptography, etc., and they can be implemented in both software and hardware. We shall use the concept heavily in Chapter 7.

In that location are many possible configurations, and we present a unproblematic one in Figure 2.ane which starts from an input of all one'due south and is very piece of cake to implement in software and hardware. An LFSR of this type volition never contain but 0's and would stop if an all 0 binary string is fed into the LFSR. But some choices of taps (that is, the nonzero coefficients $c_i$ defined below) will generate a maximal sequence with a menstruation of ${\mathrm{two}}^n-1$ cycles. The depicted LFSR of Figure 2.1 will generate the following sequence if fed the first (left) four $.25:

Figure 2.1. LFSR with 5 stages S _i , and feedback bit S _four  = South _ane  ⊕ S ₃.

$\mathrm{i},1,1,1,0,\mathrm{one},0,0,\mathrm{ane},\mathrm{ane},\mathrm{one},0,1,0,0,\mathrm{ane},\mathrm{i},1,0,1,0,0,1,\mathrm{ane},1,0,\mathrm{one},0,0,1.$

If the content of the stage $S_i$ is $s_i$ , $0\le i\le m-1$ , and then $[s_{m-1},\dots ,s_{\mathrm{ane}},s_0]$ is chosen the initial state of the LFSR. From the definition of an LFSR, the output sequence $s_0,{\mathrm{due\; south}}_1,\dots$ will satisfy the following recursion

$s_j=\sum _{i=1}^m{c}_i{\mathrm{due\; south}}_{j-i},j\ge m.$

The polynomial $C(x)=1+c_{1}x+\cdots +c_m{x}^{\mathrm{1000}}$ is the feedback (or connection) polynomial of the sequence ${\{s_j\}}_j=\{s_j:j=0,1,\dots \}$ . The LFSR is said to exist nonsingular if $c_m\ne 0$ , that is, the degree of its feedback polynomial is m.

In the shown case of Effigy 2.1, the constants are $c_1=1$ , $c_{\mathrm{ii}}=0$ , $c_3=1$ , $c_4=0$ , and so, its feedback polynomial is $C(x)=1+x+x^{\mathrm{three}}$ .

The output sequence of the LFSR can be generated past more than one register. The lowest degree polynomial associated to any such annals is chosen a minimal polynomial. Only put, the polynomial $P(x)=\sum _{i=0}^d{p}_i{x}^i$ is minimal for ${\{{\mathrm{due\; south}}_j\}}_j$ if it has the lowest degree such that

$p_0{s}_j+p_1{s}_{j+\mathrm{ane}}+\cdots +p_d{s}_{j+d}=0,\text{for all}j\in \mathbb{N}.$

If d is the degree of the minimal polynomial of an LFSR, the output sequence has maximum period $2^d-\mathrm{one}$ (and we call such a sequence an m-sequence), regardless of the initial nonzero seed if and only if the minimal polynomial is archaic (that is, any of its roots is a archaic $(2^d-1)$ -root of unity and will generate the multiplicative structure of the finite field ${\mathbb{F}}_{2^d}$ ).

Nosotros ascertain the linear span or linear complexity $L(\mathbf{s})$ of a binary space sequence $\mathbf{due\; south}={\{s_j\}}_j$ in the post-obit style [432]:

1.

if s is the nix sequence, then $L(\mathbf{s})=0$ ;

ii.

if no LFSR generates s, and then $L(\mathbf{s})=\infty$ ;

3.

if at that place is at least one LFSR that generates s, then $L(\mathbf{southward})$ is the length of the shortest LFSR that generates s. Equivalently, $L(\mathbf{s})$ is the degree of the minimal polynomial of southward.

For our example of Figure two.1, nosotros can follow easily the previous algorithm and obtain that the linear complexity is $\mathrm{50}=3$ . Of course, our LFSR is atypical. The periodic sequence $1,1,1,0,\mathrm{i},0,0$ tin can be generated by a four-phase LFSR, where the stages $T_i$ satisfy $T_{3+i}=T_{2+i}+T_i$ $(i=0,1,2,\dots )$ with input $1,\mathrm{one},1$ . The feedback polynomial $1+\mathrm{ten}+x^{\mathrm{iii}}$ is the aforementioned.

If $s^{\mathrm{north}}$ is a finite binary sequence, so $L({\mathbf{southward}}^n)$ is the length of the shortest LFSR which has ${\mathbf{south}}^n$ equally its beginning n terms. The linear complexity satisfies the following backdrop [432, pp. 198–199].

Theorem 2.35

Let $\mathbf{s},\mathbf{t}$ be binary sequences. Then

1.

$0\le L({\mathrm{south}}^n)\le n$ , $n\ge 1$ .

2.

$L({\mathbf{s}}^{\mathrm{north}})=0$ if and only if ${\mathbf{southward}}^n$ is the all zilch sequence of length n.

3.

$L({\mathbf{s}}^n)=n$ if and only if ${\mathbf{due\; south}}^n=0,0,\dots ,0,1$ .

4.

If south is periodic of menstruation T, then $L(\mathbf{s})\le T$ .

v.

L satisfies a triangle-similar inequality, that is, $\mathrm{50}(\mathbf{southward}\oplus \mathbf{t})\le L(\mathbf{s})+L(\mathbf{t})$ , where $\mathbf{due\; south}\oplus \mathbf{t}$ is the bitwise xor of $\mathbf{s},\mathbf{t}$ .

half-dozen.

If the feedback polynomial $C(x)$ is primitive over ${\mathbb{F}}_2[x]$ , then each of the $2^n-1$ nonzero states of the associated nonsingular LFSR will produce an output of linear complexity northward.

vii.

If the feedback polynomial $C(\mathrm{10})$ has degree due north and it is irreducible over ${\mathbb{F}}_2[x]$ , with α being a root of $C(x)$ in ${\mathbb{F}}_{2^{\mathrm{north}}}$ , and then the period of the LFSR is equal to the society of α in ${\mathbb{F}}_{2^{\mathrm{north}}}$ . Consequently, the period of an LFSR with n stages always divides $2^{\mathrm{north}}-1$ .

The reader may consult [175,289,432] for more details on LFSRs.

Read full affiliate

URL:

https://www.sciencedirect.com/scientific discipline/article/pii/B978012811129100002X

Stream Ciphers and Number Theory

In North-Kingdom of the netherlands Mathematical Library, 2004

two.3.4 Sphere Complexity and Linear Cryptanalysis

Let x exist a finite sequence of length n over GF(q). The weight complication [137, 138] of the finite sequence is divers by

(2.fourteen) ${\text{WC}}_u\left(x\right)=\underset{\text{WH}\left(\text{y}\right)\text{=u}}{\text{min}}\text{L}\left(\mathrm{ten}+y\right),$

where WH(y) denotes the Hamming weight of y, i.e., the number of components of y that are different from zilch.

Consider now the space GF(q) ⁿ with Hamming distance d _H . Cogent S(x, u) = {y : d _H (x, y) = u}, by definition we have

${\text{WC}}_u\left(x\right)=\underset{y\in S\left(\mathrm{ten},u\right)}{\text{min}}\text{L}\left(y\right).$

This means that the weight complexity is the maximum lower bound of linear complexities of all the sequences of length n on the sphere surface Southward(x, u). The name of this kind of complexity comes from this geometrical pregnant.

Permit O(x, u) = {y : 0 <d _H (x, y) ≤ u} be the sphere with center x. The sphere complication [137, 138] is defined by

(2.15) ${\text{SC}}_u\left(x\right)=\underset{y\in \text{O}\left(x,u\right)}{\text{min}}\text{L}\left(y\right)=\underset{0<\upsilon \le u}{\min }{\text{WC}}_{\upsilon }\left(x\right).$

Similarly, let s ^∞ be a sequence of period N (not necessarily least menstruation) over GF(q). The weight and sphere complexity of periodic sequences with respect to N are defined respectively by

(two.16) ${\text{WC}}_u\left({\mathrm{southward}}^{\infty }\right)=\underset{\text{WH}\left(t^{\mathrm{North}}\right)=u\text{,per}\left(t^{\infty }\right)=N}{\text{min}}\text{50}\left(s^{\infty }+t^{\infty }\right)$

(ii.17) ${\text{SC}}_u\left({\mathrm{south}}^{\infty }\right)=\underset{0<\upsilon \le \text{u}}{\text{min}}{\text{WC}}_{\upsilon }\left({\mathrm{southward}}^{\infty }\right),$

where per(t ^∞) = N denotes that t ^∞ has period N.

These two complexities were introduced to measure the stability of the linear complexity function, in analogy to the derivative of functions in Euclidean spaces. The cryptographic background of these complexities is that some key streams with large linear complexity can exist approximated by some sequences with much lower linear complication [137, 138]. The sphere and weight complexity are based on the LFSR approximation model. In contrast to the linear complexity which is based on the shortest LFSR that produces a sequence, the sphere complexity SC _yard (due south ^∞) is based on the shortest LFSR that produces some other sequence with a probability of agreement no less than (ane − k/Northward), where Due north is a menses of the sequence s ^∞ with which the sphere complexity is concerned. The weight complexity WC _{one thousand} (due south ^∞) is based on the shortest LFSR that produces another sequence with a probability of understanding equal to (1 − yard/North).

To illustrate the difference between the linear complexity and sphere complexity, we consider the binary sequence of period North:

The linear complication of the sequence is Northward by definition since no LFSR of length less than N can produce information technology. However its sphere complication SC_one(s ^∞) = 1 by definition since there is an LFSR of length one that produces the all-zero sequence having the probability (one − one/N) of agreement with the sequence s ^∞.

These LFSR approximation model complexities are cryptographically important only if there is an efficient algorithm to find the LFSR for approximating the original generator. To run into the cryptographic importance of these complexities, we describe an attack on all synchronous condiment stream ciphers [123].

Suppose that a cryptanalyst has a number of consecutive ciphertext-plaintext pairs of a synchronous condiment stream aught which enable him to derive a piece of cardinal stream, say z ₀ z _i · · · z _n−i. Suppose likewise that he knows nothing else but the plaintext source code of the enemy's letters. What can he practice under these assumptions in order to decipher the enemy'due south ciphertext? The best the cryptanalyst can do may be the structure of a new generator which produces a sequence with a large probability of agreement with the original key stream.

To make things simple, nosotros assume that the key stream is binary. Under the assumption that the linear complexity of the enemy's key stream is very unstable, the cryptanalyst can try to construct an LFSR to approximate the original keystream generator according to the following procedure:

Pace 1

Use the Berlekamp-Massey algorithm to construct an LFSR whichproduces the sequence z ⁿ = z ₀ z ₁ · · · z _{due north−1}. Then use the constructed LFSR to decipher a large slice of ciphertext. If only ∈ percent (this constant can be flexible, say less than 15) of the deciphered ciphertext makes no sense, then accept the LFSR and stop; otherwise, go to Step ii.

Footstep 2

For i = 0 to n − 1, practise the post-obit: Change z _i into z _i ⊕ one. Apply the Berlekamp-Massey algorithm to the new sequence to construct an LFSR which produces the new sequence. So utilise the constructed LFSR to decipher a large piece of ciphertext. If merely ∈ percent (this abiding can be flexible, say less than 15) of the deciphered ciphertext makes no sense, so accept the LFSR and end; otherwise, repeat this step for i + 1 if i <n − one, and get to Footstep three if i = n − 1.

Pace 3

For a possible pair (i, j) with i <j and i, j ∈ (0, 1, …, n−1), change z _i into z _i ⊕ 1 and z _j into z _j ⊕ 1. Then use the Berlekamp-Massey algorithm to the new sequence to construct an LFSR which produces the new sequence. And then use the synthetic LFSR to decipher a large piece of ciphertext. If only ∈ percent (this constant tin exist flexible, say less than fifteen) of the deciphered ciphertext makes no sense, then have the LFSR and stop; otherwise, echo this step for the next pair (i, j) with i <j if there is a remaining pair, and print "fail" and cease if there is no pair remaining.

Since the complexity of Berlekamp-Massey algorithm for sequences of length north is O(north ²), the complexity of this set on is O(north ^four). Thus, if s ^∞ is a fundamental stream such that its linear complexity is very large (say, for example, two⁴⁰) and SC _k (southward ^∞) is small enough (say less than 1000 for example) for some very small k, then this assail must succeed. The basic idea of this attack is that, we expect that the keystream sequence tin can be expressed every bit

$z^{\infty }=u^{\infty }+{\upsilon }^{\infty }$

such that u ^∞ and u ^∞ are of period N, the WH(v ^N )/N is very small and the sequence u ^∞ has small-scale linear complexity. This can be done when the linear complexity of the key stream is very unstable. In this case, we expect that the known fundamental stream z ⁿ can be expressed as

$z^n=u^{\mathrm{north}}+{\upsilon }^n$

with WH(v ⁿ ) ≤ 2 if northward <2N/k. Furthermore, we may also utilise the regular decimation sequences of z ⁿ to supervene upon z ^northward , then derive the minimal polynomial of u ^{due north} from the decimated sequences. Thus, it follows that the designer of a synchronous additive stream zilch must ensure that for very small k's, the sphere complication SC _{one thousand} (s ^∞) is large enough. In other words, the designer of an additive synchronous stream aught should brand sure that his fundamental stream cannot be well approximated by a sequence with small linear complexity, since the above polynomial-time algorithm tin can be used to find an LFSR to judge the original keystream sequence if its linear complication is very unstable. This shows why sphere complexity is cryptographically important. For the purpose of measuring the linear complexity stability of sequences, fixed-complication distance and variable-complexity distance were introduced. The connection between these measures and some lower bounds on these measures for some sequences can be found in [138].

The linear complexity stability problem for sequences was also considered by Stamp and Martin [412] nether the proper name of k-error linear complication which is divers to be min{SC _grand (s), 50(s)} and is essentially the same every bit sphere complexity.

Note that the motivation behind the sphere complication is linear cryptanalysis on 2 kinds of stream ciphers introduced by Ding, Xiao and Shan in 1988 [137], see also [119, 138]. The bones idea of linear cryptanalysis for stream ciphers is to utilise a related linear organization to approximate the original highly nonlinear system, or in other words to utilize linear circuits to approximate nonlinear circuits. For details near the linear cryptanalysis of 2 kinds of stream ciphers and specific examples we refer to [138]. Nosotros note that the linear cryptanalysis for stream ciphers was done earlier than that for cake ciphers.

Read total chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0924650904800047

Examination-Oriented Attacks

Swarup Bhunia , Marker Tehranipoor , in Hardware Security, 2019

9.2.4 Dynamically Obfuscated Scan (DOS)

The authors in [31] propose a design and test methodology against scan-based attacks throughout the supply concatenation, which includes a dynamically obfuscated scan for protecting IP/ICs. By perturbing test patterns/responses, and protecting the obfuscation cardinal, the proposed architecture is proven to be robust against existing noninvasive browse-based attacks, and tin protect all scan data from attackers in foundry, assembly, and organization development, without compromising the testability.

An overview of the proposed secure browse in a SoC is shown in Fig. 9.3. The DOS architecture reads Control Vector from nonvolatile straight memory access (DMA) in secure zone, and provides protection to scan chains. The DOS architecture has capacity and flexibility to provide protection for IP owner, and IC integrator. According to Fig. 9.iii, IP owner tin either integrate 1 DOS into IP, as IP core Two, or share the primal DOS belonging to the customized logic, as IP core I.

Figure ix.3. Overview of an SoC protected by DOS compages.

nine.2.4.i DOS Compages

As illustrated in Fig. 9.4 , the DOS compages is composed of a linear feedback shift register (LFSR), a Shadow chain with XOR gates, and a Control Unit.

Effigy 9.4. Detailed architecture of the DOS.

LFSR: The LFSR is adopted to generate a λ-bit obfuscation key (λ is the length of scan bondage), which is used to scramble scan in/out vectors as shown in Fig. 9.four. The obfuscation central is protected through the AND gates of the Shadow chain. The LFSR is driven by the control unit, and changes its output only when the obfuscation key update is required. It should exist noted that for LFSR, a seed with all zeros is illegal when using an XOR feedback; the LFSR would remain in locked-up land and continue providing all goose egg obfuscation Key. Therefore, the scan chains cannot be obfuscated. To avert the above scenario, it is suggested that some of XOR gates in LFSR would exist replaced with XNOR gates.

Shadow chain and XOR gates: Equally shown in Fig. 9.4, the input of the Shadow concatenation is the λ-bit obfuscation central generated by the LFSR, whereas the outputs are $k[\lambda \times \alpha ]$ bit protected obfuscation keys, where α is the permutation rate (the percentage of bits permuted inside each DFT scan chain), and thou is the number of scan bondage [31]. The Shadow chain is designed for propagating the obfuscation key at the $i_{th}$ scan cell along the scan chain, when the $i_{th}$ scan clock comes. Therefore, the Shadow concatenation is able to – (i) protect the obfuscation central from being leaked through resetting attack, (ii) forbid any unscrambled information from being scanned out, and (three) foreclose adversaries from scanning in values intentionally, and at the same time, brand no touch on on structural and chain tests.

It tin exist seen that the Shadow concatenation is designed as a pour of λ flip-flops, which is driven by the scan clock gated past scan enable signal. As shown in Fig. nine.iv, the information input of its first flip-flop is continued to Vdd. The XOR gate inserted later on the $i_{th}$ scan prison cell of browse concatenation X is controlled by the output of the $i_{th}$ flip-flop of the Shadow chain through a blazon A AND gate. As shown in Fig. 9.4, the type A AND gates of DOS are the AND gates connecting the scan cells within Shadow chain, the obfuscation fundamental bits generated by the LFSR, and the XOR gates inserted into the browse chain, which really are used to gate the private obfuscation key $.25 by the scan cells of Shadow chain.

After reset, every bit the browse clock forces the flip-bomb along the Shadow chain to logic "1", one by one, only when the last flip-flop in the Shadow chain becomes logic "one" at the ${\lambda }_{th}$ scan clock, the scrambled response starts to evidence up at the browse output. At the same time, the Shadow chain's $i_{th}$ flip-bomb starts to obfuscate the $i_{th}$ flip-flop of Browse chain X at the $i_{th}$ scan clock, which prevents the assailant from scanning in whatsoever intended values. Therefore, if the assaulter keeps flushing the browse concatenation, an original or inverted scan in sequence shows up at the scan output after λ bits of zeros. Furthermore, equally the protected obfuscation key has settled downwards after the whole chain is scanned, the Shadow concatenation does not impact the DFT launching or capturing process, such as when applying stuck-at or transition delay faults. The scrambled test responses are then scanned out. The Shadow chain should exist synchronously reset with the LFSR at any reset effect. As all of the DFT scan chains are scanned synchronously, and the length of the scan concatenation is ordinarily short with on-chip compression, the architecture only needs a unmarried short Shadow chain, which has low expanse penalty. Furthermore, as the Shadow chain is plugged into the browse chains, it is not bypassable.

Control unit: The command unit, equally shown in Fig. ix.4, is designed to control retentiveness loading and LFSR activities. It is composed of a small northward-bit register, a n-bit pattern counter, and a control flip-flop. During organisation initialization, a control vector is loaded from the secure scan read-only nonvolatile DMA, which includes a λ-scrap seed for the LFSR, an n-bit value p (determining the obfuscation central update frequency), and the maximum obfuscation fundamental update count. The command unit of DOS generates the Mem_Load_En indicate. This signal allows the control vector of DOS to be loaded from DMA, one time the system resets. The control vector is determined by the IC designer. As a part of arrangement firmware, the control vector is stored into read only nonvolatile memory located in secure zone with DMA, which satisfies: 1) firsthand control vector accessing: the control vector is automatically loaded into DOS at powering upward, which can be guaranteed past hard coding the control vector accost in DMA; 2) limited readability: the control vector can just be read by DOS, which can exist satisfied by using the handshaking signal Mem_Load_En (in Fig. 9.four) generated past DOS, every bit an input of the DMA address accessing potency. Additionally, as shown in Fig. 9.four, during scan, Mem_Load_En as well ensures that the command vector can only be read after the reset event. Furthermore, the memory encryption technique such equally [45], which allows the control vector to be stored into the nonvolatile memory in an encrypted style, is recommended, just not required. When the pattern counter value reaches p, the obfuscation key is updated. Otherwise, the obfuscation fundamental is locked. As sometimes the set up of exam patterns cannot exist delivered at once, this feature offers the IP owner flexibility to dynamically add new patterns with updated obfuscation key.

9.2.iv.2 The Obfuscation Flow of DOS Architecture

Based on the iii major components discussed higher up, the obfuscation flow of the proposed pattern is summarized below. In Stride one, during organization initialization, a control vector is loaded into the LFSR and the control unit of measurement, which is composed of a seed for the LFSR and a vector to determine the obfuscation key update frequency. In Footstep 2, the obfuscation central is generated at the output of the LFSR, which is driven by the command unit. In Stride 3, during the first λ browse clocks after reset, the protected obfuscation key is generated bit by scrap based on the Shadow chain and the obfuscation central. In Step iv, at the ${\lambda }_{th}$ browse clock, the protected obfuscation key settles down. So, all the exam patterns and responses scrambles as a result of the protected obfuscation key.

Figure ix.5 shows the timing diagram of DOS architecture. It can be seen that the obfuscation primal is generated at the output of the LFSR in waveform (C), and is dynamically inverse every p design (p is configurable by the IP possessor), when the obfuscation key update is enabled and generated by the control unit of measurement (waveforms (C) and (F)). As presented before, subsequently reset, the protected obfuscation key for scan chain X, generated past the Shadow chain, is updated bit by bit with the browse clock, and settles down at the ${\lambda }_{th}$ scan clock (waveform (K)). During the flow of the first λ browse clocks, the scan out is locked to "0". Once the ${\lambda }_{th}$ browse clock comes, the scan out starts to output obfuscated responses (waveform (H)).

Figure ix.5. The timing diagrams for DOS compages.

Read total chapter

URL:

https://world wide web.sciencedirect.com/science/article/pii/B9780128124772000149

Simulation Techniques

Scott L. Miller , Donald Childers , in Probability and Random Processes (Second Edition), 2012

12.1.1 Binary Pseudorandom Number Generators

To beginning with, suppose we would like to simulate a sequence of independent identically distributed (IID) Bernoulli random variables, X ₁, Ten ₂, X ₃, …. I style to exercise this would be to grab a coin and offset flipping it and observe the sequence of heads and tails, which could then exist mapped to a sequence of 1s and 0 southward. One drawback to this arroyo is that it is very time consuming. If our application demanded a sequence of length 1 million, not many of us would have the patience to flip the coin that many times. Therefore, we seek to assign this task to a computer. So, to simulate an IID sequence of random variables, essentially we would like to create a reckoner program that will output a binary sequence with the desired statistical properties. For example, in improver to having the diverse $.25 in the sequence be statistically independent, nosotros might too desire 0 s and 1s to exist equally likely.

Consider the binary sequence generated by the linear feedback shift register (LFSR) structure illustrated in Figure 12.ane. In that figure, the square boxes stand for binary storage elements (i.due east., flip-flops) while the adder is modulo-two (i.e., an exclusive OR gate). Suppose the shift register is initially loaded with the sequence 1, i, 1, ane. It is not hard to testify that the shift annals will output the sequence

Figure 12.1. A four-phase, binary linear feedback shift register.

(12.1) $\mathrm{one},\mathrm{one},\mathrm{one},\mathrm{ane},0,0,0,1,0,0,\mathrm{i},\mathrm{ane},0,1,0,\dots .$

If the shift register were clocked longer, it would become apparent that the output sequence would be periodic with a menses of 15 bits. While periodicity is not a desirable belongings for a pseudorandom number generator, if nosotros are interested in generating short sequences (of length less than 15 bits), then the periodicity of this sequence generator would not come into play. If we are interested in generating longer sequences, we could construct a shift register with more than stages so that the period of the resulting sequence would be sufficiently long so that its periodicity would not exist of concern.

The sequence generated by our LFSR does possess several desirable properties. First, the number of 1s and 0 south is almost equal (viii 1s and seven 0 south is as close every bit nosotros can get to equally likely with a sequence of length fifteen). Second, the autocorrelation function of this sequence is well-nigh equal to that of a truly random binary IID sequence (once more, it is as close as nosotros can maybe become with a sequence of period fifteen; come across Practice 12.one). Practically speaking, the sequence output past this completely deterministic device does a pretty good job of mimicking the beliefs of an IID binary sequence. It as well has the advantage of being repeatable. That is, if we load the shift register with the aforementioned initial contents, we can always reproduce the verbal same sequence.

It should be noted that not all LFSRs will serve every bit skilful pseudorandom number generators. Consider for example the 4-stage LFSR in Figure 12.2. This shift register is only a slightly modified version of the ane in Figure 12.one, nevertheless when loaded with the sequence one, 1, ane, one, this shift register outputs a repeating sequence of all 1s (i.e., the period of the output sequence is ane). The merely deviation between the two shift registers is in the placement of the feedback tap connections. Conspicuously, the placement of these tap connections is crucial in creating a good pseudorandom sequence generator.

Effigy 12.2. Another four-stage, binary linear feedback shift register.

A general N-stage LFSR is shown in Figure 12.iii. The feedback tap gains, one thousand_i , i = 0, 1, 2, …, Due north, are each either 0 or 1. A 1 represents the presence of a tap connection, while a 0 represents the absence of a tap connexion. It is besides understood that g ₀ = thou_N = 1. That is, there must e'er be connections at the starting time and terminal position. A specific LFSR can then be described past the sequence of tap connections. For case, the four stage LFSR in Figure 12.1 can be described past the sequence of tap connections [k ₀, g _ane, g ₂, 1000 ₃, g ₄] = [i, 0, 1, 1, 1] It is as well common to further simplify this shorthand clarification of the LFSR by converting the binary sequence of tap connections to an octal number. For example, the sequence [i, 0, 0, ane, 1] becomes the octal number 23. Too, the LFSR in Figure 12.two is described by [thou ₀, g ₁, g ₂, g ₃, thou _iv] = [one, 0, ane, 1, one] → 27.

Effigy 12.three. A general Northward-phase, binary linear feedback shift register.

An N-phase LFSR must necessarily generate a periodic sequence of numbers. At any point in time, the N-bit contents of the shift register can have on only one of 2 ^N possibilities. Given any starting state, the LFSR could at best wheel through all possible states, but sooner or later must return to its initial state (or some other state it has already been in). At that point, the output will and so begin to repeat itself. As well, notation that if the LFSR e'er gets into the all nothing land, it will remain in that state and output a sequence of all 0 s from that betoken on. Therefore, to become the maximum period out of a LFSR, we would like the shift annals to bike through all possible non-zero states exactly once before returning to its initial country. This volition produce a periodic output sequence with period of two ^North − ane . Such a sequence is referred to as a maximal length linear feedback shift register (MLLFSR) sequence, or an m-sequence, for short.

To study the question of how to connect the feedback taps of an LFSR in order to produce an m-sequence requires a background in abstract algebra beyond the telescopic of this volume. Instead, we include a short listing in Table 12.one describing a few feedback connections, in the octal format described, which will produce g-sequences. This list is not exhaustive in that it does not list all possible feedback connections for a given shift register length that lead to m-sequences.

Table 12.1. LFSR feedback connections for chiliad-sequences

SR Length, N	Feedback Connections (in Octal Format)
two	vii
iii	13
4	23
5	45, 67, 75
6	103, 147, 155
vii	203, 211, 217, 235, 277, 313, 325, 345, 367
viii	435, 453, 537, 543, 545, 551, 703, 747

As mentioned, thou-sequences have several desirable backdrop in that they mimic those properties exhibited by truly random IID binary sequences. Some of the properties of m-sequences generated by an N-stage LFSR are summarized as follows:

•

m-sequences are periodic with a period of 2 ^N − 1.

•

In one period, an m-sequence contains 2 ^N/2 1s and 2 ^N/2 − 10 due south. Hence, 0 southward and 1s are almost equally likely.

•

The autocorrelation function of m-sequences is almost identical to that of an IID sequence.

•

Define a run of length n to be a sequence of either n consecutive 1s or n consecutive 0 south. An m-sequence volition take i run of length N, 1 run of length N − 1, two runs of length Northward−2, four runs of length N−3, eight runs of length N−iv, …, and 2 ^N−2 runs of length 1.

one thousand-sequences possess many other interesting backdrop that are non as relevant to their use as random number generators.

Example 12.1

Suppose we wish to construct an thousand-sequence of length 31. Since the period of an m-sequence is two ^N −1, nosotros will need an N =5 stage shift register to exercise the chore. From Tabular array 12.i, there are three different feedback connections listed, any of which will piece of work. Using the first entry in the table, the octal number 45 translates to the feedback tap connections (1, 0, 0, ane, 0, 1). This describes the LFSR shown in Effigy 12.4.

Figure 12.four. A five-stage LFSR with feedback tap connections specified by the octal number 45.

Assuming this LFSR is initially loaded with the sequence (1, 0, 0, 0, 0), the resulting k-sequence will be

(0 0 0 0 1 0 0 1 0 1 1 0 0 i one 1 1 ane 0 0 0 i ane 0 one ane 1 0 1 0 1).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123869814500151

Cryptography

Rebecca N. Wright , in Encyclopedia of Physical Scientific discipline and Technology (Third Edition), 2003

IV.B Pseudorandom Number Generators

A pseudorandom number generator is a office that takes a short random seed and outputs a longer bit sequence that "appears random." To be cryptographically secure, the output of a pseudorandom number generator should be computationally indistinguishable from a random string. In particular, given a short prefix of the sequence, it should be computationally infeasible to predict the rest of the sequence without knowing the seed. Many so-chosen random number generators, such as those based on linear feedback shift registers (LFSR) or linear congruences, are non cryptographically secure, every bit it is possible to predict the sequence from a brusk prefix of the sequence. Despite the fact that LFSRs are not secure, a large number of stream ciphers have been developed using them. Most of these have themselves since been shown to be insecure.

The secure Blum–Blum–Shub generator, developed by Lenore Blum, Manuel Blum, and Michael Shub in 1986, is based on the believed computational difficulty of distinguishing quadratic residues modulo northward from certain kinds of nonquadratic residues modulo n.

A cryptographically secure pseudorandom number generator tin can be used to make a stream cipher by using the seed as a fundamental and treating the generator output equally a long key for a pseudorandom 1-fourth dimension pad.

Read total affiliate

URL:

https://www.sciencedirect.com/science/article/pii/B0122274105008437

Spread-Spectrum Systems

Urbashi Mitra , in Encyclopedia of Physical Science and Technology (Tertiary Edition), 2003

III Spreading Sequences

In DS-CDMA, the waveform assigned to each user can exist viewed as existence a function of a spreading sequence and a pulse waveform. The spreading sequence, s, is drawn from a finite alphabet (eastward.g., $\left\{\frac{\pm 1}{\sqrt{\text{Due north}}}\right\}$ ) and modulated onto a pulse shape p(t) (e.g., a rectangular pulse shape or a raised cosine pulse shape). To provide a consequent definition of indicate-to-racket ratio per bit, the spreading waveforms are normalized ${\Vert {\text{south}}_{\text{one thousand}}\Vert }^{\mathrm{ii}}=1$ . The parameter N is the length of the spreading sequence and is also known as the processing gain. It is a measure of the bandwidth expansion offered by the spreading operation. The distinction of "short code" DS-CDMA indicates that we shall be focusing on systems where the aforementioned spreading sequence is used for each fleck transmitted. This is in contrast to the by and nowadays implementations of standardized DS-CDMA, where the spreading sequence is time-varying and has a flow that is equal to many symbol intervals. An example,

$\begin{array}{l}\text{s}=\frac{\mathrm{one}}{\sqrt{\text{North}}}\left[-1,-1,+1,-\mathrm{one},+\mathrm{ane},-\mathrm{ane},+\mathrm{one},+\mathrm{one}\right]\hfill \\ \text{p}\left(\text{t}\right)=\{\begin{array}{l}\mathrm{one}\text{t}\in \left[0,{\text{T}}_{\text{c}}\right)\hfill \\ 0\text{else}\hfill \end{array}.\hfill \end{array}$

The parameter T _c is called the chip elapsing and the symbol duration is thus T  = NT _c .

The spreading sequences are chosen to have desirable automobile-correlation and cantankerous-correlation properties (Sarwate and Pursley, 1980). Several key sets of spreading sequences are derived from maximal length shift register sequences, likewise known equally one thousand-sequences. The 1000 sequence is generated by a linear feedback shift register whose operation is governed past a primitive polynomial of caste yard,

$\text{p}\left(\text{ten}\right)=\mathrm{one}+{\text{p}}_1\text{x}+{\text{p}}_2{\text{10}}^2\cdots {\text{p}}_{\text{thousand}-1}{\text{x}}^{\text{m}-1}+{\text{p}}_{\text{m}}{\text{ten}}^{\text{m}},$

the coefficients are fatigued from {0, 1}. Such a organization, with properly called coefficients, volition yield a sequence of length N  =   2 _m −one. The desired polynomials are tabulated in a variety of texts (see, east.m., Sarwate and Pursley, 1980; Simon et al., 1985; Ziemer and Peterson, 1985). The resulting {0,1} sequence is mapped to a {1, −1} sequence and normalized. The cyclic autocorrelation function of the sequence is defined to be

$\rho (\tau )={\displaystyle \sum _{\text{i}=1}^{\text{Due north}}\underset{¯}{\text{s}}\left(\text{i}\right)\underset{¯}{\text{s}}\left(\left(\text{i}+\tau \right)\text{mod}\text{N}\right),}$

where $\underset{¯}{\text{southward}}$ (i) denotes the ith component of the vector sequence $\underset{¯}{\text{s}}$ and modern is the modulo operator. The generated grand-sequences have the post-obit backdrop:

1.

The number of negative elements exceeds the number of positive elements past i.

2.

The autocorrelation office is given past

$\rho (\tau )=\{\begin{array}{l}1\tau =\text{l}\text{N},\text{l}=0,\mathrm{ane},\dots \hfill \\ -\frac{1}{\text{North}}\text{else}\hfill \end{array}.$

A key disadvantage of grand-sequences in regards to commercial spread-spectrum systems is that the number of distinct grand-sequences of a certain length that can be generated is quite express. ⁱⁱⁱ Furthermore, pairs of thousand-sequences do not ever achieve the near desirable cross-correlation functions. Two sets of pseudo-noise sequences which do take skillful cantankerous- and machine-correlation functions are Gilt (1967) sequences and Kasami sequences (Kasami et al., 1968).

Aureate sequences are constructed by taking the sum of ${\underset{¯}{\text{s}}}_1$ with all cyclic shifts of ${\underset{¯}{\text{s}}}_2$ , where ${\underset{¯}{\text{south}}}_{\mathrm{one}}$ and ${\underset{¯}{\text{s}}}_{\mathrm{ii}}$ are two m-sequences selected such that their associated primitive polynomials have a key relationship (Gold, 1967; Stüber, 1996). The resulting gear up of sequences is of cardinality 2 ^g   +   1 and furthermore, it can be shown that the resultant auto- and cross-correlation functions are three valued, where those three values are quite pocket-size. Kasami sequences are synthetic in a like way to Gilded sequences; notwithstanding, the constituent sequences have flow 2 ^m   −   1 and $2^{\frac{\text{m}}{\mathrm{ii}}}-\mathrm{i}$ , respectively; the resultant spreading sequence cardinality is $2^{\frac{\text{one thousand}}{2}}$ . Kasami sequences also accept iii-valued auto- and cantankerous-correlation functions; nonetheless, these values are smaller in magnitude than those of Gold sequences.

Another set of sequences, which are not pseudo-racket sequences, and possess poor off-peak correlation values are the Walsh–Hadamard sequence sets. This set is worthy of mention due to its prominent part in second generation CDMA standards (Rappaport, 1996; Viterbi, 1995). These sequences occur in the spreading operations and in the modulation specified for these standards. The rows of the Hadamard matrix of dimension N found the desired sequences. The Hadamard matrices are determined using the following recursion:

$\begin{array}{l}{\text{H}}_{2\text{N}}=\left[\begin{array}{ll}{\text{H}}_{\text{N}}\hfill & {\text{H}}_{\text{N}}\hfill \\ {\text{H}}_{\text{N}}\hfill & -{\text{H}}_{\text{N}}\hfill \end{array}\right]\hfill \\ {\text{H}}_2=\left[\begin{array}{ll}+\mathrm{one}\hfill & +1\hfill \\ +1\hfill & -\mathrm{ane}\hfill \end{array}\right].\hfill \end{array}$

It is straightforward to testify that the rows of the Hadamard matrix are orthogonal. Thus, if used in a truly synchronized system, in the absence of frequency selective fading (propagation effects), Hadamard spreading sequences result in optimal receivers of low complexity (see Section V, which details several key receiver structures for CDMA systems). Withal, this is an arcadian scenario that rarely occurs in practise.

Read full chapter

URL:

https://www.sciencedirect.com/science/commodity/pii/B0122274105007225

Motivation

MinJia Shi , ... Patrick Sole , in Codes and Rings, 2017

1.2 Sequences

Assume that M users are speaking at the same fourth dimension on the aforementioned aqueduct. To recover who said what and when a digital signature of T digits is attributed to each user, and using phase modulation and complex correlators, the receiver can look to empathise something provided that

ane.

The autocorrelation of each sequence assumes the shape of a Dirac office;

2.

The cross-correlation between whatsoever pair of singled-out sequences is as flat as can be.

To construct such sequences which should exist as pseudo-random as possible, we use linear recurrences ¹ over finite rings which are mapped into the complex plane by using an additive group character. For case, if $R={\mathbb{F}}_{\mathrm{ii}}$ , and then for a sequence $n\mapsto c_n$ with values in R we attach a complex sequence ${\mathrm{ten}}_{\mathrm{north}}$ by the rule $x_n={(-\mathrm{ane})}^{c_n}$ . More than mostly, for $R={\mathbb{Z}}_m$ the rule would exist $x_n={\omega }^{c_{\mathrm{north}}}$ with ω being a primitive complex thousandth root of unity. Another deterministic criterion for randomness of a sequence is the linear complication: the length of the shortest Linear Feedback Shift Register (LFSR) that tin can generate it. For apply of that criterion in a cryptographic perspective, see [25,26].

1.2.one Periodic Correlation

To be more specific, let $x,y$ announce two sequences of period T with values in

${\mathrm{\Omega }}_q:=\{z\in \mathbb{C}|x^q=\mathrm{i}\},$

i.e., the ready of qth circuitous roots of unity. The periodic correlation at time lag ℓ, say, of sequences x and y is defined as the Hermitian scalar product over a menstruum of x and y shifted ℓ times, that is,

${\theta }_{x,y}(\ell ):=\sum _{j=0}^{T-1}{x}_j^{⁎}{y}_{j+\ell },$

the indices being understood modulo T. When $x=y$ , information technology is called autocorrelation, and cross-correlation when $\mathrm{10}\ne y$ . When $\ell =0$ plainly, the correlation ${\theta }_{x,x}(0)=T$ .

Let $\mathcal{M}$ announce a family unit of Chiliad such sequences. Allow ${\theta }_a$ announce the maximum modulus of correlation for all $x\in \mathcal{M}$ and $\ell \ne 0$ . Similarly, let ${\theta }_c$ denote the maximum modulus of the cantankerous-correlation over all $\mathrm{Thousand}(M-1)$ pairs $x,y\in \mathcal{Chiliad}$ and all time lags ℓ. The least upper spring on the cross-correlation ${\theta }_c$ and the nontrivial autocorrelation ${\theta }_a$ is usually denoted past

${\theta }_{\max }:=\max ({\theta }_a,{\theta }_c).$

Sidelnikov proved in 1971 that when M and T are both large and of the same social club of magnitude then for ±ane-valued sequences (i.east., $q=2$ ) nosotros take

${\theta }_{\max }⩾\sqrt{2T},$

while for all other sequences (i.e., $q>2$ ) we can only ascertain that

${\theta }_{\max }⩾\sqrt{T}.$

The first bound was proved to exist tight early in 1967 (for and then-chosen Aureate sequences) but the status of the 2nd bound remained unclear till 1988 [4,23]. The construction of Gold sequences relies on binary cyclic codes. Similarly, the construction of the sequences in [iv,23] builds on certain families of 4th cyclic codes to be described fully in §1.four. What if nosotros desire to obtain more sequences, say $G\asymp T^{\mathrm{two}}$ ? Nosotros need to approximate from to a higher place the modulus of character sums of the blazon

$\sum _{x\in T}{\omega }^{Tr(P(x))},$

where P is a polynomial and ω a circuitous root of unity of gild $p^g$ . In the special case when $m=1$ , that is, when the Galois ring is a Galois field, these are handled by Weil inequalities, or a special case thereof, known equally Carlitz–Uchiyama premises [19]. A nontrivial generalization of this type of jump to the p-adic situation at hand tin be found in [18]. The case of a hybrid sum (that is, containing both additive and multiplicative characters) is partially treated in [22].

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012813388000001X

Computational Complexity: A Quantitative Perspective

In Northward-The netherlands Mathematics Studies, 2004

5.11 Comments and bibliographical notes

Shannon [Sha48] made the suggestion that cryptosystems that are breakable may still exist considered satisfactory if the breaking procedure requires an unreasonable big amount of fourth dimension. The emergence of computational complexity theory in the early '70s have allowed more precise formulations of similar ideas. The concept of a one-manner function has been introduced past Diffie and Hellman [DH76]. Pseudo-random generators have a long history (meet Knuth [Knu73] ), all the same the classical algorithms (such equally linear feedback shift registers, linear congruential sequences, etc.) are not suitable for cryptography. The notion of computational indistinguishability has been invented past Goldwasser and Micali [GM84], and Yao [Yao82] has defined formally the notion of a pseudo-random generator based on the concept of computational altitude. The fact that weak one-way functions can be converted into strong 1-way functions has been stated by Yao [Yao82]. Our proof of Theorem 5.2.1 is based on Cai's lecture notes [Cai0l]. Blum and Micali [BM84] were the first to construct a pseudo-random generator based on an intractability assumption (namely, the intractability of the Discrete Log Trouble). Blum and Micali [BM84] have too introduced the concept of a hidden bit (or a difficult-core predicate) and have shown its essential role in the construction of a pseudo-random generator. Other pseudo-random generators have been built based on different hypothesis: Blum, Blum, and Shub [BBS87] have used the assumption that the quadratic residuosity problem is hard, and Alexi, Chor, Goldreich, and Schnorr [ACGS88] accept used the weaker assumption that integer factoring is hard. The fact that any one-manner role substantially has a hard-core predicate (run into Theorem 5.iii.9) has been established past Goldreich and Levin [GL89]. At that fourth dimension, the operation oflisting decoding of error-correcting codes was not properly conceptualized and the realization that one important footstep in Goldreich and Levin's proof amounts to the list decoding of the Hadamard code came much later (see Sudan [Sud00]). The method for stretching the extension of a pseudo-random generator (meet Theorem five.4.one) has been presented by Goldreich, Goldwasser, and Micali [GGM86]. The aforementioned paper contains the construction of a pseudo-random role using as a edifice block a length-doubling pseudo-random generator (Theorem v.5.1). Another construction of a pseudo-random function has been given past Naor and Reingold [NR99]. The fact that a one-way permutation can be converted into a pseudo-random generator has been shown by Yao [Yao82] using a more complicated method. The ultimate result in this line of research is that the being of a ane-way function is equivalent to the existence of a pseudo-random generator and has been demonstrated by Håstad, Impagliazzo, Levin and Luby [HILL99a].

Nisan and Wigderson [NW94] had observed that, in social club to derandomize BPP computations, information technology is enough to have pseudo-random generators that are secure against adversaries whose running time is divisional by a fixed polynomial in the length of the output of the pseudo-random generator and which can be calculated in fourth dimension that is polynomial in the same length. The same paper presents the structure of such a pseudo-random generator using as a building block an exponentially hard predicate (meet Theorem v.8.6). Subsequent papers have succeeded in relaxing the assumption regarding the hardness of the building block by showing that hardness can be amplified. Babai, Fortnow, Nisan, and Wigderson [BFNW93] have shown that a predicate that is worst-case difficult can be converted into a predicate having the property that no adversary circuit of exponential size (i.e., of size 2 ^cn , for some constant c > 0) can calculate the predicate on more than a fraction of (1 − one/poly(n)) of the inputs in Σ ⁿ . Impagliazzo [Imp95] has shown that the latter type of predicate tin can be converted into a abiding-charge per unit difficult predicate against adversary circuits of exponential size, and Impagliazzo and Wigderson [IW97] have shown how to transform a abiding-difficult predicate into an exponentially hard predicate against adversary circuits of exponential size, i.e., the kind of predicate that is needed in the Nisan-Wigderson construction. The last paper also presents Theorem v.9.ane, which shows that under a quite plausible hypothesis, P = BPP. The newspaper [BFNW93] utilizes the technique of polynomial encoding (see the proof of Theorem v.6.3) developed in a series of earlier papers ([Lip89], [BF90], [GLR⁺91], [GS92]). Our proof of Theorem 5.6.3 uses the method of polynomial encoding and the polynomial reconstruction algorithm (see Theorem 5.6.2) to push the hardness amplification from worst-case difficult functions against superpolynomial (exponential) size antagonist circuits to constant-rate hard functions against superpolynomial (exponential) size antagonist circuits. The polynomial reconstruction algorithm was discovered by Sudan [Sud97] and was inspired by an algorithm of Berlekamp and Welch [BW86]. Sudan's algorithm needs to factor bivariate polynomials over a finite field. Dissimilar algorithms for this trouble take been found by Kaltofen [Kal85], Lenstra [Len85], and Grigoriev [Gri84]. For a recent survey on the polynomial reconstruction trouble (more commonly knownas decoding or list decoding of polynomial error-correcting codes), we recommend the paper by Sudan [Sud01]. The proof of Theorem 5.6.12 that achieves hardness amplification from constant-rate hard functions to crypto-difficult functions for antagonist circuits of superpolynomial size is modeled afterward one of the proofs in the paper past Goldreich, Nisan, and Wigderson [GNW95]. This paper presents three proofs of the and so-called XOR Lemma stated by Yao [Yao82], which, roughly speaking, shows that the hardness of a office f can be amplified past taking the "direct product" of f, which is the role f on multiple independent inputs. As we have seen in this chapter this method works fine for amplifying the hardness of functions confronting adversary circuits of superpolynomial size. However, in the instance of antagonist circuits of exponential size, the simple "direct production" method does non piece of work considering the input length is stretched too much and more refined variants of the XOR lemma are needed in which the inputs of the multiple copies are non independent. Such variants of the XOR lemma have been presented in the paper [Imp95] and in the newspaper [IW97], achieving the hardness amplification mentioned to a higher place. The proof of Theorem v.6.12, (b), which nosotros accept skipped, can be institute in the latter paper. A different arroyo to hardness amplification, based on list-decoding of error correcting codes, has been undertaken by Sudan, Trevisan, and Vadhan [STV01], who have succeeded to convert directly a worst-case predicate into an exponentially hard predicate. For references on list decoding of error-correcting codes, the reader can consult the survey paper of Sudan [Sud00]. The most efficient currently-known structure of a pseudo-random generator using as a building block a hard predicate has been given by Umans [Uma02].

The written report of methods for repairing imperfect randomness has a long history. It starts probably with von Neumann's classical algorithm [vN51] for generating a sequence of unbiased $.25 from a source of of biased but independent and identically distributed bits. More and more general types of imperfect sources of randomness have been considered by Blum [Blu84], Santha and Vazirani [SV86], and Chor and Goldreich [CG88]. The full general model for weak sources of randomness based on the notionof min-entropy has been introduced by Zuckerman [Zuc90]. Extractors have been first defined by Nisan and Zuckerman [NZ96]. There are numerous constructions of extractors and the reader is advised to consult the survey papers of Nisan and Ta-Shma [NTS99] and Shaltiel [Sha02], which contain a comprehensive coverage of extractors and their applications. The observation that the construction of a pseudo-random generator from a hard predicate can exist used to build an extractor has been made by Trevisan [Tre01]. The reconstruction technique is at the origin of some of the best currently known constructionsof extractions.

Read total chapter

URL:

https://www.sciencedirect.com/science/commodity/pii/S0304020804800069

Source: https://www.sciencedirect.com/topics/mathematics/linear-feedback-shift-register

Posted by: fosterrismustriog.blogspot.com

Share this post