# Coding Theory and Cryptography

DOI link for Coding Theory and Cryptography

Coding Theory and Cryptography book

The Essentials, Second Edition

# Coding Theory and Cryptography

DOI link for Coding Theory and Cryptography

Coding Theory and Cryptography book

The Essentials, Second Edition

ByD.C. Hankerson, Gary Hoffman, D.A. Leonard, Charles C. Lindner, K.T. Phelps, C.A. Rodger, J.R. Wall

Edition 2nd Edition

First Published 2000

eBook Published 4 August 2000

Pub. location Boca Raton

Imprint CRC Press

Pages 368 pages

eBook ISBN 9780429180934

SubjectsMathematics & Statistics

Share

#### Get Citation

Hankerson, D., Hoffman, G., Leonard, D., Lindner, C., Phelps, K., Rodger, C., Wall, J. (2000). Coding Theory and Cryptography. Boca Raton: CRC Press, https://doi.org/10.1201/b16944

Containing data on number theory, encryption schemes, and cyclic codes, this highly successful textbook, proven by the authors in a popular two-quarter course, presents coding theory, construction, encoding, and decoding of specific code families in an "easy-to-use" manner appropriate for students with only a basic background in mathematics offerin

## TABLE OF CONTENTS

chapter 1|1 pages

#### Introduction to Coding Theory

1.1 Introduction of methods for efficient and accurate transfer of infor- of noise from compact disc recordings, the trans- of financial information across telephone lines, data transfer from one

chapter |1 pages

#### of the codew ords 110110, 110101, 000111, 100111, 101000 is most

of finding an efficient way of find- 0. 0 0. 1 = w = v of two binary words of length n results in a binary word of

chapter |2 pages

#### Exercises of the following words, and the distance be-

of facts concerning weight and distance. Here u, v, and

chapter |1 pages

#### of MLD

p2(1- L(lll) {110, 101,011, 111}, ¢p(lll, 110) + ¢p(lll, 101) + ¢p(lll, 011) + ¢p(lll, Ill)

Byp2(1- =p3+3p2(1-p)

chapter |3 pages

#### of weight 3, 111. The only error pattern not covered by Theorem

of weight d = 1 of weight d = 1. Exercises

chapter |2 pages

#### If dis

/2 = 1 + t, and if d is even, say d = 2t, then d(v,v+u)=l+Lt-1/2J =t,

Byw, v + u) = 2t + 1 -

chapter 2|1 pages

#### Linear Codes

2.1 Linear codes of coding theory when applied to codes in this class.

chapter |2 pages

#### Exercises

of each linear code in Exercise 2.1.1. Check answers with of a linear code is the weight of the nonzero code- of least weight. of Kn if and only if U is closed under addition. Therefore if and only if C is a subspace of Kn. Over the next few sections of subspaces to dramatically improve our techniques

Byav are in U for any scalar a. In particular, since the only scalars in K are 0

chapter |1 pages

#### of each of the following rules

if v · w setS of vectors in of all vectors orthogonal to S is

Bya(v · w) v = 11001 and w = 01101 are orthogonal in K vis orthogonal to the setS if v · w = 0 for all w in S; that

chapter |1 pages

#### ... , Vk} of vectors is linearly dependent if there are scalars

If this question forces all the scalars a1, a2, Example 2.3.1 We testS= {1001, 1101, 1011} for linear independence. Let a,

chapter |4 pages

#### of the other words in S:

of the of the given set S. In the present example, this set is It is always true that any set

ByS is found to be a linearly dependent set. Note that S of vectors containing the zero

chapter |1 pages

#### of the leading 1s in the rows above. If

of matrices A and B: (AT) T = A and 2.5 Bases for C = {S} and C.l

chapter |1 pages

#### of G to form G' = [h, X]. Form a matrix H' as follows:

of the permutation applied to the columns of G to the rows of H'toform H.

ByS of

chapter |1 pages

#### H' and finally rearrange the rows of H into their natural

00001 7 00001 00010 10000 00100 01000 00001 00100 00010 00010 00001 9 00001 10 00001 of H form a basis for Cj_. of Algorithm2.5.7, explain why it is expected that G H of the following sets S, use Algorithm 2.5.7 to produce a basis B

ByH'= =

chapter |2 pages

#### of a matrix over K is the number of of the matrix. The dimension k of the code C is the

of C, as a subspace of Kn. If of

chapter |4 pages

#### of G), then v

of the words in a

ByuG for some u in Kk. Moreover, if G of length k. Thus C is the set of all words u G, u in K k. Moreover,

chapter |6 pages

#### If Cis

of length n, we can always obtain a new block code C' of length n by choosing a particular permutation of the n digits and then consis- C' is C' are not linear.)

ByAny linear code C is equivalent to a linear code C' having a gen-

chapter 2|2 pages

#### 11 MLD for linear codes

of our goals is to design codes which permit easy and rapid decoding of a of the of Theorem 2.10.3. of small weight are the most likely to occur, here is how of least weight in the coset C

Byw are in the same coset of C by

chapter |5 pages

#### of a particular coset, we can choose any word w in

of Example 2.10.5 (where of the first seven cosets we leader-the top word is the only word of least weight in of a word is 2, and that coset

chapter 3|3 pages

#### Chapter 3

3.1 Some bounds for codes of determining how many words a linear of given length n and distanced can have. This problem is far from solved in of n and d. We can, however, of a code with these given parameters.

ByIf if

chapter |1 pages

#### if akxn generator matrix has k linearly dependent columns

of length r to form the rows of d - 15-6 of length 9 with the property that any 4 of these

chapter |3 pages

#### Lett=

of length n is C = Kn. Kn is a perfect code. G)=(n:1)' (;)=(n:2), G)= (n:t)

Byn-i (n-i)!(n-(n-i))!

chapter |2 pages

#### of the fact that B= I and

of the parity check matrices into the algorithm, only of B. Ifwt(s):S3thenu=[s,O].

Byw + u. ei is the word of length 12 with a 1 in the ith position and s = w H.

chapter |2 pages

#### of odd weight. Show that wi is within distance 3 of a

of codes which includes of length 2m will be denoted by RM(r, m), 0 r m. We of these codes: ... 0, 11 ... 1}, RM(m,m) = K -1)}, 0 < r < =[G(m-1,m)J

Byr = 0 define

chapter |1 pages

#### of G(1, m -

of G(r,m ,m)= [G(r-1,m-1) G(r-1,m-1)] of G(r, m) and thus RM(r of RM(r,m). distanced= 2m-r for RM(r, m), using induction on r. I RM(r, m -1), -1, -1)} (7).

By-2,m -1)

chapter |1 pages

#### If = = c)> +

1 = 10101010 is the nearest codeword. Thus we have to examine at most half of the codewords in RM ( 1, m). Exercises

ByhxH=

chapter |1 pages

#### of the construction of RM( 1, m) codes suggests that there

of the largest component (in absolute value) of jth component of is positive, the presumed message is (1, v(j)), and if it

Byv(j) Km be the binary representation of j (low order digits first). Then if v(j)).

chapter |1 pages

#### G(l, 3) be the generator matrix for RM(l, 3) (see

-1, 1). Compute: 0,2,2,

ByWI= wHj = (0,2,0,2,0,2,2,0) w2Hl = (2, 6, Hj, Hff, Hj). The largest component of w3 is 6 occurring fori= 2, 3, 4.

chapter 4|2 pages

#### Cyclic Linear Codes

4.1 Polynomials and words in terms of polynomials. For + + ·· · +

Byofd egree n over K is a polynomial ao ... , are elements of K. The set of all polynomials over K is

chapter |1 pages

#### h(x) is divided into

if n = 7,

By+x+x+x f(x) +x h(x) = 1 f(x) f(x) h(x) f(x) +an-IXn-I of degree at most ... an-I of length n in Kn. +x+x +x 1+x+x

chapter 4|2 pages

#### l.ll(a), the reader computed the remainder r(x) when f(x) = +x+x +x +x

of the divisor h(x). = p(x)

Byh(x) = 1 r(x) = x r(x) is unique. Also r(x) has degree less than the f(x) modulo h(x) is r(x) if r(x) is the remainder when f(x) is r(x) = f(x) mod h(x). Furthermore, we say that p(x) are equivalent modulo h (x) if and only if they have r(x) p(x) mod h(x). f(x) h(x) = 1 +xand f(x) = 1 +x+x+xll. Then dividing f(x) by h(x) gives a remainder of r(x) r(x)

chapter 4|1 pages

#### 2 Introduction to cyclic codes

of a class of codes, called cyclic codes. Eventually we of cyclic codes to construct a generating matrix

chapter |1 pages

#### n(v) = 1010 and n

of the linear cyclic It is worth noting ... , n - if c(x) ({v(x),xv(x), ... ,xn-lv(x)}) (reducing each product mod

Byv must contain S as well, +a1xv(x) +an-IXn-lv(x)) mod 1 +xn

chapter |2 pages

#### = +x +x

= +x+x= +x+x+x

By+x+x(mod 1 +x =x+x+x +x(mod 1+x of cyclic shifts. +xn) is a codeword in C.

chapter |1 pages

#### f(x)

+x)(1 +x3) +q(x)(l + if and only if it divides 1 + xn. Hence by Theorem 4.2.13 g(x) is of length n if and only if g (x) divides 1 + xn. D

By+x +x+x +x+x+x+x)(1 +x +x +x+x+x+x +x +x+x h(x)g(x)). h(x)g(x) (mod 1 +xn) = h(x)g(x)

chapter |2 pages

#### = 2' + = +

Ifn = 2s, then (1 +xs)= 1 +xs +xs 2' s, where s is odd and let 1

By+xs = 1 +xs. We then proceed

chapter |1 pages

#### g(x) be the generator of a cyclic code of length nand let g(x)h(x)

of length 9, we simply find all idempo-

By+xn (n is odd). Then gcd(h(x),g(x)) = 1 and by the Euclidean Algorithm t(x)g(x) +s(x)h(x). t(x)g(x) gives, t(x)g(x) t(x)s(x)(l +xn) t(x)g(x) = (t(x)g(x))mod 1 +xn. +xn). D

chapter 4|2 pages

#### 5 Dual cyclic codes

of the dual code. It is a simple matter to see that the dual of a cyclic code is cyclic. This follows if a · b = 0 then (a) · :rr(b) = 0 where is the cyclic soC= ... of the dual we need to relate the product of polynomials of vectors.

By... , (v) }} = C xkh(x-

chapter 5|3 pages

#### BCH Codes

5.1 Finite fields

Byf(x) are always divisors of f(x) but these are trivial. Any other

chapter 6|1 pages

#### Reed-Solomon Codes

6.1 Codes over GF(2r) of the most practical codes known, namely the Reed-Solomon

chapter |2 pages

#### CnKn.

of 1 +xn and xc(x). In fact, it is not hard to show that if g(x) generates lengthY- of the binary of roots being the smallest if a is a root of g(x) then a R, and of length n = 2r -

chapter |1 pages

#### Lemma 6.2.1 Let oq, a2, ... at be non-zero elements ofGF(2r). Then a}=:l

I:::Dg(a; If a; = a i for some i

By+aj). f. j then two rows of the matrix are identical, so

chapter i|2 pages

#### 8 -of g (x), and thus the columns of

of 8 -of this matrix is zero, as can be of any 8 - of order n = 2r -1 h h-1:::; n of 8 -of the matrix is zero and so of the Hare linearly independent of this theorem applies to any cyclic binary linear code of

By... among its roots.

chapter |3 pages

#### if g (x) is the generator polynomial of C, then C (s) is the of polynomials c(x) = k-

= 2r-

chapter |2 pages

#### form+ 1jm + 2t.

= of of a A (x) = + + · · · + of g(x )). = = + + + + 1+ 0 + = = = + + + + = = = + + + f38+0+ = = = + + + =

By... , ... , ae.

chapter |1 pages

#### LetS be the set of nth roots of unity in GF(2r). The function

if = (p(l), p({J), ... , p({Jn-I)) ... , p({Jn-I), p(l)) is also in C. But, note of degree::; k -land p'(x) = p({Jx) C. But (p' (1), p' ({J), ... , p' ({Jn-I)) = (p({J), p({J2), ... , p({Jn-I ), p(l)). 0

chapter |2 pages

#### of values (vo, v1, ... , Vn-1) we can recover the coef-

= +x) of unity. ... , of xi is zero in C(x) and thus C(x) has degree of constructing a RS(2r, 8)

By+x), where is a primitive fori = <n-8+1.

chapter |1 pages

#### of e(x) is E(x) = .L

of Example 6.4.12 we would of w({Jk), k ... , 6 to obtain the most likely message directly. That is, find the transform of

ByE(x) = 1

chapter |6 pages

#### +x +x

of the polynomial G(x) given the values vg. of the error locator polynomial a(x). Let s(x) = 1 + sm+iX + Sm+2x+ · · · + = +r(x) LDi/2J and deg(r; (x)) Di)/2J. Moreover is a of Pi-! (x) and some specific previous polynomial = +Pi,

By-!X + a-2x+ · · · + aoxthat is, aR(x) is the "reverse" s of +... ,x +qi,ix + · · · +qi,2t-i-iX -i-i = t+i-i Pi (x)

chapter |1 pages

#### Let C be an RS(Y, 8) which is used to transmit messages and let

of erasure locations and let A be the set of error locations; of error locations which are not erasure locations. Define f1 +x)

chapter |1 pages

#### of Algorithm 6.5.1, except that i is now restricted to 1

of course (6.7) is now a system of C' to transmit messages. Then

Bya(x) = aB(x)aA-B(x). ... , can be found using step 5 of

chapter |1 pages

#### +x, so (x) = +x)(f3+x)({3+x) and the error magni-

if at most 8 - of c' as the = x) x)

ByC' with C an RS(2r, 8) code, we noted that C' u causes erasures and e error which are not erasures. w' then the reader should be critical of the answer as we have no

chapter |1 pages

#### of burst error patterns, we take as coset representatives the error

if all the words of burst length at most £ are in different co sets of if C is t error-correcting and if all error

chapter |2 pages

#### Exercises

of two error patterns with bursts q and of which has length at most £. Then show that of length of length at most £, then £ n -

By=xi H, if +e(x) is the received word, then it was shown that w ++ w(x) has wH = s ++ s(x) = w(x) mod g(x). There are two important facts that

chapter 101101110001000|2 pages

#### (b) 001101100010101

of length 15. Decode the following received words that were 010101000010010 (b) 011010010010100 001101000000100 (d) 000100010100101 0000000 11111001. of length at most r (t - cis the closest codeword inC tow. D of errors, and in space communications by of errors in the transmissions of electromagnetic waves. Under such circumstances, as-

Byc+e,

chapter |4 pages

#### of interleaving to depths on the burst error correcting capa-

... , i of errors of length at most s£ during transmission will produce a of length at most £ in c, so c will be decoded correctly, provid-

chapter 7|2 pages

#### 3 Application to compact discs

of music on compact discs has taken the music-loving world by ... , t of the array in Table 7.2 contains the bytes ,t, cz, of length 28 over GF(2that then are encoded using C= C(223), the

chapter |1 pages

#### of length 588 on the compact disc, all bursts of length (15 x 588)

if you prefer, all bursts affecting of track length on the compact disc. of the encoding

chapter 8|1 pages

#### Convolutional Codes

8.1 Shift registers and polynomials of n registers (or delay elements) and of the data contained in the

chapter |1 pages

#### of the registers and outputs are summarized in the follow-

of the contents of register X; at time t. of these devices can be described in terms of polynomials. If go, g1, ... , gs-1 are the coefficients of the s-stage shift register then g(x) of the shift register. For instance g(x) = 1

Bygs-!Xs-1 (t) where cis the output at timet =go+ g1x gs-!Xn-l is the polynomial corresponding to this shift register; this polyno-

chapter |4 pages

#### = Xo+X1 +X3

-1 0 0 of c(x) correspond to the output sequence of the device. of degree of information polynomials a (x). Exercises

By+(a!+ ao)x + (a2 + a1)x

chapter |1 pages

#### of weight 2 < 3

l)/2J is not corrected. However w ... if we wait "forever." of a walk to be the number of directed edges in the walk of weight at most e are to be corrected then the time r (e) that we must r(e) from of convolutional codes, there is no loss of

chapter 8|1 pages

#### Convolutional Codes secutive steps occurs during transmission, then the exhaustive decoding algorithm using the window size r(e) will decode the received word correctly.

of C 1) . = e = e = = of r(l) of length 7 immediately leaving the zero state have weight

chapter 8|2 pages

#### 4 Truncated Viterbi decoding

of length r at each tick, compared to calculating and storing of these two of message digits, rather than a sequence of states or a sequence of outputs on directed edges. Once t r, a message digit

chapter |1 pages

#### of Example 8.4.2 and let w = 11 00

of length k and where du is the distance

Byt=5 t=6 ... u s in the state diagram.

chapter |1 pages

#### If d(sk. ... , Sm-k. t 1) ... -1) +dv j.

of s to it. of u, then we could form W(s; t) by choosing any such u and proceeding as r, let S(t) = I d(s;t) d(s';t) for all states s'}. Decode the

By... , Sm-k. t ... , Sm-k. ... , Sm-k. Fort

chapter |2 pages

#### of a least weight path from s to s' in the state diagram. Suppose that

s') = w(OOO, s') for all of the name e-ready. However, clearly this result is of error-free transmission following a burst of errors. To obtain a result

Bys' i= 000 from the state diagram:

chapter |1 pages

#### 1)}). Therefored(C) = d(OO ... 0; t). Similarly, once

... 0; 100 ... 0), if s ... , Sm-1, 0; s), ... ,Sm-11; t +wt(sl, ... ,Sm-1, 1; s)}. If ... = ... sand if d(s'; t -1)::::; 2e for some states' then r(e) = t. If =

ByFort > 1 and for each states =so, ... , define

chapter |1 pages

#### = = =

of Algorithm 8.4.11). L(d(C)- l)/2J, we consider e r(1) = of If e r(2) = 7 (by Step 4 of Algorithm 8.4.12). Exercises

chapter 9|2 pages

#### Reed-Muller and Preparata Codes

9.1 Reed-Muller codes (7), and d of these codes; one that is better suited to decoding.

By=2m, k

chapter 1111111111111111|3 pages

#### 1111111111111111

1100000011000000 1010000010100000 1000100010001000 1100000000000000 1010000000000000 1000100000000000 fori> Ill, = If fori> of G4,4 formed by the first (6) = + (j) = + (j) [email protected] = +

By/J(uj) < !J(uJ) and /J(u;) = /J(u;) !J(u;)

chapter |1 pages

#### of weight d,

lVI. of Definition 9.3.3, dis even so we only need to show that d 2, d 4 and of weight 6. of Lemma 9.3.8 we can assume that U

BylUI=

chapter |1 pages

#### of H in 9.1 can be zero. In fact, since g (x) generates a cyclic code, it follows

andA-

chapter 10|1 pages

#### Classical Cryptography

of adversaries. of confidentiality or privacy-maintaining secrecy in com-

chapter |2 pages

#### of the one-time pad, DES was designed so that it would be "computationally

of cryptographic tools or prim- of strings of symbols from the alpha- if 5l = {0, then messages consist of strings of Os and

chapter |3 pages

#### of the cipher should rest with the keys alone; that

of computations and power consumption, for ex-

chapter |1 pages

#### sells sea shells the seashore

of ciphertext which of plaintext-although these tend to be less of a "true" match, the key length di- of accidental matches means that

chapter |1 pages

#### of which are

I (27, 229) of the of the key; e.g., for the candidate keylength = 2, the frequencies are 55 55 54 4 3 2 2 2 I 0 0 ... 12 10 10 ... 12 8 8 7

chapter |3 pages

#### of the same length, bitwise addition modulo

If of 1/2 (e.g., independent tosses of a fair coin) and are

chapter |3 pages

#### of rounds in this fashion is attractive, as it offers the possibility of

jth bit of k(m7) is 1. Chosen-plaintext attack on NDS if we can

chapter |5 pages

#### Exercises 10.3.1 Given that c = (mr+ mr) = ( 1111, 0100) is an output of the cipher in the

of binary digits; 10.3.2 The Data Encryption Standard

chapter |4 pages

#### of an entry from /etc/passwd can mount a known-plaintext attack,

of blocks which of 2DES of pairs

chapter |2 pages

#### of the input size are often written using the follow-

lf(n)l :S clg(n)l for all n 2: no. For example, f(n) = = 0(1) of k-bit binary numbers,

Byf(n) = 0(2n) does f(n) = O(n

chapter |1 pages

#### If b)=

of integers in the interval [ 1, n] which are relatively prime to n is denoted ¢(n), known as the Euler phi function. For example, ¢(6) = 2 and ¢(pi)= ifnI a If a= + a=

Bybare said to be relatively prime. For n 1, the ¢(ab) = ¢(a)¢(b) if (a, b)= in particular, ¢(pq) = (p -1)(q f. q. (a= a (mod n)), symmetric (if a= =a a= = a=

chapter |4 pages

#### = I =

of invertible elements of Zn forms a group Zh = { 5, 7, ... , p -1} if pis panda 1¢ (n) for a If = = ¢(n), then a is said

Byap-l

chapter |1 pages

#### of the theorem. The third fol-

of this corollary shows that there cannot be more than two solu- of a is ±1 (mod p), and only the congru- of a. 0

chapter |2 pages

#### of the Legendre symbol can be used to calculate ( £) more effi-

of the Legendre symbol. of the Legendre symbol by of the Jacobi symbol Let m, n 3 be odd integers, and let a, (mod8), ±3 (mod 8). ( 1) (2) (2) 3 (- 1) 3 (-l)-2---r -(-1)--r =52 (mod 55), illustrating that

Byn=3 (mod4).

chapter |1 pages

#### Let n be an odd composite integer and Jet a be an Euler

of non-witnesses in f -1, of n, and let b be a quadratic nonresidue modulo p. By the Chinese

ByLet n be an odd composite integer. Then there exists an Euler (njp)p njp p njp p +nfp)P (f)(njp)i

chapter |1 pages

#### if none are found, concludes that n is probably prime. The number

If if -1

Byj,O:Sj<s. j, 0 j < s, then a is called a strong witness for n.

chapter |3 pages

#### If f.

of all a of an integer n. of bit operations) of your test? of the results provided by this primality test.

chapter |1 pages

#### ... , p

of the first t if b factors over B; such setS is of primes appearing. Note of the desired form. of requiring more relations. For a given t, one strategy to of such a

ByLiESe; is the zero vector. The corresponding

chapter |4 pages

#### pIn). Hence, the factor base need only contain those primes p for which

Example 11.4.2 The value n (!!) = 1). The first few z for which q(z) factors over the factor base are listed

Byp:::; 19 such

chapter 11|1 pages

#### 5.2 Index calculus of the

of k for which ak mod p factors over Example 11.5.2 The method is illustrated for p of the remaining two of B, we calculate ak mod p for random k, seeking at least two values If =

ByPI+···+ et loga

chapter |2 pages

#### If k =

(p-1) of logarithms of elements in the factor base is expensive, of elements of B of a larger system of congruences to be solved. of 50-100 decimal digits. As an example, LaMacchia of logs modulo a certain

chapter 12|3 pages

#### Public-key Cryptography

of encryption and decryption capabilities. To be slightly

Bykin a public-key scheme is written as a key-pair k

chapter |4 pages

#### It is not known if cryptographic hash functions exist (since 1 and 2 imply that of candidates used for

if the hash value can be protected by some mecha-

Bym' giving collisions can be found, then Alice can cheat by signing m m'. A variation on this occurs if an adversary

chapter |4 pages

#### if the prescribed structure

if p ls in its binary representation to maintain efficiency) is

chapter |2 pages

#### of black-box cryptography is examined in CRYPTO '96

of [102] left a few details to the reader. How does the attacker

Bye, d). The process is contaminated using an attacker's key (n', e'), attempting

chapter |1 pages

#### A difficulty in Rabin decryption is that the correct plaintext must be identified

that(*) = -1. dis

Bym mod n. The triple (c = m6 mod n,b1,b2 =

chapter |1 pages

#### l = -1. =

if (c , p) of ±c is a If = of If [-a, of type 2. Show that y is type 1 iff ( = 1; hence pis delivered. of the private key a allows recovery of m, since a-ak can be computed

By[-a, -b], [-a, b], and -b], where Qp and bE a, 1 a

chapter |1 pages

#### of ax and (aaY(ak)s agree (see Exercise 12.4.3 concerning the

of at of concern in applications such as smartcards. of the

By(aay (akY holds. Choose integers j, k ai (aa)k mod p, -rk-(p-

chapter |1 pages

#### + ar

if the condition of the verification of (r,s) on m. (Show clearly that the of the private key a.) If of If f. = -1 of k?)

By)k-mod Verification accepts (r, s) as a valid signa- a= of Zh, a= m' can be forged provided a valid f. Show that has a of

chapter |1 pages

#### "v is indeed a quadratic nonresidue" has been revealed to the

if each is a quadratic residue, and gives the = if = if bi = for every i; if so,. B accepts the proof (that v is a If if

chapter |2 pages

#### r is independent of s, and

of a successful prediction is only 1/2 for each of a transcript from a valid protocol session. 12.5.3 Coin-tossing and mental poker

chapter |2 pages

#### of securely delivering a is required. Young and Yung describe a SETUP

= -1). -s2/(rf p)) (p-1).

By(m;)- ar;)kj r,;\H(m2) a = 2. Verify

chapter |3 pages

#### Appendix A The Euclidean Algorithm

of two polynomials f(x) = q1(x)d(x) and gcd(f(x), g(x)) A.l We find the greatest common divisor of f(x) and g(x)) into irreducible polynomials

Byf (x), (x) K [ x] is K[x] of largest degree such that f (x) and (x) assuming

chapter |1 pages

#### ism; = DESf: c;-J. Only m and m J+!

It is not known if the complementation property can be used to improve of an If a, It follows that if is cyclic, then there are ¢(¢(n)) generators. In this exercise, there are ¢(¢(11)) = ¢(10) = 4 generators, fori {1,3,7,9}. :s r < ord(a).

chapter |1 pages

#### = LJ nj = = + =

-1, -1. z -1 -120 ·3·5 = ai = = = A= 2i Awith odd, then we may assume without loss of generality ¢(p). Consider an element a with order ¢(p) as an element of /2 as an element of

Bya=z+m

chapter |2 pages

#### A= ord(a)A.' and x = 2i ord(a)x' for some 0 and odd and x'.

= f(M, nand d.

Byh(kxy) -Xj. -x2,x1 -x3) 2pq or 4pq has been recovered. Since n = (2p

chapter |3 pages

#### of Lecture Notes in Computer Science, pages 454-464. Springer-Verlag, of Encryption Re-

of Lecture Notes in Computer Science. Springer-Verlag, 1997.