News for hackers. Stuff that matters.
Re:Google’s Fully Homomorphic Encryption Compiler – A Primer by j2kun on Monday February 13, 2023 @10:13PM (#34784778)
Short answer: string cap has more parallelism in the circuit. Depth is more important than total number of gates, and optimizers can decrease depth pretty well.
Re:Google’s Fully Homomorphic Encryption Compiler – A Primer by squeaky-clean on Tuesday February 14, 2023 @02:08AM (#34786383)
Thanks (and Dylan18607). So to continue assuming, the number of wires specified is just the input/output, and the add.cc has more intermediate "wires"?
Re:Google’s Fully Homomorphic Encryption Compiler – A Primer by j2kun on Tuesday February 14, 2023 @12:06PM (#34792388)
It's more like: to implement add you need a ripple carry adder. You can't evaluate bit 6 until you've evaluated bits 1-5. So there's a nested dependence that makes the circuit deep. String cap, on the other hand, can be implemented in parallel by looking at pairs of characters independently. So that makes it into a parallel band of small circuits, which we can evaluate in parallelism. Also I think the capitalization routing affects fewer bits of a char (it's just toggling one bit in each char, IIRC).
Re:Google’s Fully Homomorphic Encryption Compiler – A Primer by anthk on Tuesday February 14, 2023 @01:30PM (#34793776)
It's faster to carry six glasses at once than having to carry them to some point one by one.
Re:Google’s Fully Homomorphic Encryption Compiler – A Primer by squeaky-clean on Wednesday February 15, 2023 @09:58PM (#34814427)
That makes perfect sense, thank you! I also didn't know until today that capitalization in ascii is just the 6th bit. I thought it would have been doing 32 subtract operations. (I'll be honest I haven't written my own uppercase function since school haha)