CGGI / TFHE scheme: Common LUT optimizations?

[asraa]

Some LUTs generated by Yosys for a circuit seem more common that others - namely, 128, 120, 1, and others.

It may be an interesting optimization to target these LUTs to some optimized modules, or to use some linear rewrites for these LUTs and avoid the bootstrap operation in the PBS.

[j2kun]

These LUTs correspond to the following operations, where the input bits a, b, c are combined into a single value via concatenating their bits, or equivalently input = 4*c + 2*b + a. The "operands" below are referring to a, b, c.

• 1: output 1 if all operands are 0, otherwise 0
• 128: output 1 if all operands are 1, otherwise 0
• 120: output 1 if input >= 3, i.e., if c=1 or (b=1 and a=1)

[j2kun]

For fun, I tried asking GPT4 to interpret the third LUT, and it was unable to.

[asraa]

It will be a tradeoff with increased noise to use multiplications for the 1 and 128, but it's possible that passes that find better bootstrapping placement mitigates that!

[j2kun]

Combing the tfhe-rs codebase, I didn't find anything existing that handles these without a bootstrap. Moreover, the old TFHE API also seems to require a bootstrap for every boolean gate, even though they did some tricky ops to avoid combining two inputs into one with a scale-and-add like we do.