Hacker News Reader

I'm wondering if this sort of thing would fit well with GPU processing, which tends not to do well with branchy code?

People are working on it. The biggest problem is that cryptography usually requires bignum math and GPUs are not optimized for that. FPGAs are also being researched. The cost/benefit is not as big as you would imagine, CPUs are pretty optimized for bignum math.

I attended the event celebrating the solving of LCS35. LCS35 was a cryptographic challenge set by Ron Rivest (the R in RSA) in 1999. It was intended to be so difficult that only computers made 35 years in the future would be able to solve it.

The challenge was solved by Bernard Fabrot. It was fairly simple code on I believe an intel 4770K. The math libraries and CPU had been optimized so much in the ~20 years since the challenge was set that a consumer CPU could calculate the answer. The only catch is that it took months on end of calculation.

https://en.m.wikipedia.org/wiki/LCS35

NuFHE can do a binary operations in 0.1ms/bit, and mux operations in 0.2ms/bit using FFT, which is hyperoptimized on GPUs. I think the issue is that the keys tend to be rather large.. NuFHE's decryption keys are 110MB! So memory/FFT problem size may be the bottleneck now.

Reply on news.ycombinator.com