This is why tools like formal verification and symbolic analyses can help you establish that for all possible integers X, your function does the right thing (for some definition of “right”). You get this assurance without having to actually enumerate all X.

There are no obvious ways to improve on this work, so it is not a matter of engineering. We really do need another breakthrough result to get us closer to practicality.

Comments URL: https://news.ycombinator.com/item?id=36831956

Points: 112

# Comments: 19

We never built it into a product because we couldn't figure out a way to monetize it to pay for the servers.

But yes, you make less as a professor than you do in industry.

Key idea is the client issues a query that is independent of what they really want. This is the “offline” query. This query is linear (unavoidable) and the client gets some hints as a result

Then later, the client can issue one or more queries for elements they want and those queries can be sublinear in terms of computation. The client uses hints to make that happen.

Some papers on this are:

https://eprint.iacr.org/2019/1075.pdf

https://eprint.iacr.org/2021/1438

https://eprint.iacr.org/2022/081.pdf

That said, yeah this hashing example is not zero knowledge because, among other things, the hash is not hiding.

I don’t see how you can call that good temperature.

I'm really curious to see where the government acquired their evidence (and what solid evidence do they have), and whether it ends up holding up in court.

Suppose H(s||k) is a collision-resistant hash function. Let's build another CRHF from H as follows: H'(s || k) = H(s || k) || last-bit-of-k.

Now let's instantiate the cryptosystem you proposed with H'. Suppose m is message and that it is of length equal to the length of the bitstring produced by H'.

We have C = H'(s||k) XOR m.

The ciphertext is thus: (k, C).

What can an attacker do? Well, the attacker can XOR the last bit of C with the last bit of k and get the last bit of m. This is already enough to violate semantic security.

You first compare target-digest with all endpoints. If it's a match with any of them, good. Then you know a pre-image is in that column.

If not, then try H(R_last(target-digest)). Does it match any endpoint?

If not, then try H(R_last(H(R_second-to-last(target-digest))).

Rinse and repeat.

Column 1 Column 2

start-text1 start-text2

last-hash1 last-hash2

You only store the start text and the last hash for each column. consists of a mix of passwords ("text ") and hashes. To see how they are computed, let us narrow our attention to a single column.

text1

computed using H(text1)

computed using R_1(hash-1)

computed using H(text-2)

computed using R_2(hash-2)

last-hash computed using H(text-3)

Each column will look like that. I'm using to denote things that are not stored. H is the hash function you are creating the rainbow table for. R_1, R_2, etc. are the reduction functions. Each column uses the same hash function and reduction functions but uses a different starting text.

Note that in a rainbow table that consists of k columns, there is no need to recompute hash/reduction functions for each chain. Instead, the attacker computes R_last(target-digest), and checks that against all the endpoints (last hash) of all column. If it matches any endpoint, then that chain likely has the corresponding password. Otherwise, compute R_last(H(R_second_to_last(target-digest))), and compare the result with all endpoints. Rinse and repeat. In the worst case, you have to compute as many hash/reduction functions as there are rows (regardless of the number of columns since all columns use the same hash and reduction functions).