Robust PPH Implementation - BLV19 Construction 2

[sambux1]

We need to implement a robust PPH. The best starting point is construction 2 of the BLV19 paper, since we already have the nonrobust version implemented, and the two constructions are very similar.

The first major step is to implement the sparsify() function from the paper, which converts an input vector into a larger sparse version of the input vector.

• implement sparsify() function
• add unit test for sparsify() function

The next and only other major step is to figure out parameters and sampling the hash function. Hashing and evaluation will be similar to the nonrobust version.

• figure out parameters and implement sample()

[sambux1]

This is done but buggy. I need to still do 2 things:

• make sure the matrix and the sparsified inputs have compatible dimensions (currently having incompatibilities due to rounding errors)
• automatically find the minimum hash size given certain parameters

[sambux1]

I added a function to automatically calculate the minimum hash size given values for the input length and the threshold and an optional upper bound on epsilon. The bad news is it doesn't seem like any choice of parameters will make preimage resistance possible.