High-Level FHE Dialect #53
Replies: 6 comments 18 replies
-
|
I think a good next step is to give a high-level sketch of what each of the possible implementations would look like (and where the challenges might occur), even including the supposedly-naive options like encoding noise in type attributes. I am happy to take a stab at this myself just to give me a chance to think about it. For the question of "fixing arith" so that it could work with a new container type like |
Beta Was this translation helpful? Give feedback.
-
Please note that adding support for new container types is not the intention of In your case, as |
Beta Was this translation helpful? Give feedback.
-
Is there somewhere that describes what has been decided about the "arith update movements" that I could read more about? |
Beta Was this translation helpful? Give feedback.
-
|
Not that I'm aware of... You can gather most of it by reading the discourse board. Apart from that, most of the concrete gripes I also heard at the MLIR Hackathon / EuroLLVM, where I presented my approach. I'm thinking of starting an RFC post for Note that the consensus was not to deprecate arith, but to keep it around as an "unspecified" interface, which is how current users mostly experience it. Still, some changes are deemed necessary. So, even better would be someone stepping forth and starting and RFC for arith itself. I was not going to do that, because that part is more or less worthless to my work. |
Beta Was this translation helpful? Give feedback.
-
|
I welcome this initiative as we just started take a look at the MLIR landscape for FHE. In our use-case we used Proxy Re-Encryption (PRE) to enable a secure computation of data encrypted under different keys from multiple parties. Re-encryption happened to another key (i.e., the key of the party that receives the result, but is not doing the computation and not colluding with the entity that does the computation) whenever two operands of an operation have been encrypted under different keys. We implemented our prototype with PALISADE 8000 (now OpenFHE) using the BFV scheme. At the high-level IR, this required to additionally tag private data with a label, i.e., |
Beta Was this translation helpful? Give feedback.
-
|
Thank you so much for chiming in! The need to have The correct answer here might depend quite a bit on the scenario a given compiler is targeting, so on a technical level we might want to go for a very permissively typed attribute (with a sensible "N/A" default + some pretty-printing to make sure this only shows if it's actually being used)? |
Beta Was this translation helpful? Give feedback.
-
Right, in reality each operation unions the potential set of owners of a secret value that is computed. In the High-Level IR we only captured the key labels via the inputs, which gave us some polymorphism w.r.t. real keys and parties, and used those labels. In our compiler, we computed the potential owners when we did the lowering. The question is, also technically with MLIR, how much of this set of potential owners must be captured already in the type-level of the IR or whether that can be computed later, too. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for expanding on this! I like the idea of computing the sets during a lowering. |
Beta Was this translation helpful? Give feedback.
-
|
Nice! I like the idea of including the key as a parameter that the data is secret "relative" to. With regards to the idea that "should it be a key or rather a set of owners": is there really a difference? I can imagine maybe we have one key encrypted with a key shared by Alice and Bob, and then another piece of data with Alice, Bob, and Charlie. In this case of simply adding one party (or perhaps the reverse and restricting to a subset), is the PRE operation any cheaper than going from an arbitrary party A to party B? If not, then it seems like keeping track of an opaque key "label" seems to make sense, and that the lowering would be responsible for computing the owners. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for pinging me on this. You may have realized already that there haven't been any updates to
While I have a working prototype integrating all of this, it has not been scrutinized by the community yet, and I expect changes to be necessary. Unfortunately, such is the way of moving from research to upstream. Therefore, should you determine that stronger integer semantics are necessary, I would be happy to move on this together during the RFC phase, and avoid waiting on implementation delays. |
Beta Was this translation helpful? Give feedback.
-
|
I noticed that there's been quite a bit of movement on the poison semantics RFC, and I was wondering if you would you be interested in joining our next discussion meeting (Tuesday, 1st of August at 17:00 CEST) to discuss the state of |
Beta Was this translation helpful? Give feedback.
-
|
Sorry about my late reply, unfortunately I was unavailable at that time. I'm not sure whether I'm the right person for what I think you need, but I'd gladly join the next time around. Note that Mehdi has now started the discussion about the future of I think the sentiment so far supports following up on the ideas presented in this issue so far. |
Beta Was this translation helpful? Give feedback.
-
|
One of the key goals with this "High-Level FHE Abstraction" is to be able to represent complex programs pre "arithmetization" (i.e., truncation, approximation, LUT-ization, etc). However, while there are obvious ways to represent some "non arithmetic" operations in the IR (e.g., comparisons, divisions, and other "basic" operations), this gets a bit murkier for things such as commonly used activation functions (should there be an Here, I think we should follow an approach similar to what certain frontends already do (concrete comes to mind here), essentially offering an interface that accepts a function/lambda and a range and does the necessary work to figure out, e.g., a k-bit LUT. For this, the high-level dialect should probably just nest the function/lambda in a special region-based operation, to allow different compilers to apply different lowerings (e.g., polynomial approximation instead of LUTs). This raises a bunch of concrete questions about what information this operation needs to encode (in addition to the function) in order to allow this lowering to be done effectively by compilers following a variety of different approaches. Clearly, the expected input range seems pretty important, as maybe the acceptable error in bits? |
Beta Was this translation helpful? Give feedback.
-
|
On concrete there are no notion of floating point at the compiler level (we dealing only with integers). Concrete Python frontend handle some subgraphs where integers inputs are converted to floating point then convert to integer, this is transformed to a table lookup. This is the only support of floating point we have at the Concrete level. But Concrete-ML support floating points by quantizing floatting point model to integers. |
Beta Was this translation helpful? Give feedback.
-
|
About the error I'm not sure we want to express that on the apply function operators, maybe it could make sense to express that on the type? From my point of view the error is the probability than the noise lead to an incorrect decryption of an fhe value (secret) |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for the detailed update Quentin! I think assuming that there'll be some kind of quantization of floating points is a good approach, and I like the idea of quantization as something that might end up shared between different compilers. For now, I'd suggest we make sure to allow things like I really like the comparison to At the same time, I absolutely agree that it's much easier to evaluate functions in the frontend, especially for the LUT approach. Maybe this is even true for the polynomial approximation approach? A trivial approach could be to sample a lot of points of the function and then look for a polynomial that is "close enough" (for some definition of that) to all of those points in a given interval. Either way, it seems like there's definitively a need for an |
Beta Was this translation helpful? Give feedback.
-
I think we're talking about a different type of error here. In the meeting (meeting notes) we identified three types of error: encryption/LWE noise, encoding/decoding errors (e.g., CKKS or any other fixed-point approximations of reals), and program->circuit approximation error (i.e., error due to quantization and conversion of non-linear things to LUTs/polynomial approx.).
Assuming "bits" is indeed a sufficiently generic measure of "approximation error", then it might indeed be a good idea to encode this in the type system. For example, as an optional parameter along the lines of However, from a user/programmer perspective, it might be easier to think about "how many bits of error can I tolerate for this comparison/sigmoid/etc" rather than "how many bits of error can I tolerate in this value at this point in the program", as types are associated with SSA values, a lot of which don't have explicit counterparts in high-level programs. |
Beta Was this translation helpful? Give feedback.
-
|
I was skimming through ELSAM, a follow-up paper to HECATE, which in turn proposes a more optimal rescaling insertion approach than the waterline approach used in EVA, and it reminded me that we should consider how to handle (fixed-point) scale in the high-level Maybe this is actually a lower-level detail, and the compiler should work out the correct scale from some combination of high-level type, range, and "acceptable bits of approximation", but then that opens up the wohle can of worms that is floating point types and what it means to be "k bits off" on a floating point value... |
Beta Was this translation helpful? Give feedback.
-
|
In the last WG meeting, the idea of "core" and "non-core" operations came up, where "core" operations in a dialect/abstraction level. The non-core operations would come with default "lowerings" to core operations, so that tools only have to implement the core operations. While it might seem reasonable to use For example, we might have a (non-core) Alternatively, Note that this actually has implications for the information that I don't have a lot of experience with state-of-the-art polynomial approx/interp approaches for FHE, so it'd love to hear a (more) expert opinion on whether or not this is too much of a constraint. |
Beta Was this translation helpful? Give feedback.
-
|
FYI, I've started implementing I also read through the structured operations and transform dialects to see what |
Beta Was this translation helpful? Give feedback.
-
|
To expand/reframe this a bit better (contradicting some of what I wrote above): My intention is to have How this could work is following in the footsteps of Here's an example of what I mean, which I'm going to prototype in #78 this week: The input program would look something like: x : i32 = 7
# or however one gets the data as input, what matters is that the source language
# annotates `y` as private in some way we can ingest in MLIR
y : Secret[i32] = encrypt(input('Enter your value to encrypt'), sk)
z = x * yThe corresponding MLIR might look like: module {
func.func @main(%y : !secret.secret<i32>) {
%X = arith.constant 7 : i32
%Z = !secret.generic
ins(%X, %Y : i32, !secret.secret<i32>)) {
^bb0(%x: i32, %y: i32) :
%d = arith.addi %x, %y: i32
!secret.yield %d : i32
} -> (!secret.secret<i32>)
}
}Here the body of A naive lowering would match on this op, and convert If the I also think that |
Beta Was this translation helpful? Give feedback.
-
|
Moving this thread to #96 |
Beta Was this translation helpful? Give feedback.
-
As discussed in the MLIR Dialects Session, I'm setting up three discussions topics, corresponding to the three streams identified.
This is the High-Level FHE Dialect discussion, you can find the Scheme Dialects and Poly/Math Dialects discussions at the links.
The goal of this abstraction/dialect is to enable high-level programs (DSLs, annotated Python, C/C++, etc) to be translated to a scheme/implementation agnostic intermediate representation.
Technical/MLIR Challenges
In addition to the ability to distinguish between "public" and "private" data (most likely via a wrapper-style type along the lines of
!fhe.secret<T>, this requires the ability to express computations over encrypted data. Existing FHE MLIR compilers currently use their own "faux arith" dialects for this (e.g.,fhe.add(%a, %b)) as the existingarithdialect restricts the types which can be used with its operations. However, there is an opportunity here to suggest a more generic version ofariththat is more accepting of different types/semantics, with something likebase2(paper, code, spec) by @KFAFSP for use cases that need to precisely specify arithmetic semantics.Conceptual Challenges
The scheme/approach-agnostic nature of such an abstraction also requires solving a challenge not yet addressed by the existing tools: Expressing sufficient information to allow conversion to an efficient FHE "circuit", no matter which computational paradigm (binary emulation with gate bootstrapping, precise or approximate large integers, or small(ish) integers with LUTs/PBSs) is used. This in addition to the challenge of tracking encryption noise (the "error" in Learning with Errors), both in the precise setting and in the approximate setting (where noise and message are mixed). While encryption noise can most likely be handled via MLIR analysis tooling, rather than needing to be encoded into the IR, it is less clear how to do this for "program-to-circuit approximation error" that arises when one converts an existing computation to a more efficiently evaluatable form, e.g., by truncating bit width of data types and/or replacing non-arithmetic operations (e.g., comparisons, sigmoid, etc) with either LUTs or polynomial approximations. Especially for the latter, it seems unclear how to express the error introduced by a high-degree approximation as a clean "number of bits". However, this might be possible when combined with sufficient range analysis (i.e., "in [x,y], this approximation has at most b bits of error").
Next steps
We need to solve the conceptual issues around representing approximation tolerance in a scheme-agnostic way, and converge on a technical approach which we could bring back to the Working Group and, with their approval, pitch as an RFC to the MLIR upstream. The expected timeline for this is 1 month until we have a draft RFC ready to present back to the Working Group and, ideally shortly afterwards, the MLIR community.
Tasks
base2and identifying prior discussions on the intended direction ofarithBeta Was this translation helpful? Give feedback.
All reactions