Implement CKKS in HEIR

[j2kun]

This tracking issue is for the implementation of (at least one variant of) the CKKS FHE scheme as lowering passes in HEIR. This implementation is generally happening inside lib/Dialect/LWE/Conversions/LWEToPolynomial/LWEToPolynomial.cpp

Still TODO:

• Relinearize, basis conversion, key switch: Implement CKKS Relinearize #2650
• Rotate
• Level_reduce/rescale
• Bootstrap

Done:

• Encrypt/decrypt
• Add/Sub/AddPlain/SubPlain
• Mul (without relinearize)

[NarasimhanKovalai]

Hello @j2kun , I am interested to contribute to this issue. I have good working knowledge of MLIR Compiler Infrastructure (Custom Dialect, Ops, Pass Infrastructure, Traits, Pattern Rewrites/OpRewrite pattern in dialect conversion and FileChecks).

I expect some time to get famiiar with the codebase(1 week maybe?). So do let me know if there is some timeline in mind to close this issue.

Let me know if I can start with the above. Thanks!

[j2kun]

Hello @j2kun , I am interested to contribute to this issue. I have good working knowledge of MLIR Compiler Infrastructure (Custom Dialect, Ops, Pass Infrastructure, Traits, Pattern Rewrites/OpRewrite pattern in dialect conversion and FileChecks).

I expect some time to get famiiar with the codebase(1 week maybe?). So do let me know if there is some timeline in mind to close this issue.

Let me know if I can start with the above. Thanks!

This issue requires a rather deep expertise in cryptography. Are you familiar with the CKKS homomorphic encryption scheme? If you haven't implemented it before in a software library, this issue may be a poor starter ticket.

If you are serious about contributing, consider attending office hours, with the calendar at https://heir.dev/community

[NarasimhanKovalai]

Hello @j2kun , I am interested to contribute to this issue. I have good working knowledge of MLIR Compiler Infrastructure (Custom Dialect, Ops, Pass Infrastructure, Traits, Pattern Rewrites/OpRewrite pattern in dialect conversion and FileChecks).
I expect some time to get famiiar with the codebase(1 week maybe?). So do let me know if there is some timeline in mind to close this issue.
Let me know if I can start with the above. Thanks!

This issue requires a rather deep expertise in cryptography. Are you familiar with the CKKS homomorphic encryption scheme? If you haven't implemented it before in a software library, this issue may be a poor starter ticket.

If you are serious about contributing, consider attending office hours, with the calendar at https://heir.dev/community

I have theoretical understanding of the CKKS algorithm, but I have not implemented it seriously from scratch. I see this issue as an opportunity to learn the same and contribute to the repository using my MLIR Skills. However that being said, I will try my best to attend the office hour meetings to get an idea on how to get started on starter issues.

[AlexanderViand]

Done:

• Encrypt/decrypt

Are we sure this is actually done for CKKS? See this thread on discord

EDIT: pretty sure it's not, there's even a TODO and a (rather old) issue

• For encrypt and decrypt lowering LWE to Polynomial, add support for encryption schemes besides BGV #882

[j2kun]

Yes, agreed, though the BFV encryption is similar enough to CKKS, I think there are probably some gaps there. The existing code is at

heir/lib/Dialect/LWE/Conversions/LWEToPolynomial/LWEToPolynomial.cpp

Line 162 in 10fb051

struct ConvertRLWEEncrypt : public OpConversionPattern<RLWEEncryptOp> {