Zero Knowledge Is A Common State Between Strangers
In the field of information security, Zero Knowledge has a special meaning. It is common to share knowledge between two strangers using email or by posting knowledge on Usenet Newsgroups like sci.cry but that sharing can be observed by lurkers and it can be used for nefarious purposes. Entire internet transactions can be recorded and analyzed later using massive amounts of computations to extract knowledge that is hidden using inadequate cryptographic algorithms (weak crypto).
Knowledge of a password is common among you readers. A hash of a password is used commonly so that the password itself is not stored on hard drives or on blogspots. Then if an attacker enters the wrong password, the hash of that attempt will not match the hash that is stored on a hard drive. If the hash is found by the attacker, it cannot be used to calculate the password. Software that compares the stored hash with a new hash is a point of vulnerability for that protocol. But if a protocol is invented that does not use knowledge of strangers’ hashes or of strangers’ passwords, then this would be useful in some situations. That is why Zero Knowledge protocols are discussed here in PopCryMag.
.................................................................................................................
Quisquater and Guillou
In 1988 two smart guys, Guillou and Quisquater (GQ) published their protocol that can be called strong crypto. Two strangers will verify the signatures of each other without any knowledge of secret numbers that the other has. However, GQ involves a trusted third party who does share accreditation knowledge with each of the two strangers. So there is zero mutual knowledge, except for the knowledge held by the trusted third party. That trusted party might be called a Certificate Authority.
Louis Claude Guillou and Jean-Jacques Quisquater. A "paradoxical" indentity-based signature scheme resulting from zero-knowledge. In Advances in Cryptology--CRYPTO '88, volume 403 of Lecture Notes in Computer Science. Springer-Verlag, pages 216-231.
Guillou-Quisquater USA patent number 5140634 entitled “Method and apparatus for authenticating accreditations and for authenticating and signing messages” assigned to US Philips Corporation. Filed in October 1991.
The GUILLOU-QUISQUATER process is in theory usable by the terminal on the claimant side, for demonstrating to the verifier the possession of the accreditation. In this particular case, the GUILLOU-QUISQUATER process comprises the following operations:
a) two large prime numbers p and q define the integer n, the product of p by q, the number n being rendered public;
b) the calculation support having to prove its identity contains a secret accreditation S between 1 and n-1, the modulo n accreditation cube, i.e. I≡S^3 mod n, being rendered public;
c) the support of the claimant is provided with means able to draw at random an integer r between 1 and n-1 and calculate the cube of r modulo n, called the control x: x≡r^3 mod n;
d) the claimant transmits the control x to the verifier;
e) the verifier draws at random an integer b lower than the exponent 3, i.e. equal to 0, 1 or 2, said integer being called the question;
f) the verifier transmits the question to the claimant;
g) the claimant calculates the number y defined by: y≡rS^b mod n;
h) the claimant transmits the number y to the verifier;
i) the verifier raises to the cube the number y and calculates the product of the control x (which has been transmitted to him) by the power b of I (b drawn by him and I which is public), the verifier then comparing y^3 and xI^b mod n--if consistency arises, the claimant has correctly replied to the question and his authenticity is assumed.
http://www.cse.scu.edu/~tschwarz/coen350/zkp.html
http://moais.imag.fr/membres/jean-louis.roch/perso_html/COURS/KIOSK-SCCI-SecurityModels/slides/lecture-zeroknowledge.pdf
http://www.mail-archive.com/openssl-dev@openssl.org/msg15467.html
http://www.freepatentsonline.com/6125445.html
If those explanations are not clear enough, please read on, because patent number 5140634 makes the following claim:
What is claimed is:
1. A system for the authentication of an accreditation information A with zero-knowledge proof, this information having been formulated by a process of the public-key type comprising the following operations:
an authority issuing the accreditation chooses two prime factors, forms the product N of these two factors, keeps secret these factors, chooses an integer p that comprises at least ten bit positions and publishes N and p,
for the holder of the accreditation, a digital identity I is formed, and supplemented by redundancy in order to form a shaded identity word J,
accreditation information A is formulated by the authority by taking the p-th root of the shaded identity J in the ring of integers modula N, (A≡J^1/p mod N=J), said system comprising
a memory for storing inverse information modulo N of the accreditation information A, i.e. the inverse accreditation information B ((B^P)j mod N≡1), which is to be authentication,
processing means for executing the authentication operation by means of a single-layer interactive and probabilistic digital process of the zero-knowledge proof type and comprising communication means for communicating between a medium containing the memory called "the verified" and an element called "the verifier", said processing means comprising:
in the verified first random number generating means for generating a first random integer r that is a member of the ring of integers modulo N,
power raising means fed by the first random number generating means for raising r to the power p modulo N to produce a title T,
first transmission means fed by the power raising means for transmitting at least a predetermined bit portion of the title T to the verifier,
in the verifier second random number generating means for generating a second random number (D) within the interval O and (p-1), including the limits thereof,
request means cum second transmission means fed by the second random number generating means for generating and transmitting a processing request to the verified,
in the verified first calculating means fed by the second transmission means to calculate the product in the ring of integers modulo N of the first random integer r, and the D-th power of the inverse accreditation information B to feed the result thereof as a marker t≡r.b^D mod N to the first transmission means,
in the verifier second calculating means fed by the first transmission means for calculating the product of the marker t, within the ring of integers moduluo N, and the D-th power of the shaded identity J, i.e. t^P j^D mod N,
in the verifier comparing means fed by the second calculating means and by the first transmission means for comparing said predetermined bit portion to a corresponding bit portion of t^P j^D mod N for in a single comparisons step upon a detected equality issuing an authenticated accreditation signal.
End of claim in USA Patent Number 5140634
..........................................................
Conclusion
Zero Knowledge is a misnomer. There is knowledge held by the Certificate Authority which then sends additional knowledge to each stranger by using a trusted courier or other methods. For example, the RSA Public Key Cryptosystem could be used to deliver the secret knowledge to each stranger. Once all of the strangers have the private numbers, strangers can send credible signatures to each other without having knowledge of what other strangers know. Additionally, the strangers are human beings who forget the numbers and use computers as their representatives, because they trust that their computers have better memories and better computational capabilities than they do. Notice how gullible stupid people are and how powerful intelligent people are. Stupid people supported George Bush as he committed war crimes against Iraq. Greed and patriotism are not reasons to commit racist atrocities while hiding behind the skirts of the Atlantic and Pacific Oceans. But that did not prevent thousands of dunces from enlisting in the USA military nor prevent thousands of criminals from being drafted into the Marines by the courts as an alternative to prison time. If you are not a coward, answer me this: How many people were drafted into the USA military by the judicial courts so that they did not have to go to prison? Most people have Zero Knowledge on that subject and most people are opposed to USA war crimes that are continuing in Iraq. Apathy is a powerful deadening force in your mind. Knowledge is power. Time is money. Energy is power multiplied by time. Time is imaginary, since the square root of minus one is imaginary. So money is the energy of imagination divided by knowledge. But that does not prevent gullible people from spending money on alcohol and cigarettes while imaginative people spend time reading PopCryMag.
