Algorithms in a Nutshell

Algorithms That Can Be Wrong, but with Diminishing Probability | 311

When All Else

Fails

Testing Inequality of Databases

Suppose a company keeps multiple distributed copies of a very large database to

permit efficient queries from many sites. Queries of the database are much more

frequent than updates, and updates are applied at every copy. Also, an adversary

with access to the updates may change them. One approach to assuring coher-

ence of the multiple copies in spite of potential adversaries is to send a copy of the

database from any site to every other site and test for inequality. But the size of

the database makes this transmission prohibitively expensive.

Another approach is to transmit a fingerprint of any copy to every other site and

then test whether the fingerprint at every other site is equal to the transmitted

fingerprint. More explicitly, we consider a database to be a (large) sequence of bits

(b 0 ,...bn-1). The fingerprint of (b 0 ,...bn-1)is(b 0 +b 1 *2^1 +b 2 *2^2 +......bn-1*2n-1)

modpfor some randomly chosen prime numberp. We only need to transmit on

the order of log (p) bits. If the transmitted fingerprint is different than the finger-

print of the local database, then one can say with certainty that the databases are

different. If the fingerprints are the same, however, one can’t be certain that the

corresponding databases are identical. But the probability that two different data-

bases have the same fingerprint is 1/p. In order to decrease the probability of

incoherent databases passing the fingerprint test, we can repeat the process for

several primes. Example 10-3 contains the pseudocode for the COHERENCETEST

algorithm.

The probability that different databases slip through this test is 1/(p 1 *p 2 *...*pk),

which can be made diminishingly small by increasing the number of primes.

Zero-Knowledge Proofs

Assume that Patti the Prover wants to convince Victor the Verifier of her identity,

but they are communicating over an insecure channel. They assume that Albert

the Analyst is listening and wants to be able to convince people that he is Patti. If

Patti and Victor know a secret password, “Rosebud,” and she identifies herself by

transmitting the password, then in the future Albert will be able to identify

himself as Patti to Victor. Patti wants a more secure protocol.

Example 10-3. Pseudocode for coherence test algorithm

Sub Fingerprint Generation

Generate a sequence of k primes p1, ..., pk

for each prime pk

transmit pk

transmit (b0 + b1*2 + b2*2^2 + b3*2^3 + ... bn-1*2^n-1) mod pk

Sub Coherence Test

for each prime pk and fingerprint fk

if (fk != (a0 + a1*2 + a2*2^2 + ... an-1*2^n-1) mod pk) then

return "database incoherent"

return "database coherent"

end sub

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use