While looking over Markus Jakobsson’s home page I read Cryptographic Randomized Response Techniques, Ambaninis, Jakobsson and Lipmaa. Among other results, they discuss a cryptographic implementation of Randomized Response Technique RRT, where a Respondant to an Inquiry will lie with probability p less than one-half. Statisically, the Inquirer can correct for this, but it allows the Respondant privacy, since the Respondant can deny the truth of her response.

In certain cases, a vote for instance, there would be an advantage for the Respondant to always answer truthfully, thus biasing the survey. The paper provides mechanisms by which the Respondant must respond with truthfully with probability exactly p.

The methods used, which I found of interest, are Pedersen commitments, Pinkas-Naor 1 of N OT, and NIPK. The OT will transfer exactly one of the commitments, but all commitments will have NIPK to guarentee they are correct commitments.

The actual Pinkas-Naor OT transfers exactly one among a set of N random numbers chosen by the sender. The clever idea is the chooser sends gⁱ, where i is the index of the choice, and the sender replies with g^r(i-j), where r is chosen randomly by the sender, and j is the index of the sent secret. There are additional numbers sent back and forth to further mask choices.

However, I wanted to learn more about the NIPK, and looked at two papers. Blum et. al have a journal and improved version of the original paper, Non-Interactive Zero Knowledge, Blum, De Santis, Micali, Persinao, 1991. It still eludes me that exact nature of NIZK. In particular, the difference between the simulator and the actual prover.

One thing that I noticed is that the Simulator only works on strings in the language. So it is already in a sense zero knowledge, since we know that the string is in the language before we begin the computation that so proves it. This might be a red-herring, however, because the issue isn’t member, rather than proof of membership. It might be entirely technical, in that we cannot speak of a proof of membership for a string not in the language!

The other, perhaps more important observation, is that the Simulator computes the proof and the trusted random string simultaneously, whereas the prover must take the trusted random string as given and respond to it with a proof. The paper An Efficient Non-Interact Statis Zero-Knowledge Proof System for Quasi-Safe Prime Products, Gennaro, Micciancio, Tal Rabin, give examples of NIZK where this is exactly the game played. The Prover must take an n-th root of the random value, whereas the Simulator simply takes the n-th power and claims the result was the given random string.

In this say, I sort of want to write that the Prover is a Random Variable w → (p,w), and the Simulator is a R.V. r →(p,w), with the same distribution. — Burt Rosenberg 2006/05/18 10:59

Read the paper DES, Triple-DES and AES by Biham and Knudsen, Cryptobytes V4N1. Resumes the work by Biham breaking CBC in the inside, among others, but provides reasons by CBC on the outside is not perfect: slower and matching ciphertext attack. Talked about the use of DEAL to increase block size, to counter this attack.

— Burt Rosenberg 2006/05/18 11:43

Square the relation sq+rp=1. Mod pq inner terms cancel, and outer terms in invariant to signs of s and r. So the four square roots of unity mod pq are (+/-)(sq+rq) and (+/-)(sq-rq).

— Burt Rosenberg 2006/05/18 11:43

Let Y be the 2^k roots of unity where p-1=2^kj, j odd. Let y in Y be a quadratic non-residue, and hence a generator of Y. Let S₀ by the stablized subgroup by repeated squarings of Fp. Let S_i be those elements no in S_i-1 but with squares in S_i-1. S_k is the set of quadratic non-residues. If x is in S_i it is said to have height i. The j-th power map maps Fp onto Y and preserves height.

Multiplying the image of any x under the j-th power map with any element of Y of equal height reduces the height (of the product). Repeating (having each time to figure out the height of the intermediate quantity) we arrive at the equation x^jy^r=1, where j is odd and r is even.

Multiply by x. A square root of x is (obviously) x^(j+1)/2y^r/2.

— Burt Rosenberg 2006/05/18 11:43

History of WEP cracks, starting with Wagner, leading to KoreK, including FMS like weak keys and chopchop, which really works on any single byte without chopping: http://www.netstumbler.org/showthread.php?t=12277

A description of some of the extensions to FMS: http://www.netstumbler.org/showpost.php?p=89036&postcount=11

I think there is also notations inside the code.