PaperlayerView exact revision on arXiv

Source-linked AI summary

EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation

Roshan Dathathri, Blagovesta Kostova, Olli Saarikivi, Wei Dai, Kim Laine, Madanlal Musuvathi

arXiv:1912.11951v2cs.CRcs.LGcs.PL

TL;DR

FHE is difficult to program because its cryptographic constraints and unusual execution model require careful scheme-specific management. EVA addresses this with a general-purpose language, intermediate representation, and optimizing compiler, and its CHET re-targeting achieves a 5.3× average speedup in DNN inference. The paper demonstrates practical applications while leaving some compiler capabilities and evaluation settings bounded by explicit limitations.

  • Problem

    FHE enables privacy-preserving computation, but programming it requires cryptographic expertise and managing scheme-specific parameters, noise, scaling, and levels.

  • Method

    EVA combines a vector-oriented FHE language and intermediate representation with an optimizing compiler that hides encryption parameters, noise, and other target-scheme complexities.

  • Results

    5.3× average speedup: CHET re-targeted onto EVA outperforms unmodified CHET on average for DNN inference.

  • Takeaways & Limitations

    EVA provides a foundation for general-purpose FHE applications and domain-specific compilers while hiding cryptographic details from programmers.

  • Takeaways & Limitations

    Advanced relinearization insertion beyond the enforced constraint is left for future work, and one industrial-network evaluation used random weights and images because proprietary materials were unavailable.

Abstract

from arXiv · show

Fully-Homomorphic Encryption (FHE) offers powerful capabilities by enabling secure offloading of both storage and computation, and recent innovations in schemes and implementations have made it all the more attractive. At the same time, FHE is notoriously hard to use with a very constrained programming model, a very unusual performance profile, and many cryptographic constraints. Existing compilers for FHE either target simpler but less efficient FHE schemes or only support specific domains where they can rely on expert-provided high-level runtimes to hide complications. This paper presents a new FHE language called Encrypted Vector Arithmetic (EVA), which includes an optimizing compiler that generates correct and secure FHE programs, while hiding all the complexities of the target FHE scheme. Bolstered by our optimizing compiler, programmers can develop efficient general-purpose FHE applications directly in EVA. For example, we have developed image processing applications using EVA, with a very few lines of code. EVA is designed to also work as an intermediate representation that can be a target for compiling higher-level domain-specific languages. To demonstrate this, we have re-targeted CHET, an existing domain-specific compiler for neural network inference, onto EVA. Due to the novel optimizations in EVA, its programs are on average 5.3x faster than those generated by CHET. We believe that EVA would enable a wider adoption of FHE by making it easier to develop FHE applications and domain-specific FHE compilers.

1. Introduction

EVA is a general-purpose FHE language and intermediate representation whose optimizing compiler hides scheme-specific complexity while generating correct, secure, and efficient programs. Its re-targeting of CHET demonstrates a 5.3× average performance advantage in DNN inference.

  • FHE enables computation on encrypted data, but programming it requires cryptographic expertise and careful management of scheme-specific constraints.CKKS, for example, requires programmers to manage scaling factors and rescaling operations.
  • EVA provides vector and scalar arithmetic aligned with encrypted SIMD capabilities and serves as both a general-purpose language and an intermediate representation.Its compiler hides encryption parameters and noise while targeting efficient FHE execution.
  • The compiler automatically performs FHE-specific optimizations, including rescaling and modulus-switching insertion, and its executor parallelizes computation and reuses encrypted-message memory.These mechanisms target performance and reduced memory consumption when executing generated programs.
  • EVA applications include secure path-length computation, statistical machine learning, and image processing implemented with few lines of code.The Python frontend supports applications such as Sobel filtering and Harris corner detection.
  • 5.3× average speedup: EVA outperforms CHET in DNN inference after CHET is re-targeted to generate EVA programs.The DNN compiler uses the same tensor kernels as CHET, while EVA supplies the optimizing compilation backend.

2. Background and Motivation

FHE supports privacy-preserving computation but exposes programmers to intertwined correctness, performance, and security constraints. CKKS adds approximate fixed-point arithmetic, making scale, level, rescaling, and modulus-switching management especially difficult.

  • FHE supports encrypted evaluation but requires managing encryption parameters, ciphertext noise, multiplicative depth, and scheme-specific operations.These constraints motivate abstractions that can produce correct, efficient, and secure computations.
  • Ciphertext multiplication increases the number of component polynomials, making relinearization necessary but costly and key-dependent.Relinearization reduces ciphertexts back to two polynomials and requires distinct public keys for different input sizes.
  • CKKS provides approximate fixed-point results, combining encoding error with noise introduced by homomorphic operations.Higher scaling factors can hide errors, but they also interact with the modulus budget.
  • Rescaling consumes the ciphertext modulus budget, so logQ grows linearly with multiplicative depth and ciphertext levels decrease as rescaling proceeds.The remaining modulus determines how much further rescaling the computation can support.
  • Binary CKKS operations require matching ciphertext levels, while addition and subtraction also require matching scales.Modulus switching changes a ciphertext’s level without scaling its message.
  • Selecting rescaling points is constrained by the fixed order of prime factors in RNS-CKKS implementations.Rescaling too early can make the fixed-point representation too small for accurate computation.

3. EVA Language

EVA represents programs as vector-oriented DAGs and abstracts batching-compatible FHE schemes through a common language format. Its execution model separates ordinary input operations from compiler-inserted scheme-specific operations while preserving reference semantics.

  • EVA uses one language as input format, intermediate representation, and executable format for batching-compatible schemes such as BFV, BGV, and CKKS.Input programs omit FHE-specific details such as when to rescale.
  • EVA programs are directed acyclic graphs whose instruction nodes compute values from ordered parameter nodes.A program records instructions, constants, inputs, and designated outputs.
  • EVA distinguishes runtime inputs from compile-time constants, with Cipher values excluded from constants because their type is unresolved before key generation.Vector and Cipher inputs use fixed power-of-two sizes required by target encryption schemes.
  • The language defines reference execution using a dummy identity encryption scheme, then preserves the same execution semantics for real encryption schemes with encrypted outputs.The reference semantic recursively evaluates each node using its opcode and parameters.
  • EVA supports different input and execution vector sizes by repeating smaller input vectors until they match the target size.This construction is valid when the input size divides the execution size and preserves rotation behavior on the original elements.
  • The EVA language is serialized with Protocol Buffers and also has an in-memory graph representation for compiler analysis and transformation.The serialized definition corresponds to the language format shown in Figure 1.

4. Overview of EVA Compiler

The EVA compiler converts high-level EVA programs into executable programs while determining encryption parameters and rotation keys, hiding FHE-specific instructions from programmers. Its optimizations manage cryptographic constraints and trade off performance against accuracy through scale selection.

  • Compiler scope: The EVA compiler targets the RNS variant of CKKS in Microsoft SEAL and can be adapted to other CKKS libraries or batching-compatible schemes.The paper identifies BFV and BGV as additional schemes that EVA can support.
  • Compiler inputs and outputs: The compiler accepts an EVA program, input scales, and desired output scales, then emits an executable EVA program, encryption-parameter bit sizes, and rotation steps.The generated bit sizes and rotation steps are used to generate encryption parameters and rotation keys.
  • Compiler inputs and outputs: FHE-specific instructions such as RELINEARIZE, RESCALE, and MODSWITCH are omitted from input programs because they require scheme-specific knowledge.The compiler inserts or handles these operations in the generated program.
  • Scale selection: Input and output scales create a performance–accuracy trade-off: larger scales yield more accurate but slower programs, whereas smaller scales yield less accurate but faster programs.The scale choices affect the encryption parameters while preserving the same security.
  • Motivation and constraints: EVA enforces ciphertext constraints by matching levels and scales, controlling modulus consumption, and reducing ciphertext polynomial counts through relinearization.These constraints arise because binary operations require compatible levels and addition or subtraction requires matching scales.
  • Optimization strategies: The compiler chooses among optimization strategies such as waterline rescaling, modulus switching, scale matching, and relinearization to generate more efficient programs.For the x2y3 example, waterline rescaling uses a smaller modulus product than the input program, while relinearization reduces ciphertexts to two polynomials.

5. Transformations in EVA Compiler

EVA’s transformation compiler rewrites computation graphs to satisfy FHE correctness constraints while reducing encryption cost. Its passes coordinate rescaling, modulus switching, scale matching, and relinearization, with waterline rescaling and eager modulus switching providing key optimization choices.

  • Graph rewriting framework: EVA represents compiler transformations as local graph-rewrite rules applied according to scheduled forward or backward traversals.Each pass defines rewrite rules for subgraphs, and the schedule can affect transformation correctness or efficiency.
  • Graph rewriting framework: The transformation passes run in the order WATERLINE-RESCALE, EAGER-MODSWITCH, MATCH-SCALE, and RELINEARIZE.EAGER-MODSWITCH uses a backward pass, while the other passes use forward passes; ALWAYS-RESCALE and LAZY-MODSWITCH are defined but unused in this sequence.
  • Relinearization insertion: EVA inserts RELINEARIZE after ciphertext-ciphertext MULTIPLY operations to reduce ciphertexts to two polynomials and satisfy Constraint 3.Optimal relinearization placement is NP-hard, so EVA uses a simple constraint-enforcing pass; more advanced placement is left for future work.
  • Rescale and modulus-switch insertion: EVA inserts RESCALE and MODSWITCH nodes so coefficient moduli match at the parents of ADD and MULTIPLY nodes.The compiler tracks rescale chains and seeks conforming chains for nodes and matching chains across operation inputs.
  • Rescale and modulus-switch insertion: Using the maximum rescale value sf minimizes the number of RESCALE nodes on any path, while WATERLINE-RESCALE avoids reducing scales below the accuracy threshold.The waterline is the maximum scale among roots, and rescaling occurs only when the post-rescale scale remains above it.
  • Rescale and modulus-switch insertion: EAGER-MODSWITCH inserts switches at the earliest feasible edge, producing smaller-modulus ADD operands than lazy insertion in x^2 + x + x.The smaller coefficient modulus makes ADD faster in the illustrated comparison.

6. Analysis in EVA Compiler

EVA analyzes and executes its graph through forward and backward traversals, validation passes, parameter selection, and rotation-key selection. These analyses generate encryption bit sizes and rotation steps while enabling parallel execution and memory reuse.

  • Graph traversal and execution: EVA supports forward and backward graph traversals that visit nodes after their parents or children, respectively, without changing graph structure.Traversal state is maintained on nodes, enabling analyses and execution scheduling.
  • Graph traversal and execution: Ready nodes can execute in parallel because each active node updates only its own state.The executor schedules active nodes whose traversal dependencies are complete.
  • Graph traversal and execution: Retired-node ciphertext memory is automatically reused after dependent operations finish, reducing memory consumption.For example, the ciphertext for x^2 can be reused after RELINEARIZE executes.
  • Validation and parameter analysis: EVA validates rescale-chain conformity, matching chains at ADD and MULTIPLY inputs, scales, and ciphertext polynomial counts in separate forward passes.These assertions check the compiler constraints after transformation.
  • Validation and parameter analysis: The encryption-parameter pass derives bit sizes from conforming rescale chains and output scales, while the rotation-key pass returns unique rotation steps.The parameter pass factorizes output-scale requirements and selects the output with the largest combined chain and scale-factor count.
  • Validation and parameter analysis: EVA’s rotation-key selection pass computes the unique step counts used by ROTATELEFT and ROTATERIGHT nodes.These step counts form the set of rotation keys required by the generated program.

7. Frontends of EVA

EVA provides a Python-embedded frontend, PyEVA, for writing encrypted programs, and serves as a backend target for higher-level domain-specific compilers such as CHET.

  • PyEVA: PyEVA embeds EVA program construction in Python through a Program wrapper and context-managed operation recording.Expressions overload Python operators to provide concise program syntax.
  • Domain-specific compiler backend: EVA can serve as a backend for domain-specific compilers, allowing higher-level systems to generate EVA programs instead of directly invoking FHE libraries.The modified CHET compiler inserts EVA instructions through a new HISA implementation, decoupling generation from execution.

8. Experimental Evaluation

The evaluation measures EVA on encrypted arithmetic, machine learning, image processing, and DNN inference, comparing DNN performance with CHET under matched conditions. EVA achieves substantial performance and scaling advantages while supporting practical applications.

  • Experimental setup: EVA is evaluated on arithmetic, statistical machine learning, image processing, and DNN inference using SEAL’s RNS-CKKS implementation.Experiments use a 56-core, four-socket machine with 128-bit security.
  • DNN inference: 5.3× average speedup over CHET comes from global placement of FHE-specific instructions and cross-kernel parallelization.EVA is 2.3× faster on one thread from instruction placement, with a further 2.3× average improvement on 56 threads from parallelization.
  • Encryption parameters: EVA selects smaller coefficient moduli than CHET, reducing the polynomial modulus degree and the cost and memory of homomorphic operations.Global analysis minimizes coefficient-modulus chain length, whereas kernel-local choices can be sub-optimal for the whole program.
  • Comparison with hand-written implementations: EVA outperforms LoLa on reported MNIST and CIFAR-10 comparisons while evaluating larger networks with higher accuracy.For MNIST, latency is 1.2 seconds versus 2.2 seconds; for CIFAR-10, 72.7 seconds versus 730 seconds.
  • Other applications: Sobel filtering takes half a second and Harris corner detection takes one second on encrypted data using one thread.The evaluation describes Harris detection as one of the most complex CKKS programs evaluated.

9. Related Work

EVA differs from prior FHE compilers by targeting CKKS, supporting domain-specific compiler backends, and applying global optimization across kernels while hiding cryptographic details.

  • FHE libraries and abstractions: EVA abstracts batching-compatible schemes including BFV, BGV, and CKKS while hiding cryptographic details from programmers.This distinguishes its language abstraction from lower-level libraries that expose FHE primitives.
  • General-purpose FHE compilers: Unlike prior general-purpose compiler languages, EVA supports rotations on fixed power-of-two-sized vectors, enabling domain-specific compiler targets such as CHET.Other language designs lack this capability.
  • General-purpose FHE compilers: EVA is the first general-purpose compiler described here for CKKS, whereas prior general-purpose compilers target BFV or BGV.Its graph-rewriting passes insert RESCALE and MODSWITCH correctly using global analysis.
  • Domain-specific FHE compilers: Unlike EVA, nGraph-HE2 uses a hybrid model requiring client-server interaction for non-HE-compatible operations and increasing communication overhead.Neither nGraph-HE nor nGraph-HE2 automatically selects encryption parameters.
  • Domain-specific FHE compilers: Existing domain-specific FHE compilers rely on expert-optimized high-level kernels with visibility limited largely to individual kernels.EVA instead performs global analysis and parallelizes FHE operations across kernels transparently.

10. Conclusions

EVA combines a general-purpose FHE language, an intermediate representation, and an optimizing compiler that hides cryptographic details while generating efficient code. Retargeting CHET onto EVA yields a 5.3× average speedup and supports broader encrypted-data applications.

  • Conclusions: EVA provides a Python frontend and optimizing compiler that hide cryptographic details while generating correct, secure, and efficient code for SEAL.It is also designed to support targeting by domain-specific languages.
  • Conclusions: 5.3× average speedup is achieved when the unmodified CHET compiler is retargeted onto EVA.The paper presents EVA as a foundation for richer FHE applications and domain-specific or auto-vectorizing compilers.
Loading 1912.11951v2…