search

google / heir

A compiler for homomorphic encryption
https://heir.dev/
Apache License 2.0
292 stars 44 forks source link

Add an OpenFHE exit dialect for arithmetic schemes #328

Closed j2kun closed 6 months ago

Maokami commented 9 months ago

Hi, @j2kun!

I'm interested in this topic, so I created an initial version based on the tfhe-rs dialect. There may be design issues since I simply mimicked the tfhe-rs dialect, but I would appreciate it if you could take a look at it when you have a chance.

In my opinion, when compared to the tfhe-rs dialect, there are additional considerations that should be taken into account in the OpenFHE dialect.

  1. How to represent plaintext in the dialect (OpenFHE primarily uses PackedEncoding for BGV/BFV and CKKSPackedEncoding for CKKS).
  2. Since it supports multiple schemes, a way to represent which scheme to use in the dialect.
  3. How to represent encryption parameters (N, the bitsizes of q_i's, the number of q_i's, etc.) in the dialect.
j2kun commented 9 months ago

Thank you for this! I will take a closer look on Monday.

In the mean time, I wanted to point you to an encoding attribute I defined in https://github.com/google/heir/blob/153eaf6622101375ba9e687dc17fbe076c916bb5/include/Dialect/LWE/IR/LWEAttributes.td. There you can find

As far as I could tell from my literature review, all of the encoding methods used in arithmetic FHE schemes are among these three, with the last one being CKKS.

We haven't figured out exactly how we want to use these attributes yet, but they may provide you with something to put on a plaintext or ciphertext to represent the chosen encoding.

Maokami commented 9 months ago

Oh, there was an LWE dialect! Then I think we can connect those to the following encoding APIs in OpenFHE.

Therefore, we can directly use LWEPlaintext/CiphertextType, eliminating the need for plaintext/ciphertext types in the OpenFHE dialect, I guess?

j2kun commented 9 months ago

In general the LWE dialect is supposed to represent common types and operations for LWE and RLWE across schemes. I originally intended this for reuse and abstraction across the HEIR scheme dialects. For tfhe-rust, there is a distinct set of types in their API so we have no choice to but use specific types there. But if the lwe dialect is sufficient for a particular backend, I don't have a problem with reusing the types there.

Maokami commented 9 months ago

Aha, I see, I'll take a little more time to look at it.

AlexanderViand-Intel commented 8 months ago

Hi @Maokami 👋 as I mentioned in the last working group meeting, I'm also very interested in having an OpenFHE dialect - what are your current plans for this?

Maokami commented 8 months ago

Hi @AlexanderViand-Intel 😸!

I'm just getting started with catching up on the project, but due to my limited experience, it's a bit challenging for me to figure out what needs to be done and where to begin. As a rough idea, I'm thinking about:

  1. Adding OpenFHE dialect ops (relinearization, rescale/modswith, bootstrapping, ...)
  2. Creating passes for OpenFHE dialect (from BGV dialect?)
  3. OpenFHE code generation (If I understand correctly, this is what @j2kun👋 is planning to do next, right?)

Do you have any additional opinions or priorities of what needs to be done? Your guidance would be much appreciated! 😊

j2kun commented 8 months ago

The weather has messed up my week a bit, but I can sketch out a plan later today for an end-to-end BGV path.

j2kun commented 7 months ago

Ops

Intending to mirror the OpenFHE pke API

The API methods that seem like we might want to add corresponding ops for:

Most of these have "in place" variants as well. I think the natural approach is to add these each at the same time we add the lowering from the BGV dialect.

Then there are some "advanced" ops for:

I think we should leave these advanced ops out for now.

Codegen

The basic codegen will be to generate a C++ implementation file that has some boilerplate preamble, and then translates each function to a corresponding C++ function with the corresponding API calls. The TfheRustEmitter is a good example of this. Lit tests check the generated code as strings, and then we have end-to-end tests that actually compile and run the generated rust code, and assert the output is correct.

BGV to Openfhe

The BGV dialect will be pretty close to Openfhe, but since it will lower to other library dialects, we would ideally want to know the least common denominator of BGV library APIs. I don't know exactly what that is, but I am also comfortable with that boundary evolving as we add more libraries.

Higher level -> BGV

This is the trickiest part of the pipeline, since right now we have a large gap between "secret.generic with arith ops inside" and the BGV dialect. We had talked about adding an intermediate dialect representing scheme-agnostic FHE arith/math ops, but haven't strictly needed it for the CGGI path because we emit to verilog (which supports all the arith ops we need) and use yosys/abc to translate to gate operations, which then is easy to lower to CGGI.

I think this should be out of scope of this particular ticket, since it will require a broader discussion and is somewhat independent from the low-level BGV and Openfhe APIs.

Maokami commented 7 months ago

It's a great blueprint! I'll start the ops part first.

j2kun commented 7 months ago

The OpenFHE dialect has been added now, so I'm going to close this issue and we can open more issues for other parts of the overall project of getting an end-to-end BGV flow. I'm going to start focusing on this a bit more in the next few weeks because I want to have it ready for the FHE.org conference.