Reverse the direction of the noisy_vole protocols (performance improvement)

[ladnir]

the silent vole protocols make use a noisy vole. We can reverse the direction of the protocol to save on communication and rounds.

Details:
lets see, we have log2 |G| = k, F = G^m and want to do a vole of size n. We currently have

1. km OTs, each requiring s bits of communication to generate (for softspoken s=64 or s=32, for base ot s=512, for silent s=1).
2. For each OT, we send a derandomization string of size kmn
3. Overall we will have km * (km n + s) bits of communication.

You are proposing to switch the direction:

1. nk OTs each with s comm.
2. For each OT, we send a derandomization string of size km.
3. Overall we will have kn * (km + s).

So for m=1,k=128, n=100 & softspoken s=32, the old way requires 128^2 *100 + 128^2 * 32=2,162,688 bits, the new way requires 128^2 *100 + 128 * 100 = 1,576,800. If n>128, then the new way is worse. Current LPN parameters has n=170 or so but you could argue thats too high, some say n=64 is fine or even less.

For m=4, k=32, n=100, the old way requires 128 * 128 * 100 + 128 * 32=1,642,496. The new way requires 32*100 (128 + 32)=512,000.

This actually has a second (larger?) benefit, the rounds complexity of vole goes down to 2.

Silent Sender         Silent Receiver
             base ot 1 
      ( pprf & c choice bits)
     <------------------------

              base ot 2,
            noisy vole msg
      ------------------------>

In the old way we had to do the pprf OT and c OT in different directions. This means the best you could do was 3 rounds (with base Ots)! Now we can even use OT extension to get 3 rounds and avoid doing a PK operation for each.