Homomorphic Encryption for Developers

A developer-focused tutorial that moves from algebra and textbook RSA to a working BFV implementation, then examines trust boundaries and the obstacles to practical FHE.

Roadmap

This tutorial develops homomorphic encryption from its security motivation to its practical use. The goal is not merely to show that encrypted computation is possible, but to help you decide when it is appropriate, select a suitable scheme, and recognize what it does not protect.

You will learn how to:

• identify the trust boundary that ordinary encryption leaves around computation;
• describe an HE system in terms of key generation, encryption, evaluation, and decryption;
• distinguish partially, somewhat, leveled, and fully homomorphic encryption;
• choose between exact modular arithmetic, approximate real-number arithmetic, Boolean circuits, and programmable lookup tables;
• reason about multiplicative depth, ciphertext noise, bootstrapping, packing, and ciphertext expansion;
• combine HE with differential privacy, secure multiparty computation, zero-knowledge proofs, trusted execution environments, and private information retrieval;
• evaluate candidate uses in public clouds, private clouds, blockchains, federated analytics, and collaborative data systems; and
• account for integrity, metadata leakage, key management, parameter selection, performance, and implementation risk.

The tutorial first establishes the problem and the HE execution model. It then introduces the mathematical foundations and representative schemes, before moving to implementation patterns and hands-on prototyping. By the end, you should be able to turn a privacy requirement into an explicit threat model, an encrypted circuit, and a benchmarkable prototype rather than treating HE as a universal privacy layer.

Introduction

Consider a healthcare application in which a patient or hospital wants a cloud service to evaluate a risk model over a medical record. Encryption can protect the record while it is stored and while it travels over a network. Ordinary software, however, normally processes plaintext, so the record must eventually enter a trusted execution boundary. That boundary might be the data owner’s device, an organization-controlled server, or a trusted execution environment. It does not necessarily mean that a cloud provider receives the decryption key, but it does mean that some component must be trusted with readable data.

Homomorphic encryption, abbreviated as HE, changes that boundary. A data owner encrypts a message, an evaluator applies an allowed computation directly to the ciphertext, and an authorized party decrypts the result. The evaluator need not receive the secret key or the plaintext.

RSA and AES are useful reference points, but deployed forms of those systems do not provide general encrypted computation. Textbook RSA has an algebraic multiplicative property, yet it is deterministic and insecure as an encryption construction; secure encodings such as OAEP deliberately remove that property. RSA is also vulnerable to a sufficiently capable fault-tolerant quantum computer running Shor’s algorithm.¹ AES is a symmetric block cipher for protecting data, not an HE scheme. Grover’s algorithm gives a generic quadratic speedup for idealized key search, which is why quantum security discussions distinguish the effect on symmetric keys from Shor’s polynomial-time attack on factoring.²

An HE scheme can be described with four algorithms:

1. \operatorname{KeyGen}(1^\lambda) creates a secret key sk and the public or evaluation material required by the selected scheme.
2. \operatorname{Enc}_{pk}(m) encrypts a plaintext message m as a ciphertext c.
3. \operatorname{Eval}_{evk}(f,c) evaluates a supported function f over c and returns a result ciphertext c_f.
4. \operatorname{Dec}_{sk}(c_f) decrypts that result.

The central correctness requirement is:

\operatorname{Dec}_{sk}\!\left(\operatorname{Eval}_{evk}\!\left(f,\operatorname{Enc}_{pk}(m)\right)\right)=f(m). \tag{1}

For exact schemes, the equality in Equation 1 is interpreted in the scheme’s plaintext ring. For approximate schemes such as CKKS, the decrypted value should instead be sufficiently close to f(m) under an application-defined error tolerance. In either case, correctness depends on compatible parameters and on keeping accumulated error within the scheme’s supported range.

HE therefore protects selected data values while a supported computation is performed. It does not automatically hide message length, traffic volume, timing, access patterns, the evaluated function, or the final plaintext once an authorized party decrypts it. It also does not prove that an evaluator ran the requested computation. Those properties require additional system design.

The challenge with data security

The phrase data in use compresses several different risks into one label. Before choosing HE, separate them.

1. Plaintext exposure during computation. Conventional processors ordinarily need readable operands. Administrators, compromised software, memory-disclosure vulnerabilities, or an overly broad service role may therefore gain access to sensitive values.

2. Metadata and access-pattern leakage. Encryption may leave record sizes, query frequency, timing, tenant identity, network endpoints, and memory-access patterns visible. A repeated query against an oncology database can be sensitive even when the record contents remain encrypted.

3. Output leakage. A computation can reveal private information through its legitimate result. A precise statistic, model prediction, or repeated series of answers may expose an individual even if every intermediate value was encrypted.

4. Integrity and availability failures. An evaluator may return a stale, malformed, or deliberately incorrect ciphertext. HE confidentiality does not make a server honest or available.

5. Key and endpoint compromise. Whoever can decrypt the result remains security-critical. Client devices, key stores, decryption services, and recovery procedures must be protected independently of the encrypted evaluator.

HE primarily addresses the first risk for computations that can be expressed efficiently in the chosen scheme. It can also reduce the amount of plaintext exposed inside a service. The other risks remain, so an HE design should begin with explicit answers to the following questions:

• Which values must remain secret, and from whom?
• Which party selects the function and which party may learn it?
• Who may decrypt each output?
• What metadata can the evaluator observe?
• Must the client verify that the result is correct?
• What information may the output legitimately reveal?
• Are the clients, evaluator, and key holders honest, curious, malicious, or potentially colluding?

These questions turn a broad privacy objective into a testable security model.

Computing on encrypted data

The diagrams in this tutorial use a consistent visual grammar. Color is repeated by shape and text so that meaning does not depend on color alone.

Meaning	Shape	Color	Interpretation
Trusted operation	Rounded rectangle	Green	Runs inside the client or another trusted key-holding boundary
External evaluation	Rectangle	Amber	Runs in an outsourced or otherwise untrusted computational environment
Ciphertext	Parallelogram	Blue	May cross the trust boundary without exposing its plaintext value under the stated security assumptions
Plaintext	Parallelogram	Red	Is readable and therefore sensitive when it crosses the trust boundary

Table 1: Diagram grammar used throughout this tutorial.

In an ordinary outsourced workflow, Alice sends a readable input m to Bob, who computes f(m) and returns a readable result. Transport encryption can protect both messages in transit, but Bob’s application still receives plaintext.

flowchart TD
  subgraph Client[Trusted client]
    C1([Prepare private input m]):::trusted
    C2[/Plaintext input m/]:::plaintext
    C3([Use result of f]):::trusted
  end
  subgraph Server[External evaluator]
    S1[Evaluate function f]:::evaluator
    S2[/Plaintext result/]:::plaintext
  end
  C1 --> C2 --> S1 --> S2 --> C3

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 1: Ordinary outsourced computation exposes plaintext to the external evaluator

With HE, Alice encrypts m locally. Bob receives a ciphertext c, evaluates f homomorphically, and returns c_f. Only the trusted client decrypts the result.

flowchart TD
  subgraph Client[Trusted client]
    C1([Encrypt private input m]):::trusted
    C2[/Ciphertext c/]:::ciphertext
    C3([Decrypt and use result]):::trusted
  end
  subgraph Server[External evaluator]
    S1[Evaluate function f]:::evaluator
    S2[/Result ciphertext c_f/]:::ciphertext
  end
  C1 --> C2 --> S1 --> S2 --> C3

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 2: Homomorphic evaluation keeps the input and result encrypted at the external evaluator

Suppose Alice encrypts two messages a and b as c_a and c_b. A scheme that supports homomorphic addition and multiplication defines ciphertext operations, written here as \boxplus and \boxtimes, such that:

\begin{aligned} \operatorname{Dec}_{sk}(c_a \boxplus c_b) &= a+b,\\ \operatorname{Dec}_{sk}(c_a \boxtimes c_b) &= a\times b. \end{aligned} \tag{2}

The ciphertext operations in Equation 2 are not ordinary plaintext arithmetic. Internally they manipulate polynomials, residues, or lattice samples, and they increase ciphertext error or consume a level from a modulus chain. Multiplication is usually much more expensive than addition and has a larger effect on the available computation budget.

Complex programs are compiled into arithmetic or Boolean circuits built from supported operations. The relevant cost is therefore not just the number of source-code instructions. Multiplicative depth, rotations, comparisons, nonlinear functions, bootstrapping, data packing, and communication can dominate performance.

Semantic security and controlled malleability

Modern randomized encryption is commonly analyzed through indistinguishability under chosen-plaintext attack, abbreviated as IND-CPA. Informally, an efficient adversary should not be able to distinguish which of two equal-length chosen messages produced a challenge ciphertext, except with negligible advantage. Fresh randomness normally causes repeated encryptions of the same plaintext to produce different ciphertexts.³

IND-CPA is a computational guarantee about message content under a defined experiment. It is not a promise that a ciphertext leaks nothing at all. Length, parameters, timing, access patterns, and protocol behavior may remain observable. The guarantee also depends on correct parameter selection, fresh randomness, safe key handling, and an implementation that does not leak through side channels.

HE adds deliberate, structured malleability. An evaluator is allowed to transform a ciphertext so that decryption yields a corresponding transformation of the plaintext. This is precisely the feature that authenticated encryption normally prevents. As a result, an HE ciphertext should not be treated as though it were an authenticated message. If an application needs integrity, origin authentication, replay protection, or proof that a particular circuit was evaluated, it must add suitable mechanisms around the HE computation.

This relationship leads to three important distinctions:

• Semantic security is not non-malleability. An encryption scheme can hide plaintext while still permitting meaningful ciphertext transformations.
• Controlled evaluation is not correctness proof. A server can return an arbitrary ciphertext unless a protocol verifies the computation or constrains the server’s behavior.
• MPC is not merely ciphertext malleability. Secure multiparty computation is a broader protocol family that may use secret sharing, garbled circuits, oblivious transfer, commitments, HE, or combinations of those techniques.

Most practical HE schemes target IND-CPA-style confidentiality or HE-specific extensions of it. Conventional adaptive chosen-ciphertext security is generally incompatible with unrestricted public evaluation because a successful authenticity check would reject the transformations that make HE useful. A complete application therefore separates the confidentiality goal from its integrity and authorization goals.

Types of HE

HE schemes are often classified by the family and depth of computations they support. The boundaries are conceptual rather than product categories: the same underlying scheme may be used in a leveled configuration without bootstrapping or in a fully homomorphic configuration with bootstrapping.

Class	Supported computation	Typical mechanism	Representative use
Partially homomorphic encryption	Repeated use of one algebraic operation or a narrowly defined family	Additive or multiplicative homomorphism	Sums, tallies, scalar products, or threshold protocol components
Somewhat homomorphic encryption	Addition and multiplication for a limited, relatively shallow circuit	Finite error budget	Proofs of concept and low-depth computations
Leveled homomorphic encryption	Circuits up to a parameterized maximum multiplicative depth	Modulus chain sized for the target circuit, normally without bootstrapping	Batched analytics and inference with a known depth
Fully homomorphic encryption	Any finite circuit expressible in the supported model	Bootstrapping refreshes ciphertexts when necessary	Workloads whose depth is not bounded by the initial level budget

Table 2: Capability classes of homomorphic encryption.

Partially homomorphic encryption. Paillier encryption supports additive aggregation: multiplying appropriate Paillier ciphertexts corresponds to adding their plaintexts. Textbook RSA and ElGamal have multiplicative algebraic properties, but that observation must not be confused with a recommendation to use textbook RSA as secure encryption. Goldwasser–Micali supports XOR over encrypted bits. These schemes remain useful when a protocol needs a narrow operation and does not need a general circuit.⁴

Somewhat and leveled homomorphic encryption. Ciphertexts in lattice-based schemes contain an error term that hides the message. Homomorphic operations enlarge that error or consume levels. Parameters can be selected for a known circuit depth, which often avoids the cost of bootstrapping. In application development, leveled HE is usually the more useful term because it makes the design constraint explicit.

Fully homomorphic encryption. Gentry’s 2009 construction showed how a scheme capable of evaluating its own decryption circuit could refresh a ciphertext through bootstrapping, thereby supporting arbitrary finite circuits.⁵ The word fully describes the supported class of computations, not infinite speed or an infinite execution. Every real evaluation is finite, consumes time and memory, and must use concrete security parameters.

Developers must also choose a plaintext and computation model:

• BFV and BGV provide exact modular arithmetic over integers or polynomials. Overflow is modular, so encoding bounds must be planned.
• CKKS provides approximate arithmetic over packed real or complex values. Rescaling and numerical error are part of the program’s correctness analysis.
• FHEW and TFHE-style schemes are well suited to Boolean gates and programmable lookup tables, including comparisons and other non-arithmetic operations.
• Scheme switching can move selected values between representations, but it adds conversion cost and new parameter constraints.

There is no universally best scheme. A voting tally, a neural-network inference, and a private string comparison have different arithmetic, precision, latency, and throughput requirements.

How HE enhances private computing

HE is one privacy-enhancing technology among several. Each technique protects a different boundary, so combinations should be driven by the threat model rather than by the assumption that more cryptography automatically means more privacy.

Technique	Primary protection	What it does not provide by itself
Homomorphic encryption	Confidentiality of selected values during supported computation	Output privacy, access-pattern privacy, or proof of correct evaluation
Differential privacy	A bound on how much one person’s data can influence a released distribution	Confidential processing of raw inputs or exact answers
Secure multiparty computation	Joint computation without revealing each party’s input beyond the protocol output	A bound on what the agreed output reveals
Zero-knowledge proof	Evidence that a stated relation holds without revealing the witness beyond the proof’s leakage	General confidentiality of data stored or processed elsewhere
Trusted execution environment	Hardware-enforced isolation for code and data while executing	Security outside the hardware trust model or immunity to every side channel
Private information retrieval	Privacy of the requested index from the database server	Database privacy, response-size privacy, or correctness unless the protocol adds them

Table 3: Complementary privacy technologies and their boundaries.

Differential privacy. Differential privacy, abbreviated as DP, constrains how much the distribution of a released result can change when one person’s record is added, removed, or replaced. HE can protect inputs and intermediate values before release; DP can limit what the decrypted or published output reveals. DP is not de-identification, and repeated releases consume privacy budget.⁶

Secure multiparty computation. MPC allows several parties to compute a function over private inputs while limiting what each participant learns. HE may reduce interaction in some MPC protocols, while secret sharing or garbled circuits may be faster for other operations. Threshold HE is particularly useful when no single organization should hold the complete decryption key.⁷

Zero-knowledge proofs. A zero-knowledge proof can show that a precisely defined statement is true without revealing the witness beyond what follows from the statement. In an HE workflow, a proof might bind an input ciphertext, an authorized circuit, and an output ciphertext. The proof system must be designed for that relation; attaching an unrelated proof does not make an HE result verifiable.⁸

Trusted execution environments. A TEE protects code and plaintext within a hardware-enforced enclave. It can run operations that are awkward under HE, but it introduces trust in the processor, its firmware, remote attestation, and its resistance to side channels. A hybrid design may use HE across administrative domains and a TEE only for a carefully bounded conversion or decryption step.⁹

Conventional controls still matter. TLS protects network channels, authenticated encryption protects stored or transmitted objects, access-control systems decide who may invoke an operation, and hardware security modules protect keys. HE narrows plaintext exposure; it does not replace those controls.

Applications of HE

An attractive HE use case normally has four properties:

• the evaluator needs to compute on data that it should not read;
• the required function can be expressed efficiently in an HE-friendly circuit;
• an authorized party can retain control of decryption; and
• the privacy benefit justifies additional computation, memory, bandwidth, and engineering complexity.

The examples below are deployment patterns, not claims that HE is the best solution in every named industry. A benchmark and threat-model review are required before production use.

Public cloud services

A common public-cloud architecture separates the data owner from the evaluator:

1. The owner encodes and encrypts data on a trusted system.
2. The cloud stores ciphertexts and evaluates an approved function.
3. The cloud returns an encrypted result.
4. The owner, or an authorized decryption service, decrypts that result.

This pattern can reduce the need to trust cloud administrators, hypervisors, application workers, and analytics services with plaintext. Candidate workloads include:

• encrypted aggregation of financial, operational, or telemetry data;
• private scoring in which a customer keeps features secret from a model service;
• private inference in which a service keeps its model, the client’s input, or both confidential, provided the selected protocol supports the intended model-privacy goal;
• encrypted matching, filtering, or classification over a constrained feature representation; and
• cross-tenant analytics in which only an approved aggregate is decrypted.

HE does not make a public cloud invisible. The provider may still observe account identity, request timing, payload size, computation duration, resource use, and the selected endpoint. The evaluator normally knows the function it runs; protecting a service’s model from the client or hiding the evaluated circuit from the decryptor requires separate measures. Rate limits, authentication, authorization, audit logs, traffic analysis, and output review remain part of the design.

The programming model also matters. A linear statistic or polynomial approximation can be a good fit. Branch-heavy code, arbitrary strings, large database scans, and highly nonlinear models can be expensive unless the scheme or compiler offers efficient comparisons and lookup tables. A useful prototype therefore starts from the exact function, not from the general idea of moving an existing application into an encrypted domain.

Private cloud computing

A private cloud gives an organization administrative control, but it does not eliminate insider risk, software compromise, supply-chain risk, or lateral movement. HE can reduce plaintext exposure even when the infrastructure belongs to the same organization.

Use each control at the boundary it is designed to protect:

• Data at rest: authenticated storage encryption and disciplined key management protect disks, snapshots, and backups.
• Data in transit: TLS or an equivalent authenticated channel protects network traffic and endpoints.
• Data in use: HE keeps selected values encrypted during outsourced computation; a TEE instead isolates plaintext computation inside a hardware boundary.
• Collaborative control: threshold HE, multi-key HE, or MPC can prevent one administrator or institution from decrypting alone.
• Correctness: a proof system, replication strategy, or application-level verification can detect an incorrect result.

Traditional single-key HE commonly expects inputs under one compatible key context, but that is a deployment pattern rather than a universal law. Threshold HE distributes one logical secret key among several parties. Multi-key HE permits evaluation over ciphertexts associated with different keys and requires the relevant parties to participate in output decryption.¹⁰

Representative private-cloud patterns include:

• a hospital encrypting feature vectors before an internal analytics cluster evaluates a risk model;
• a bank isolating encrypted scoring from general-purpose data-processing accounts;
• several subsidiaries using threshold decryption so that no single operator can reveal a joint result; and
• a research environment combining encrypted aggregation with a separately governed disclosure review.

These designs can support a compliance program, but HE alone does not establish compliance with GDPR, HIPAA, PCI DSS, NIS2, or any other legal or industry framework. Lawful basis, data minimization, retention, access control, auditability, incident response, and organizational governance remain separate obligations.

Blockchain technology

A public blockchain replicates state so that many validators can agree on it. That transparency conflicts with applications that need confidential amounts, identities, bids, or contract state. HE can represent selected state as ciphertext and permit transformations without exposing the underlying values, but doing so creates three immediate design questions:

• Who creates and protects the encryption and evaluation keys?
• How do validators reject invalid encrypted state transitions?
• Who can decrypt an output, and under what threshold or policy?

Putting ciphertext on a blockchain does not answer those questions. It can also create permanent ciphertext retention, metadata leakage, and substantial execution cost.

HE, ZKPs, and MPC

HE, zero-knowledge proofs, and MPC serve complementary roles in a confidential blockchain design:

• HE provides data confidentiality during a supported state transition. Validators or an off-chain service can transform encrypted values without learning them.
• A zero-knowledge proof can provide public verifiability. The proof can show that the transition obeyed a contract rule and was bound to the correct input and output commitments or ciphertexts.
• MPC or threshold cryptography can distribute trust. A committee can generate keys, authorize decryption, or jointly release an output without giving one member unilateral access.

Consensus records which state transition the network accepted. Consensus alone does not prove that an opaque off-chain computation was mathematically correct. That claim requires validators to recompute the transition, verify a proof, or rely on an explicitly trusted mechanism.

Other cryptographic techniques

Several additional primitives may appear in the same protocol, but their roles should remain distinct:

• Commitments bind a party to a value while optionally hiding it until opening. A homomorphic commitment can support algebraic checks over committed values, but it is not encryption and does not by itself grant decryption capability.
• Digital signatures authenticate transactions and establish who authorized them. They do not hide transaction data.
• Threshold signatures and threshold decryption distribute authority across a committee. Their security depends on the threshold, participant corruption model, and key-generation protocol.
• Ring signatures can hide which member of a defined group signed a message. They are orthogonal to HE and should be added only when signer anonymity is a requirement.
• Attribute-based or identity-based encryption can express access policies or simplify public-key naming. They govern access to protected data rather than supplying general encrypted computation.

Representative designs

Potential blockchain designs include:

• Sealed-bid auctions: bids remain encrypted during comparison or aggregation, a proof enforces the auction rule, and a threshold committee releases only the authorized result.
• Confidential voting: ballots are encrypted and homomorphically tallied, eligibility and ballot validity are proved separately, and trustees jointly decrypt the total.
• Private asset rules: encrypted balances are updated under constrained arithmetic while proofs prevent value creation or invalid ranges.
• Supply-chain aggregates: participants disclose verifiable provenance events while keeping selected quantities or prices encrypted.

Each design must specify what remains public. Transaction timing, participant addresses, proof size, contract calls, and the occurrence of a state transition may still reveal sensitive information.

Secure data operations

Secure data operations arise when several organizations or devices want a joint statistic or model without centralizing all raw records. Federated learning is one example: participants train locally and send model updates rather than raw training data. This architecture reduces data movement, but model updates and the final model can still leak information. HE, secure aggregation, MPC, and DP are optional protections added to the federated protocol; none is inherent in federated learning.¹¹

A representative protected-aggregation workflow is:

1. Participants clip or otherwise bound their contributions according to the protocol.
2. Each participant encrypts an update under a common, threshold, or multi-key arrangement.
3. An evaluator aggregates the encrypted updates.
4. Authorized parties decrypt only the aggregate.
5. A DP mechanism adds calibrated randomness before the result or trained model is released, if the release requires a formal individual-level privacy bound.

HE and DP use the word noise for unrelated mechanisms. Ciphertext error in lattice HE is a cryptographic component that enables security and constrains correctness. DP noise is randomized perturbation calibrated to a query’s sensitivity and privacy parameters. Increasing one does not substitute for the other.

Privacy budget management

A randomized mechanism M satisfies (\varepsilon,\delta)-differential privacy if, for every pair of neighboring datasets D and D' and every measurable set of outputs S,

\Pr[M(D)\in S] \leq e^{\varepsilon}\Pr[M(D')\in S] + \delta. \tag{3}

The neighboring relation must be specified. It may represent adding or removing one person, or replacing one bounded record. The value \varepsilon controls a multiplicative bound on distributional change, while \delta permits an additive relaxation. It is misleading to describe \delta simply as the probability that privacy fails.

Repeated use requires accounting:

• Basic composition adds the privacy parameters of individual mechanisms and is easy to understand but can be loose.
• Advanced composition, Rényi DP, and privacy-loss accounting can provide tighter bounds for repeated or sampled mechanisms under their respective assumptions.
• Post-processing does not consume additional privacy budget when it uses only an already private output and no fresh access to the underlying data.
• Adaptive queries still compose, so a system must authorize and record releases rather than treating each query in isolation.

No task-independent accuracy percentage follows from \varepsilon and \delta. Utility also depends on sensitivity, clipping, population size, sampling, mechanism choice, model architecture, number of rounds, and the chosen accountant. A value such as \varepsilon=1 is therefore not a complete privacy or accuracy assessment.

Advanced protocols

HE can be one component of more specialized protocols:

• Secure aggregation: the coordinator learns an aggregate rather than each contribution. Threshold HE or secret-sharing-based MPC can implement this property; DP can then constrain what the released aggregate reveals.
• Private set operations: organizations can compute an intersection, cardinality, or aggregate over matching records. PSI is a separate functionality from PIR, even though implementations may reuse HE, oblivious transfer, hashing, or MPC.
• Privacy-preserving inference: a data owner can keep features secret from a model service. Protecting the model from the client is a separate requirement and may need a specialized two-sided protocol.
• Collaborative fraud analysis: institutions can contribute bounded signals to an encrypted or secret-shared aggregate while governance defines which alerts may be revealed.
• Cross-institution research: data custodians can compute approved statistics without pooling raw records, then apply disclosure controls or DP to the released output.

Practical protocol design must account for participant dropouts, malicious inputs, duplicate records, data provenance, communication cost, key rotation, decryption authorization, and auditability. HE protects encoded values; it does not establish that the inputs are accurate, lawful, or representative.

Representative deployments

The strongest candidates are usually narrow, repeated workflows with a stable schema:

• hospitals computing an encrypted count or regression statistic under jointly governed decryption;
• companies producing salary benchmarks from bounded contributions and releasing only DP-protected aggregates;
• banks computing cross-institution risk signals without disclosing complete customer ledgers;
• insurers evaluating a shared risk model over encrypted feature vectors; and
• public agencies aggregating regional measurements while separating computation from disclosure approval.

For each case, the design should state whether privacy is required between contributors, against the evaluator, against the result recipient, or against all three. Different answers lead to different combinations of HE, MPC, and DP.

Private information retrieval

Private information retrieval, abbreviated as PIR, allows a client to retrieve an item from a server-held database without revealing the requested index to the server. PIR protects query privacy. It does not automatically hide the database from the client beyond the retrieved item; that stronger goal is called symmetric PIR. It also does not automatically hide response size, timing, client identity, or repeated-query patterns.

A simplified HE-based PIR construction illustrates the idea. Let a database contain records x_1,\ldots,x_n, and let the client want record x_j. The client creates a one-hot selector vector q with q_j=1 and all other entries equal to zero, encrypts its components, and sends the ciphertexts to the server. The server evaluates an encrypted dot product:

\begin{aligned} q_i & = \begin{cases}1,& i=j,\\0,& i\ne j,\end{cases}\\ c_{\mathrm{answer}} & = \boxplus_{i=1}^{n}\left(x_i \odot \operatorname{Enc}_{pk}(q_i)\right). \end{aligned} \tag{4}

Here \odot denotes multiplication of a ciphertext by a plaintext database value. After decryption, the client obtains x_j. Packing, recursive query expansion, database preprocessing, and specialized encodings make practical systems more sophisticated than Equation 4.

Two broad PIR families have different trust assumptions:

• Information-theoretic multi-server PIR distributes queries among replicated, non-colluding servers. Privacy does not depend on a computational hardness assumption, but it does depend on at least one server not colluding with the others.
• Computational single-server PIR relies on cryptographic assumptions, often lattice-based HE, so one server can process an encrypted query.¹²

HE-based PIR can reduce communication compared with downloading the entire database, but the server may still perform substantial work. Performance depends on database dimensions, record size, batching, preprocessing, client storage, and whether the server must support updates. SealPIR is an influential research implementation built with Microsoft SEAL; its maintainers explicitly describe it as a research library rather than a production system.¹³

Candidate uses include retrieving a threat-intelligence indicator, patent record, software-update metadata entry, key-transparency record, or public catalog item without disclosing the selected index. The claim must remain precise: PIR hides which item is requested under its protocol assumptions; it does not make the client’s entire interaction anonymous or guarantee that the returned record is authentic.

Beyond HE

HE is best understood as a way to reduce where plaintext must exist. It can be transformative when the evaluator should not read its operands, but it does not remove trust from the client, key holders, output recipients, or surrounding protocol. It also converts an ordinary program into a constrained cryptographic computation whose security, correctness, and performance depend on parameters.

Challenges

1. Performance and ciphertext expansion. Ciphertext operations are far slower and larger than their plaintext equivalents. Rotations, multiplications, key switching, and bootstrapping can dominate runtime and memory. Packing many values into one ciphertext can improve throughput, but it may not reduce single-query latency.

2. Circuit design. Branches, comparisons, division, table lookups, nonlinear activations, and variable-length data are not equally efficient in every scheme. Developers often need polynomial approximations, fixed iteration counts, alternative data layouts, or a scheme specialized for Boolean gates and lookup tables.

3. Exactness and numerical error. BFV and BGV compute exact modular results, which can wrap if bounds are wrong. CKKS computes approximate results, so scales, rescaling, approximation error, and acceptable output tolerance must be analyzed together.

4. Parameter selection. Polynomial degree, ciphertext moduli, plaintext modulus, decomposition parameters, secret distribution, and circuit depth jointly affect security, correctness, and speed. Copying parameters from an unrelated benchmark can produce an insecure system or a computation that fails to decrypt correctly.

5. Key management and multi-owner data. A simple deployment uses one compatible key context, but collaborative systems may require threshold keys, multi-key evaluation, distributed key generation, key rotation, and a governed decryption protocol. A single shared secret key can become both an operational bottleneck and a concentration of risk.

6. No inherent proof of correct evaluation. A malicious or faulty evaluator can return the wrong ciphertext. Signatures authenticate messages, not the semantics of an encrypted computation. A blockchain provides an ordered log, not a proof of an opaque computation. Verifiable computation, zero-knowledge proofs, redundancy, or application-specific checks may be needed.

7. Residual leakage. Standard HE confidentiality does not necessarily hide the circuit, message dimensions, access pattern, timing, or resource use. It also does not control what decrypted outputs reveal. Circuit privacy, oblivious data access, traffic shaping, DP, and release governance address different portions of this leakage.

8. Endpoint and implementation security. Encryption and decryption endpoints still handle secrets. Random-number generation, serialization, malformed ciphertext handling, memory safety, side channels, and decryption-oracle behavior can invalidate a secure mathematical design.

9. Encrypted outputs. The evaluator normally returns ciphertext. That is a feature when only the data owner should learn the result, but it complicates workflows in which several parties need different output permissions. Threshold decryption, key switching, proxy re-encryption, or a separate access-control service may be required.

10. Interoperability and lifecycle management. Serialized formats, parameter identifiers, evaluation keys, versioning, long-term storage, and library upgrades must be planned. A ciphertext is not useful if the organization can no longer reconstruct its exact cryptographic context.

Future directions

Research and engineering are improving HE along several fronts:

• Faster bootstrapping and scheme switching reduce the cost of deep and mixed computations.
• Compilers and automatic parameter selection translate higher-level programs into circuits, optimize packing and rotations, and connect precision goals to concrete parameters.
• Hardware acceleration targets number-theoretic transforms, modular arithmetic, key switching, and memory movement on GPUs, FPGAs, and dedicated accelerators.
• Verifiable HE combines confidential evaluation with proofs that bind inputs, functions, and outputs.
• Multiparty and multi-key HE reduces reliance on one key holder and supports data owned by independent organizations.
• Circuit privacy and metadata-aware protocols aim to protect more than plaintext values.
• Hybrid privacy systems choose HE, MPC, DP, PIR, and TEEs per operation instead of forcing an entire application into one cryptographic model.
• Standards and security guidance are converging on shared terminology, parameter analysis, and safer implementation practices.¹⁴
• Developer tooling is making it easier to express, test, profile, and audit encrypted computations.

Many leading HE constructions are based on Learning With Errors or related lattice problems, for which no efficient classical or quantum attacks are currently known at properly selected parameters. That makes them candidates for post-quantum use, not a blanket guarantee. Concrete security estimates, future cryptanalysis, implementation quality, and parameter choices remain decisive.

Open-source libraries make serious prototypes possible. Microsoft SEAL supports BFV, BGV, and CKKS, while OpenFHE includes exact, approximate, and Boolean or lookup-table-oriented schemes. These libraries reduce implementation burden but do not choose the application threat model, numerical bounds, or disclosure policy for you.¹⁵

The most productive next step is a narrow prototype. Select one function, define who must not learn each input and output, choose an exact or approximate representation, measure multiplicative depth and rotations, select parameters using current security guidance, and benchmark the complete client-to-evaluator-to-client path. That process reveals whether HE is the right primitive and which complementary controls the application still needs.

Foundations of HE

The introduction established the purpose of homomorphic encryption: an evaluator can transform encrypted inputs without receiving the secret key or the underlying plaintext. We can now make that statement precise. The essential ideas come from algebra, circuit theory, randomized encryption, and lattice-based error management.

The word homomorphic refers to preservation of structure. Plaintext operations are represented by corresponding ciphertext operations, so that decrypting an evaluated ciphertext yields the result that the authorized computation would have produced on the plaintext. The idea of using such privacy homomorphisms for outsourced computation was already formulated in 1978, although secure and general constructions came much later.¹⁶

The mathematical vocabulary is compact, but several distinctions are crucial. An algebraic homomorphism is not automatically an encryption scheme; randomized encryption is not generally a single deterministic map; and support for addition and multiplication does not by itself make a construction fully homomorphic. Security, correctness, compactness, and a sustainable computation budget must all hold together.

Homomorphisms

Let (A,\circ) and (B,\bullet) be sets equipped with operations. A function h:A\rightarrow B is a homomorphism for those operations when it preserves their structure:

h(x\circ y)=h(x)\bullet h(y) \qquad \text{for all }x,y\in A. \tag{5}

The operations need not look identical. The operation \circ belongs to the source structure, while \bullet belongs to the target structure. What matters is that applying an operation before mapping gives the same mathematical result as mapping first and then applying the corresponding target operation.

A simple example is reduction modulo n. Define \pi_n:\mathbb{Z}\rightarrow\mathbb{Z}_n by \pi_n(a)=a\bmod n. Then:

\pi_n(a+b) =\pi_n(a)+\pi_n(b)\pmod n. \tag{6}

For n=7, adding 5 and 6 in the integers gives 11, while adding their residues gives 5+6\equiv4\pmod7. Reducing 11 modulo 7 also gives 4. The map preserves addition even though it changes the representation and loses information about the original integer.

This example isolates the algebraic idea but provides no secrecy. Anyone can reverse a small residue computation only to the extent allowed by the quotient, and no cryptographic hardness assumption is involved. An HE scheme adds randomized encoding, secret-key decryption, computational security, and an evaluation algorithm to this structural foundation.

Groups, rings, and fields

HE descriptions repeatedly use three algebraic structures:

• A group has one closed associative operation, an identity element, and an inverse for every element. If the operation is also commutative, the group is abelian.
• A ring has addition and multiplication. Its elements form an abelian group under addition, multiplication is associative, and multiplication distributes over addition. A ring need not allow division by every nonzero element.
• A field is a commutative ring in which every nonzero element has a multiplicative inverse. Familiar examples include the rational numbers and finite prime fields such as \mathbb{Z}_p for prime p.

General-purpose lattice HE commonly performs arithmetic in polynomial quotient rings. A typical ciphertext ring has the form:

R_q=\mathbb{Z}_q[X]/\langle \Phi(X)\rangle, \tag{7}

where coefficients are reduced modulo a ciphertext modulus q, and polynomials are reduced modulo a chosen polynomial \Phi(X). A common cyclotomic choice is \Phi(X)=X^N+1 when N is a power of two. Plaintexts live in a related space, such as R_t for an exact scheme or an encoded approximate space for CKKS.

The quotient-ring structure matters for two reasons. First, it makes polynomial addition and multiplication efficient. Second, suitable plaintext rings can be decomposed into independent slots through a Chinese-remainder representation, enabling SIMD-style batching. The resulting plaintext space may be a product of smaller rings or fields rather than a single field.

Many widely used HE schemes derive security from Learning With Errors or Ring Learning With Errors. At a high level, the public data contain linear or polynomial relations perturbed by small random error. Recovering the hidden secret, or distinguishing these samples from suitable random samples, is assumed to be computationally hard for appropriate parameters.¹⁷

The error is not an implementation defect. It is part of the security construction. Correctness requires it to remain within a decryptable range, while security requires parameters that resist the best known attacks.

From a homomorphism to an HE scheme

An HE scheme does not normally define encryption as a deterministic algebraic map. Encryption uses fresh randomness, so two encryptions of the same plaintext should generally differ. The homomorphic claim is therefore a statement about evaluation followed by decryption, not literal equality between a computed ciphertext and one particular fresh encryption.

For public parameters pp, keys (pk,sk,evk), messages m_1,\ldots,m_k, encryption randomness r_1,\ldots,r_k, and a supported circuit f, the workflow is:

1. pp\leftarrow\operatorname{ParamGen}(1^\lambda) selects public parameters for security parameter \lambda and the intended computation.
2. \operatorname{KeyGen}(pp) creates the secret key and the public or evaluation material required by the selected mode.
3. c_i\leftarrow\operatorname{Enc}_{pk}(m_i;r_i) encrypts each encoded message.
4. c_f\leftarrow\operatorname{Eval}_{evk}(f,c_1,\ldots,c_k) evaluates the circuit.
5. y\leftarrow\operatorname{Dec}_{sk}(c_f) recovers the result.

For an exact scheme, correctness requires:

\Pr\!\left[ \operatorname{Dec}_{sk}\!\left( \operatorname{Eval}_{evk}(f,c_1,\ldots,c_k) \right) =f(m_1,\ldots,m_k) \right] \geq 1-\operatorname{negl}(\lambda). \tag{8}

For an approximate scheme, the application instead needs a bound such as:

\left\| \operatorname{Decode}\!\left( \operatorname{Dec}_{sk}(c_f) \right) -f(m_1,\ldots,m_k) \right\| \leq \varepsilon_{\mathrm{app}}, \tag{9}

with the required probability and for a declared application tolerance \varepsilon_{\mathrm{app}}. That tolerance must include encoding error, polynomial-approximation error, homomorphic rounding, and any error already present in the input data.

The following diagram reuses the visual grammar defined in Table 1. Plaintext remains inside the trusted client, while the external evaluator receives ciphertexts and evaluation material.

flowchart TB
  subgraph Client[Trusted client]
    direction TB
    I[/Plaintext inputs/]:::plaintext
    K([Select parameters and generate keys]):::trusted
    E([Encode and encrypt inputs]):::trusted
    C[/Input ciphertexts/]:::ciphertext
    D([Decrypt and decode result]):::trusted
    O[/Plaintext result/]:::plaintext
    I --> E
    K --> E
    E --> C
    D --> O
  end
  subgraph Server[External evaluator]
    direction TB
    V[Evaluate circuit f]:::evaluator
    R[/Result ciphertext/]:::ciphertext
    V --> R
  end
  C --> V
  R --> D
  K -. Evaluation material .-> V

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 3: Algorithms and trust boundaries in a homomorphic-encryption workflow

Two further properties separate useful HE from a transcript of an ever-growing computation:

• Compactness: evaluated ciphertext size and decryption work are bounded independently of the evaluated circuit’s size, although they may depend on the security parameter, scheme parameters, and output representation.
• Security: ciphertexts hide their plaintexts under a defined adversarial experiment, normally with IND-CPA confidentiality as the baseline for ordinary HE.

Correctness, compactness, and security are distinct. A construction can preserve an operation and still fail to hide its messages; it can be secure but unable to evaluate the required depth; or it can return a correct value only by making decryption grow with the entire circuit.

Functional completeness

Homomorphic programs are represented as circuits over a selected gate basis. A basis is functionally complete when every function in the relevant finite computation model can be expressed using gates from that basis.

For Boolean circuits, XOR is addition in \mathrm{GF}(2) and AND is multiplication. The basis \{\operatorname{XOR},\operatorname{AND},1\} is functionally complete because negation can be derived from XOR with the constant 1:

\operatorname{NOT}(x)=1+x\pmod2. \tag{10}

NAND alone and NOR alone are also functionally complete. This is a statement about expressibility, not efficiency. A circuit may exist and still be too deep, too large, or too expensive to evaluate homomorphically.

For arithmetic circuits over a ring, addition and multiplication, together with allowed constants, generate polynomial functions. This does not imply that they directly implement every ordinary programming operation. Comparison, division, branching, sorting, table lookup, and transcendental functions need one or more of the following:

• a Boolean-circuit representation;
• a polynomial approximation over a bounded domain;
• a programmable lookup-table scheme;
• a different encoding or HE scheme; or
• an auxiliary MPC, TEE, or client-side step.

Over a finite field, every function from a finite field to itself has a polynomial representation, but the degree and circuit cost may be impractical. Over a general ring, not every set-theoretic function is necessarily a polynomial function. Expressibility must therefore be distinguished from an efficient circuit for the chosen scheme.

Supporting addition and multiplication is necessary for general arithmetic-circuit evaluation, but it is not sufficient to establish FHE:

• A somewhat homomorphic construction supports only a bounded circuit family.
• A leveled construction accepts a target maximum depth and selects parameters for that level budget, normally without bootstrapping.
• A fully homomorphic construction supports arbitrary finite circuits within the formal computation class, normally by bootstrapping when the remaining budget is insufficient.

Leveled FHE formalized the important result that any chosen finite depth can be supported with parameters that grow appropriately, without invoking bootstrapping during that evaluation.¹⁸

Functional completeness identifies a sufficient gate basis. FHE additionally requires a secure, correct, and compact evaluation mechanism whose supported depth is not permanently bounded by the initial ciphertext budget.

Secret-key and public-key modes

Many lattice HE schemes support both secret-key and public-key encryption modes.

• In secret-key mode, the data owner uses sk to create and decrypt ciphertexts.
• In public-key mode, authorized senders use pk to encrypt, while only the holder or holders of sk can decrypt.

This choice primarily determines who can create ciphertexts and how encryption authority is distributed. It does not usually change the core ciphertext representation used by the evaluator, so public-key evaluation is not generically slower merely because encryption was public-key.

Evaluation remains a separate capability. The evaluator receives the ciphertexts, parameters, circuit, and required evaluation keys, but not the secret decryption key. Public-key mode also does not make unrelated users’ ciphertexts automatically compatible. Inputs evaluated together must share compatible parameters and, in a conventional deployment, the same logical decryption context.

When independent data owners cannot accept one shared decryption authority, the protocol needs an explicit multiparty construction:

• Threshold HE distributes one logical secret key so that a threshold of parties must cooperate to decrypt.
• Multiparty HE adds distributed key generation and interactive operations around a shared scheme context.
• Multi-key HE evaluates ciphertexts under distinct keys and produces an output whose decryption involves the relevant owners.
• Key switching changes the decryption context only when suitable switching material has been generated; it is not an unrestricted conversion between arbitrary keys.

These are protocol properties, not automatic consequences of publishing an encryption key.

Operational components of an HE scheme

Parameters, encoding, and keys

An HE implementation must select a complete parameter set before it can generate usable keys. Depending on the scheme, this includes:

• security parameter and target security level;
• polynomial or ring dimension;
• ciphertext-modulus chain;
• plaintext modulus for exact arithmetic;
• scale and precision targets for approximate arithmetic;
• secret-key and error distributions;
• multiplicative depth, bootstrapping strategy, and supported rotations; and
• batching layout and expected input bounds.

Encoding and encryption are separate operations. Encoding maps application values into the scheme’s plaintext space. Encryption then protects that encoded plaintext. Decoding reverses the application representation after decryption. Incorrect bounds or encodings can produce modular wraparound, precision loss, or semantically meaningless outputs even when the cryptographic algorithms behave exactly as designed.

Key generation may produce several objects:

• sk, the secret decryption key;
• pk, an optional public encryption key;
• relinearization keys;
• rotation or Galois keys;
• key-switching material; and
• bootstrapping keys or other scheme-specific evaluation material.

These auxiliary keys are normally designed to be available to the evaluator under the scheme’s security assumptions. They are not equivalent to the secret key, but their authenticity, lifecycle, size, parameter binding, and permitted distribution still require control.

Evaluation keys

Evaluation keys enable particular ciphertext transformations:

• Relinearization keys reduce the number of ciphertext components after multiplication.
• Rotation or Galois keys enable automorphisms that permute packed slots.
• Key-switching keys convert a ciphertext from one compatible secret-key context to another specified context.
• Bootstrapping material supports the homomorphic refresh computation.

An implementation should generate only the evaluation keys required by the circuit. Rotation and bootstrapping keys can be large, and unnecessary key material increases storage, transfer, initialization time, and attack surface.

Noise, levels, and ciphertext maintenance

In exact schemes such as BFV and BGV, decryption succeeds while the ciphertext error remains within a scheme-dependent bound relative to the active modulus. Addition normally grows error moderately. Multiplication combines error terms, enlarges ciphertext structure, and consumes much more of the available computation margin.

In CKKS, approximate values and error occupy the same numerical representation. Multiplication increases the encoded scale, and rescaling reduces the scale and modulus while introducing controlled rounding. Correctness is therefore numerical rather than exact.¹⁹

The principal maintenance operations have different purposes:

Operation	Primary effect	What it does not do
Relinearization	Reduces ciphertext component count after multiplication	Erase accumulated error or restore consumed levels
Modulus switching	Moves a ciphertext to a lower modulus while controlling the scheme’s error relation	Return the ciphertext to its initial state
CKKS rescaling	Reduces scale and modulus after multiplication	Restore exact arithmetic
Bootstrapping	Homomorphically refreshes a ciphertext and restores computational capacity	Make computation free, prove correctness, or reduce error literally to zero

Table 4: Ciphertext-maintenance operations and their distinct effects.

Modulus switching and rescaling consume entries in a modulus chain, which is why implementations describe ciphertexts as occupying levels. Two operands may need compatible levels and scales before an operation can proceed. Relinearization keeps multiplication outputs manageable but does not reset their error.

Bootstrapping evaluates a decryption-like function homomorphically and returns a refreshed ciphertext under the required context. The evaluator never performs ordinary plaintext decryption. A leveled computation whose multiplicative depth fits the selected chain does not need bootstrapping, and avoiding it can substantially reduce latency.

Batching and rotations

Batching encodes multiple logical values into one plaintext and then into one ciphertext. Addition and multiplication act slotwise, creating SIMD-style parallelism. If a ciphertext contains s useful slots, one homomorphic operation can update as many as s logical values, subject to the packing layout and scheme.

Rotations permute those slots. They are necessary for summing a packed vector, computing dot products, implementing convolutions, and reorganizing matrices. Each permitted rotation normally requires compatible evaluation material, and rotations can dominate both runtime and key size.

Packing improves throughput when many values share the same circuit. It does not automatically improve the latency of one small request, and it can force the developer to redesign data layout around the algebra of available rotations.

Required security and correctness properties

A production design must evaluate separate properties rather than collapsing them into the single word secure:

• Message confidentiality: the scheme meets its stated indistinguishability definition for the selected adversary model.
• Correctness: exact outputs decrypt correctly except with the allowed negligible failure probability, or approximate outputs remain within a declared numerical tolerance.
• Compactness: evaluated ciphertext size and decryption work do not grow with the complete circuit history.
• Circuit privacy: the evaluated ciphertext does not reveal unintended information about the circuit to the decryptor. This property is optional and may require extra randomization or protocol steps.
• Integrity and verifiability: malformed inputs, substituted circuits, stale results, or incorrect evaluation can be detected. Ordinary HE does not provide this property.
• Metadata protection: sizes, parameters, timing, access frequency, and circuit topology are hidden to the degree required by the application. Ordinary HE leaves much of this metadata visible.

Parameter selection couples security, correctness, and performance. A larger ciphertext modulus gives the circuit more room, but for a fixed ring dimension it generally weakens the estimated lattice security. Preserving the security target may therefore require a larger ring dimension, which increases key size, ciphertext size, and computational cost.

The exact trade-off depends on the scheme, distributions, attack model, and circuit. Parameters should come from a maintained implementation and current security analysis rather than from a standalone key-size rule. The Homomorphic Encryption Standard provides common terminology, scheme descriptions, and parameter guidance that make this evaluation reproducible.²⁰

These foundations lead directly to the implementation problem: choose a plaintext model, express the target function as an efficient circuit, derive its depth and data-movement requirements, and only then select parameters and keys. The next sections can build on that order without treating HE configuration as a collection of independent tuning knobs.

Textbook RSA and multiplicative homomorphism

The preceding section distinguished an algebraic homomorphism from a secure randomized HE scheme. Textbook RSA is an ideal test of that distinction. Its core exponentiation map preserves multiplication exactly, but the resulting deterministic and malleable construction is not secure encryption and must not be deployed as HE.

The purpose of this section is therefore twofold. First, it develops the number-theoretic and group-theoretic tools needed to derive RSA from first principles. Second, it shows why an algebraically elegant ciphertext operation can be both mathematically correct and cryptographically unsafe.

Number-theoretic toolkit

Only a small part of elementary number theory is required for RSA. Each concept has a specific role.

Concept	Mathematical purpose	Role in textbook RSA
Prime factorization	Decomposes an integer into prime powers	The modulus is built as n=pq while its factors remain secret
Greatest common divisor	Tests whether two integers are coprime	The public exponent must be invertible modulo \lambda(n)
Bézout identity	Expresses a GCD as a linear combination	The extended Euclidean algorithm computes the private exponent
Congruence	Identifies integers with the same residue	Encryption and decryption operate modulo n
Modular exponentiation	Computes large powers without constructing the full integer	Both RSA primitives are modular exponentiations
Euler and Carmichael functions	Bound the orders of invertible residues	They determine the exponent relation that makes decryption correct
Chinese remainder theorem	Reconstructs a residue from residues modulo coprime factors	It proves correctness for every message and accelerates private-key operations

Table 5: Number-theoretic tools used in textbook RSA.

Divisibility, primes, and factorization

The integers are denoted by \mathbb{Z}. For a,b\in\mathbb{Z}, the notation a\mid b means that b=ac for some c\in\mathbb{Z}. If b>0, the division algorithm states that there are unique integers q and r such that:

a=qb+r, \qquad 0\leq r<b. \tag{11}

The remainder r is the canonical nonnegative value of a\bmod b. For example, 17=3\cdot5+2, so 17\bmod5=2.

An integer p>1 is prime when its only positive divisors are 1 and p. Every integer n>1 has a factorization:

n=\prod_{i=1}^{k}p_i^{e_i}, \tag{12}

where the p_i are distinct primes and the e_i are positive integers. The factorization is unique apart from the order of its factors.

Multiplying two known primes is efficient in their bit length. Recovering them from their product is a different computational problem. For general large integers, the general number field sieve has heuristic running time:

L_n\!\left[\frac13,\left(\frac{64}{9}\right)^{1/3}\right] = \exp\!\left( \left(\left(\frac{64}{9}\right)^{1/3}+o(1)\right) (\ln n)^{1/3}(\ln\ln n)^{2/3} \right). \tag{13}

This is subexponential, not exponential, in the bit length of n, but it is also superpolynomial. No polynomial-time classical factorization algorithm is known. That observation is evidence about present algorithms, not a proof that factoring is intrinsically hard.²¹

Factoring an RSA modulus is sufficient to recover its private key, but the converse statement is more delicate. The task of inverting the RSA power map on a challenge value is the RSA problem. No general proof shows that solving arbitrary RSA inversion instances is equivalent to factoring. The security assumption for an RSA-based construction must therefore be stated as the assumption actually used by that construction, not silently replaced by the factoring assumption.²²

Greatest common divisor, Bézout identity, and modular inverse

For integers a and b, not both zero, \gcd(a,b) is the unique positive integer that divides both and is divisible by every common divisor. The Euclidean algorithm follows from Equation 11:

\gcd(a,b)=\gcd\!\left(b,a\bmod b\right). \tag{14}

For a=385 and b=364, the successive remainders are 21, 7, and 0, so the last nonzero remainder is \gcd(385,364)=7. The signs of the inputs do not change the positive GCD.

Bézout identity states that integers x and y exist such that:

ax+by=\gcd(a,b). \tag{15}

The extended Euclidean algorithm computes the GCD and suitable coefficients by carrying the same quotient steps through three recurrences. If r_0=a, r_1=b, s_0=1, s_1=0, t_0=0, and t_1=1, then each iteration uses:

\begin{aligned} q_i&=\left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor,\\ r_{i+1}&=r_{i-1}-q_i r_i,\\ s_{i+1}&=s_{i-1}-q_i s_i,\\ t_{i+1}&=t_{i-1}-q_i t_i. \end{aligned} \tag{16}

The invariant is r_i=as_i+bt_i. For 48 and 18:

\begin{aligned} 48&=2\cdot18+12,\\ 18&=1\cdot12+6,\\ 12&=2\cdot6,\\ 6&=3\cdot18-48. \end{aligned} \tag{17}

Hence \gcd(48,18)=6 with one pair of Bézout coefficients (x,y)=(-1,3).

An integer a has a multiplicative inverse modulo n exactly when \gcd(a,n)=1. If Bézout gives ax+ny=1, reduction modulo n gives ax\equiv1\pmod n, so x is an inverse of a. Equivalently:

a^{-1}\bmod n = x\bmod n \quad\Longleftrightarrow\quad ax+ny=1. \tag{18}

The inverse is unique as a residue class modulo n. Exponentiation can also produce an inverse when the group order is known, but the extended Euclidean algorithm is normally the direct and less expensive method.

Congruence, residue rings, and units

For n>0, integers a and b are congruent modulo n when their difference is divisible by n:

a\equiv b\pmod n \quad\Longleftrightarrow\quad n\mid(a-b). \tag{19}

Congruence is an equivalence relation. Its classes form the quotient ring:

\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z} = \{[0]_n,[1]_n,\ldots,[n-1]_n\}. \tag{20}

The set on the right lists classes, not merely integers. In computations, the least nonnegative representatives 0,\ldots,n-1 are normally used. A centered representative can instead be chosen in an interval around zero; when n is even, the endpoint convention must be stated to resolve the tie at n/2.

Addition and multiplication are well defined on classes because congruent inputs produce congruent outputs:

\begin{aligned} (a+b)\bmod n &=\bigl((a\bmod n)+(b\bmod n)\bigr)\bmod n,\\ (ab)\bmod n &=\bigl((a\bmod n)(b\bmod n)\bigr)\bmod n. \end{aligned} \tag{21}

Not every nonzero element of \mathbb{Z}_n is invertible. The invertible classes form the unit group:

\mathbb{Z}_n^{*} = \{[a]_n:\gcd(a,n)=1\}. \tag{22}

This distinction is essential. The ring \mathbb{Z}_6 contains nonzero zero divisors because [2]_6[3]_6=[0]_6. Its unit group is only \{[1]_6,[5]_6\}. If p is prime, every nonzero class is a unit and \mathbb{Z}_p is a field.

Modular exponentiation

Computing the full integer a^b and reducing only at the end is unnecessary. Reduction can occur after every multiplication. If the binary expansion of a nonnegative exponent is b=(b_{\ell-1}\cdots b_1b_0)_2, left-to-right square-and-multiply initializes r_0=1 and processes the bits from most significant to least significant using:

r_{j+1}=r_j^2a^{b_{\ell-1-j}}\bmod n. \tag{23}

The method needs \mathcal{O}(\log b) modular squarings and multiplications. For 3^{13}\bmod7, the exponent bits are (1101)_2, and the accumulator evolves as:

1\longrightarrow3\longrightarrow6\longrightarrow1\longrightarrow3 \pmod7. \tag{24}

Thus 3^{13}\equiv3\pmod7. A right-to-left variant instead scans from the least significant bit while maintaining separate accumulator and current-power variables. Reversing a bit list does not by itself convert one algorithm into the other; the state update must change as well.

Euler, Carmichael, and multiplicative order

Euler’s totient \phi(n) counts the units modulo n, so |\mathbb{Z}_n^*|=\phi(n). If n=\prod_i p_i^{e_i}, then:

\phi(n) = n\prod_i\left(1-\frac{1}{p_i}\right). \tag{25}

Euler’s theorem and its Carmichael refinement state:

\begin{aligned} a^{\phi(n)}&\equiv1\pmod n,\\ a^{\lambda(n)}&\equiv1\pmod n, \end{aligned} \qquad \gcd(a,n)=1, \tag{26}

where \lambda(n) is the exponent of the finite abelian group \mathbb{Z}_n^*. It is the smallest positive integer that works simultaneously for every unit. For prime powers:

\lambda(p^k)= \begin{cases} \phi(p^k), & p\text{ odd, or }p=2\text{ and }k\leq2,\\ 2^{k-2}, & p=2\text{ and }k\geq3. \end{cases} \tag{27}

For pairwise coprime prime powers, the values combine by least common multiple. Therefore:

\lambda(18) = \operatorname{lcm}\!\left(\lambda(2),\lambda(3^2)\right) = \operatorname{lcm}(1,6) =6. \tag{28}

The value is not 3. Every unit modulo 18 has order dividing 6, but individual orders may be 1, 2, 3, or 6.

For a\in\mathbb{Z}_n^*, its multiplicative order is:

\operatorname{ord}_n(a) = \min\{k\geq1:a^k\equiv1\pmod n\}. \tag{29}

The order always divides \lambda(n) and therefore also divides \phi(n). Fermat’s little theorem establishes only that a^{p-1}\equiv1\pmod p for p\nmid a; it does not establish that the order of every such a equals p-1.

A composite integer n is a Carmichael number when a^{n-1}\equiv1\pmod n for every a coprime to n. Equivalently, \lambda(n)\mid n-1. For example, \lambda(561)=\operatorname{lcm}(2,10,16)=80, and 80\mid560. Consequently, a Fermat test can label a composite number as a probable prime even when many bases are tried.

Probable primes and cryptographic randomness

Trial division up to \sqrt n is correct but unsuitable for RSA-sized candidates. If n has b bits, \sqrt n is on the order of 2^{b/2}, so the number of trial divisors is exponential in the input length.

Miller–Rabin instead writes an odd candidate as n-1=2^s d with d odd and tests whether a selected base follows one of the exponent patterns that every odd prime must satisfy. If an odd composite candidate passes t independent uniformly selected tests, the standard worst-case error bound is at most 4^{-t}. In actual key generation, small-prime division and Miller–Rabin tests are combined according to a specified algorithm and error target.²³

Randomness is a separate requirement from primality. RSA key generation needs unpredictable candidate selection; randomized encryption needs fresh unpredictable coins for every encryption. A deterministic random bit generator can safely expand a seed only when the seed contains sufficient entropy, the internal state remains protected, reseeding is handled correctly, and the construction provides the required prediction resistance. Statistical uniformity alone does not provide these security properties.²⁴

Chinese remainder theorem

If n_1,\ldots,n_k are pairwise coprime and N=\prod_i n_i, the Chinese remainder theorem gives a ring isomorphism:

\mathbb{Z}_N \cong \mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_k}. \tag{30}

For prescribed residues r_i, let M_i=N/n_i and let u_i=M_i^{-1}\bmod n_i. The unique solution modulo N is:

x \equiv \sum_{i=1}^{k}r_iM_i u_i \pmod N. \tag{31}

Consider x\equiv4\pmod9, x\equiv7\pmod{13}, and x\equiv2\pmod{17}. Here N=1989, while (M_1,M_2,M_3)=(221,153,117) and (u_1,u_2,u_3)=(2,4,8). Therefore:

\begin{aligned} x &\equiv4\cdot221\cdot2 +7\cdot153\cdot4 +2\cdot117\cdot8 \pmod{1989}\\ &\equiv7924 \equiv1957 \pmod{1989}. \end{aligned} \tag{32}

Direct reduction verifies that 1957 has residues 4, 7, and 2 under the three moduli. The theorem is central to RSA because a statement proved modulo both secret primes p and q is then true modulo n=pq.

Group theory specialized to RSA

The previous section introduced groups in general. RSA uses one specific finite abelian group, \mathbb{Z}_n^*, and the multiplicative monoid of all residues \mathbb{Z}_n.

The order of a finite group G is its number of elements |G|. The order of an element is the size of the cyclic subgroup it generates. Lagrange’s theorem implies that an element order divides |G|. For \mathbb{Z}_n^*, the stronger common bound is the group exponent \lambda(n).

A group is cyclic when some element g generates every element through repeated application of the operation. Such an element has order |G|. The group \mathbb{Z}_p^* is cyclic for every prime p, but not every unit group \mathbb{Z}_n^* is cyclic. Primitive roots modulo n exist only for a restricted family of moduli, so a generic unit must not be called a generator merely because its powers eventually return to 1.

For example, 3 generates \mathbb{Z}_7^* because:

3^1,3^2,3^3,3^4,3^5,3^6 \equiv 3,2,6,4,5,1 \pmod7. \tag{33}

A group homomorphism h:G\to H preserves the respective operations:

h(x\star y)=h(x)\circ h(y). \tag{34}

Because \mathbb{Z}_n^* is abelian, the power map P_e(m)=m^e\bmod n is a group homomorphism:

P_e(m_1m_2) =(m_1m_2)^e =m_1^em_2^e =P_e(m_1)P_e(m_2) \pmod n. \tag{35}

The same identity holds on all of \mathbb{Z}_n, where it defines a homomorphism of the multiplicative monoid even though nonunits have no multiplicative inverses. If \gcd(e,\lambda(n))=1, there is a d such that ed\equiv1\pmod{\lambda(n)}. The inverse of P_e on \mathbb{Z}_n^* is then P_d, making P_e an automorphism. This group-theoretic fact is the core of textbook RSA.

Constructing textbook RSA

Rivest, Shamir, and Adleman introduced RSA as a public-key construction in 1978.²⁵ In its basic two-prime form, key generation proceeds as follows:

1. Select distinct odd primes p and q using a specified cryptographic random-prime generation procedure.
2. Compute n=pq and \lambda(n)=\operatorname{lcm}(p-1,q-1).
3. Select a public exponent e satisfying 1<e<\lambda(n) and \gcd(e,\lambda(n))=1.
4. Compute the private exponent d=e^{-1}\bmod\lambda(n).
5. Publish (n,e) and keep d, p, q, and any CRT parameters secret.

The defining exponent relation is:

ed=1+k\lambda(n) \tag{36}

for some integer k. The textbook encryption and decryption maps on an integer representative in \{0,\ldots,n-1\} are:

\begin{aligned} \operatorname{Enc}_{(n,e)}(m)&=m^e\bmod n,\\ \operatorname{Dec}_{(n,d)}(c)&=c^d\bmod n. \end{aligned} \tag{37}

Correctness

If m\in\mathbb{Z}_n^*, Carmichael’s theorem and Equation 36 give:

m^{ed} = m^{1+k\lambda(n)} = m\left(m^{\lambda(n)}\right)^k \equiv m \pmod n. \tag{38}

Correctness also holds when m is not a unit. Modulo p, either p\mid m, in which case both m^{ed} and m are zero, or p\nmid m, in which case Fermat’s theorem and ed\equiv1\pmod{p-1} give m^{ed}\equiv m\pmod p. The same argument holds modulo q. The Chinese remainder theorem then gives:

m^{ed}\equiv m\pmod{pq} \tag{39}

for every message representative m\in\mathbb{Z}_n.

Multiplicative homomorphism

For textbook RSA ciphertexts c_1=m_1^e\bmod n and c_2=m_2^e\bmod n:

\begin{aligned} c_1c_2\bmod n &=m_1^em_2^e\bmod n\\ &=(m_1m_2)^e\bmod n\\ &=\operatorname{Enc}_{(n,e)}(m_1m_2\bmod n). \end{aligned} \tag{40}

This is literal ciphertext equality because textbook RSA is deterministic. It is not the probabilistic correctness relation used by modern randomized HE.

Consider the deliberately insecure toy parameters p=5, q=11, n=55, \lambda(n)=20, e=3, and d=7. For m_1=2 and m_2=3:

\begin{aligned} c_1&=2^3\bmod55=8,\\ c_2&=3^3\bmod55=27,\\ c_1c_2\bmod55&=8\cdot27\bmod55=51,\\ \operatorname{Enc}(2\cdot3)&=6^3\bmod55=51,\\ \operatorname{Dec}(51)&=51^7\bmod55=6. \end{aligned} \tag{41}

The following diagram uses the visual grammar defined in Table 1. It depicts only the textbook primitive, not a secure RSA encryption protocol.

flowchart TB
  subgraph Client[Trusted client]
    direction TB
    P[/Plaintexts m1 and m2/]:::plaintext
    K([Generate textbook RSA keys]):::trusted
    E([Apply public exponent e]):::trusted
    C[/Ciphertexts c1 and c2/]:::ciphertext
    D([Apply private exponent d]):::trusted
    O[/Product m1 m2 modulo n/]:::plaintext
    P --> E
    K --> E
    E --> C
    D --> O
  end
  subgraph Server[External evaluator]
    direction TB
    M[Multiply ciphertexts modulo n]:::evaluator
    R[/Product ciphertext/]:::ciphertext
    M --> R
  end
  C --> M
  R --> D
  K -. Public modulus n .-> M

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 4: Multiplicative evaluation with the deterministic textbook RSA primitive

Why deployed RSA encryption is not homomorphic encryption

The same equation that makes textbook RSA an elegant algebraic example also exposes its cryptographic defects.

Determinism. A fixed message under a fixed key always produces the same ciphertext. An adversary can test guesses by encrypting candidate messages and comparing the results. Textbook RSA therefore fails even the baseline indistinguishability expected of modern encryption.

Unrestricted multiplicative malleability. Given a ciphertext c=m^e\bmod n and any chosen unit r, an evaluator can create c'=c\,r^e\bmod n. Decryption returns mr\bmod n. This is useful only when the protocol explicitly authorizes the transformation and controls its consequences. In ordinary encryption, it is an attack surface.

Narrow functionality. Textbook RSA preserves multiplication. It does not natively provide plaintext addition, arbitrary arithmetic circuits, batching, level management, or bootstrapping. It is partially homomorphic in the algebraic sense, not fully homomorphic.

Secure encoding breaks the simple relation. RSA encryption standards combine the RSA exponentiation primitive with a randomized encoding such as OAEP. The encoder maps a message and fresh randomness to an integer representative before exponentiation. Consequently, multiplying two RSA-OAEP ciphertexts does not produce a valid RSA-OAEP encryption of the product of their source messages. This loss of homomorphism is intentional.²⁶

Construction	Randomized encryption	Simple multiplicative relation	Intended interpretation
Textbook RSA exponentiation	No	Yes	Mathematical primitive and unsafe teaching example
RSAES-OAEP	Yes	No	RSA-based encryption scheme with a defined security analysis
Purpose-built randomized HE	Normally yes	Only through its specified evaluation algorithms	Controlled computation under an explicit correctness and security model

Table 6: Textbook RSA, secure RSA encoding, and purpose-built HE are different constructions.

The correct implementation rule is categorical: never remove a secure RSA encoding to recover the textbook multiplicative property. If an application requires encrypted computation, it should use a purpose-built HE scheme whose security definition already accounts for its authorized malleability.

Residuosity assumptions used by adjacent schemes

Quadratic and higher-order residues are not needed to derive RSA’s multiplicative homomorphism. They matter because other partially homomorphic schemes use related power maps and decisional assumptions.

For an odd prime p, a nonzero a is a quadratic residue when a=x^2\bmod p for some x. Euler’s criterion states:

a^{(p-1)/2} \equiv \begin{cases} 1\pmod p, & a\text{ is a quadratic residue},\\ -1\pmod p, & a\text{ is a quadratic non-residue}. \end{cases} \tag{42}

The Legendre symbol records these cases for a prime modulus. The Jacobi symbol extends multiplicatively to odd composite moduli, but a Jacobi value of 1 does not prove that the value is a square modulo the composite. Goldwasser–Micali encryption exploits a decisional quadratic-residuosity problem under a carefully selected composite modulus; the hardness claim is scheme- and distribution-specific, not a generic theorem about every composite.²⁷

More generally, for a finite abelian group G, the map \rho_r(x)=x^r is a homomorphism. Its image is the subgroup of rth powers, and its kernel is the subgroup of rth roots of the identity. Every element in the image has exactly |\ker\rho_r| preimages:

|\rho_r^{-1}(y)|=|\ker\rho_r| \qquad \text{for every }y\in\operatorname{im}\rho_r. \tag{43}

The number of roots is therefore not generically equal to r. If \gcd(r,\lambda(n))=1, the power map on \mathbb{Z}_n^* is an automorphism, so every unit has exactly one rth root.

Paillier encryption uses nth-power residue classes in \mathbb{Z}_{n^2}^* and a decisional composite-residuosity assumption. Its randomized ciphertext multiplication corresponds to plaintext addition modulo n, which is structurally different from textbook RSA’s deterministic multiplication of plaintexts.²⁸

What the RSA example contributes to HE

Textbook RSA does not provide a deployment path to modern HE, but it establishes several durable design principles:

1. Name the algebraic domain. A statement over \mathbb{Z}_n, its multiplicative monoid, and its unit group \mathbb{Z}_n^* can have different scope.
2. Separate the primitive from the encryption scheme. Modular exponentiation is a primitive; an encoding plus that primitive forms an RSA encryption scheme.
3. State correctness at the right layer. Deterministic textbook RSA permits literal ciphertext equality, whereas randomized HE normally states correctness after evaluation and decryption.
4. Treat malleability as an authorized capability. A ciphertext transformation is useful only when the security model says who may perform it, which functions are allowed, and what the output may reveal.
5. Do not infer security from algebra. A homomorphism can coexist with determinism, dictionary attacks, chosen-ciphertext attacks, or an inadequate parameter generator.
6. Use assumptions precisely. Factoring, RSA inversion, quadratic residuosity, and composite residuosity are related but distinct computational problems.

The next useful step is to examine a randomized scheme whose homomorphic operation is part of its intended security model. That transition makes clear why modern HE is not obtained by taking an ordinary encryption system and merely exposing one convenient algebraic identity.

Executable textbook RSA lab

The preceding section derived textbook RSA as a power-map automorphism and proved its multiplicative identity. This section turns that identity into a small, auditable program. It does not introduce a second RSA construction, and it does not repeat the deployment guidance already established.

The parameters are intentionally tiny and insecure. The purpose is to trace four algorithms:

1. generate a toy key pair;
2. encrypt two integer representatives;
3. multiply the ciphertexts without decrypting them;
4. decrypt the evaluated ciphertext and compare the result with the modular plaintext product.

The contract under test is:

\operatorname{Dec}_{d} \left( \operatorname{Eval}_{\times} \left( \operatorname{Enc}_{e}(m_1), \operatorname{Enc}_{e}(m_2) \right) \right) \equiv m_1m_2 \pmod n. \tag{44}

This relation concerns the deterministic textbook primitive. It is not a security claim about RSAES-OAEP or any deployed RSA encryption protocol.

Keep the algorithm boundaries visible

The actor boundary is the same one shown in Figure 4. Plaintext handling and private-key operations remain inside the trusted environment, while the external evaluator receives ciphertexts and public context only.

Algorithm	Input	Output	Required knowledge
\operatorname{KeyGen}	Distinct primes p,q and exponent e	Public key (n,e) and private material	Prime factors and cryptographic randomness
\operatorname{Enc}	Public key and m\in\mathbb{Z}_n	c=m^e\bmod n	Public key and plaintext
\operatorname{Eval}_{\times}	Public modulus and ciphertexts c_1,c_2	c_{\mathrm{mul}}=c_1c_2\bmod n	Public context and ciphertexts only
\operatorname{Dec}	Private material and c_{\mathrm{mul}}	m_{\mathrm{mul}}=c_{\mathrm{mul}}^d\bmod n	Private exponent or equivalent CRT material

Table 7: Inputs, outputs, and trust boundaries in the textbook RSA lab.

Although the public exponent permits anyone to perform the exponentiation, encryption must occur wherever the source plaintext is allowed to exist. Public-key availability does not make a plaintext-handling environment trusted.

Derive the toy key

Choose:

p=11, \qquad q=13, \qquad n=pq=143. \tag{45}

As in the preceding section, use Carmichael’s function:

\lambda(n) = \operatorname{lcm}(p-1,q-1) = \operatorname{lcm}(10,12) = 60. \tag{46}

Select e=7. Because \gcd(7,60)=1, the inverse of e modulo \lambda(n) exists. The extended Euclidean relation

1=43\cdot7-5\cdot60 \tag{47}

gives:

d=43, \qquad ed=7\cdot43=301\equiv1\pmod{60}. \tag{48}

One can instead compute with Euler’s totient \phi(n)=120. That choice gives d=103 because 7\cdot103\equiv1\pmod{120}. It is also valid for this key. In fact, 103\equiv43\pmod{60}, so both exponents satisfy the required congruence modulo \lambda(n). This lab uses d=43 to remain consistent with the key derivation in the preceding section.

The public key is (143,7). For this simplified presentation, the private operation uses (143,43). A real implementation normally retains additional private structure, including CRT parameters, and protects all equivalent private representations.

Trace the multiplicative evaluation

Let:

m_1=5, \qquad m_2=7, \qquad m_1m_2\bmod143=35. \tag{49}

Encrypt each representative:

\begin{aligned} c_1&=5^7\bmod143=47,\\ c_2&=7^7\bmod143=6. \end{aligned} \tag{50}

The external evaluator multiplies the ciphertexts modulo n:

c_{\mathrm{mul}} = 47\cdot6\bmod143 = 139. \tag{51}

Directly encrypting the modular plaintext product produces the same deterministic ciphertext:

35^7\bmod143=139. \tag{52}

Finally, decrypt the evaluated ciphertext:

139^{43}\bmod143=35. \tag{53}

Stage	Computation	Result
Public modulus	11\cdot13	143
Group exponent	\operatorname{lcm}(10,12)	60
Private exponent	7^{-1}\bmod60	43
First ciphertext	5^7\bmod143	47
Second ciphertext	7^7\bmod143	6
Evaluated ciphertext	47\cdot6\bmod143	139
Direct encryption check	35^7\bmod143	139
Decrypted result	139^{43}\bmod143	35

Table 8: Complete arithmetic trace for the corrected textbook RSA example.

The equality between the two ciphertext values is stronger than the usual correctness statement for randomized HE. It occurs only because textbook RSA encryption is deterministic:

\operatorname{Eval}_{\times}(c_1,c_2) = c_1c_2\bmod n = \operatorname{Enc}_{e}(m_1m_2\bmod n). \tag{54}

Run the example

The program below derives the key instead of hard-coding d, checks every message representative for round-trip correctness, and verifies the multiplicative relation. Python’s three-argument form of pow performs modular exponentiation without constructing the full intermediate power.

Listing 1

from math import gcd, lcm


def modular_inverse(value, modulus):
    old_r, r = value, modulus
    old_s, s = 1, 0

    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s

    if old_r != 1:
        raise ValueError

    return old_s % modulus


p, q = 11, 13
n = p * q
lambda_n = lcm(p - 1, q - 1)

e = 7
assert gcd(e, lambda_n) == 1
d = modular_inverse(e, lambda_n)
assert (e * d) % lambda_n == 1

m1, m2 = 5, 7
assert 0 <= m1 < n
assert 0 <= m2 < n

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

c_evaluated = (c1 * c2) % n
m_evaluated = pow(c_evaluated, d, n)

m_expected = (m1 * m2) % n
c_direct = pow(m_expected, e, n)

assert m_evaluated == m_expected
assert c_evaluated == c_direct

for message in range(n):
    ciphertext = pow(message, e, n)
    assert pow(ciphertext, d, n) == message

for left in range(n):
    for right in range(n):
        left_ciphertext = pow(left, e, n)
        right_ciphertext = pow(right, e, n)
        evaluated = (left_ciphertext * right_ciphertext) % n
        direct = pow((left * right) % n, e, n)
        assert evaluated == direct

print(n, lambda_n, e, d)
print(c1, c2, c_evaluated, m_evaluated)

143 60 7 43
47 6 139 35

The output is:

143 60 7 43
47 6 139 35

The exhaustive checks are feasible only because n=143. For realistic parameters, tests must combine known-answer vectors, boundary cases, property-based samples, negative tests, and the implementation’s established conformance suite.

Interpret the result precisely

The trace establishes four facts.

1. Correctness covers all representatives in this toy domain. The round-trip loop checks every m\in\mathbb{Z}_{143}, including nonunits such as 11 and 13.
2. Evaluation requires no private exponent. The evaluator computes one modular multiplication using n, c_1, and c_2.
3. The plaintext operation is modular. Decryption returns m_1m_2\bmod n, not an unbounded integer product. The value is 35 here because 5\cdot7<n.
4. The equality is algebraic, not evidence of confidentiality. The tests prove implementation properties for the selected domain; they do not establish semantic security, resistance to active attacks, or safe protocol composition.

The phrase partially homomorphic therefore needs qualification. Textbook RSA preserves one operation, multiplication modulo n, but it is deterministic and malleable. It is a useful algebraic example, not a secure PHE deployment.

Preserve the production boundary

Production RSA separates low-level exponentiation primitives from complete encryption and signature schemes. RSAES-OAEP applies a randomized encoding before the RSA encryption primitive. Its ciphertexts do not retain the simple product relation used in this lab. RSA signatures likewise use dedicated signature encodings and algorithms; signing is not accurately described as ordinary encryption with the private key.²⁹

Consequently:

• never use these toy parameters outside the lab;
• never process application data with raw textbook RSA;
• never remove a secure encoding to recover multiplicative behavior;
• never infer message integrity or evaluator correctness from the homomorphic identity;
• use a purpose-built HE scheme when encrypted evaluation is an application requirement.

This executable trace completes the textbook RSA example. The next construction should add what raw RSA lacks: randomized encryption whose supported evaluation operation is part of an explicit correctness and security model.

Programming leveled HE with Microsoft SEAL

The textbook RSA lab exposed one multiplicative identity. A useful HE program must go further: it must select an arithmetic model, encode application values, generate the evaluation material required by the circuit, run the circuit without the secret key, and verify that the decrypted result has the intended meaning.

This section implements that workflow with BFV and Microsoft SEAL. BFV is suitable here because the application requires exact integer arithmetic. The example adds and multiplies packed integer vectors, then evaluates three sequential squarings. It is intentionally a leveled HE example: the parameters reserve enough capacity for a bounded circuit, and the program performs no bootstrapping. Calling the program fully homomorphic without that qualification would hide the central engineering constraint.

Microsoft SEAL’s supported library is written in C++ and also provides a .NET wrapper. The Python package used below, SEAL-Python, is a community-maintained binding rather than an official Microsoft binding. As of August 2026, the current Python package exposes SEAL 4.4.0, while the official C++ project has reached 4.4.3.³⁰³¹ This version distinction is acceptable for a learning environment but must be reviewed before production use.

Define the computation before choosing parameters

The application will process two vectors:

\begin{aligned} \mathbf{x}&=(12,5,7,9),\\ \mathbf{y}&=(23,3,4,11). \end{aligned} \tag{55}

BFV represents each slot as an element of \mathbb{Z}_t, where t is the plaintext modulus. For each slot i, the expected contracts are:

\begin{aligned} \operatorname{Dec} \left( \operatorname{Eval}_{+} \left( \operatorname{Enc}(\mathbf{x}), \operatorname{Enc}(\mathbf{y}) \right) \right)_i &= (x_i+y_i)\bmod t,\\ \operatorname{Dec} \left( \operatorname{Eval}_{\times} \left( \operatorname{Enc}(\mathbf{x}), \operatorname{Enc}(\mathbf{y}) \right) \right)_i &= x_iy_i\bmod t. \end{aligned} \tag{56}

The second experiment starts with (2,3,4,5) and performs three sequential squarings:

x \longrightarrow x^2 \longrightarrow x^4 \longrightarrow x^8. \tag{57}

This circuit has multiplicative depth three. It performs seven conceptual multiplications if x^8 is expanded naively, but repeated squaring arranges them into three dependent layers. HE parameter selection depends primarily on those dependent layers, not merely on the total operation count.

Choose an installation path deliberately

Create an isolated environment so that the wrapper version and its numerical dependency are explicit:

python -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install "seal-python==4.4.0" "numpy>=1.24,<3"
python -m pip check
python -c "import seal; print(seal.__version__)"

On Windows PowerShell, activate the environment with:

.venv\Scripts\Activate.ps1

The version check should print:

4.4.0

Do not substitute pip install seal. The package named seal on the Python Package Index is an unrelated Hadoop-based bioinformatics toolkit.³² If no wheel exists for the operating system, processor architecture, and Python version in use, follow the SEAL-Python source-build instructions and pin both the wrapper commit and its Microsoft SEAL submodule.

For an application whose assurance depends directly on Microsoft-supported code, use the official C++ library, pin an approved release, and reproduce the same circuit through the native API. The Python example remains valuable because its objects and operations closely expose the underlying SEAL concepts.

Map code objects to the trust model

The code should not be read as one monolithic local function. Its objects belong to different trust domains:

Object	Normal owner	Secret	Purpose
Encryption parameters and SEAL context	Client and evaluator	No	Define the scheme, arithmetic domain, and compatible parameter identifiers
Public key	Plaintext owner or encrypting client	No	Encrypt new inputs under the selected key
Relinearization keys	Evaluator	No, but access should still be governed	Reduce ciphertext size after multiplication
Input and result ciphertexts	Client and evaluator	No plaintext content by design	Carry encrypted inputs and outputs
Secret key	Decrypting client only	Yes	Decrypt results and create secret-key-dependent diagnostics
Decryptor	Decrypting client only	Uses the secret key	Recover plaintexts and inspect local test ciphertexts

Table 9: Microsoft SEAL objects and their intended trust domains.

The workflow uses the visual grammar defined in Table 1. The evaluator receives public context, evaluation keys, and ciphertexts; it never receives the secret key.

flowchart TB
  subgraph Client[Trusted client]
    direction TB
    P[/Integer vectors/]:::plaintext
    K([Validate parameters and generate keys]):::trusted
    N([Encode and encrypt]):::trusted
    C[/Input ciphertexts/]:::ciphertext
    D([Decrypt decode and verify]):::trusted
    O[/Verified result/]:::plaintext
    P --> N
    K --> N
    N --> C
    K --> D
    D --> O
  end
  subgraph Service[External evaluator]
    direction TB
    E[Add multiply and relinearize]:::evaluator
    R[/Result ciphertexts/]:::ciphertext
    E --> R
  end
  C --> E
  K -. Public context and evaluation keys .-> E
  R --> D

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 5: Trusted-client and external-evaluator workflow for the BFV example

The single-process program below preserves these logical boundaries for readability. A later experiment can move the evaluator into another process without changing the circuit.

Understand the demonstration parameters

The program selects the following values:

Parameter	Demonstration value	Operational meaning
Scheme	BFV	Exact addition and multiplication in a modular plaintext ring
Polynomial modulus degree N	8192	Determines ring dimension, batching capacity, ciphertext size, and the safe coefficient-modulus limit
Coefficient modulus q	SEAL BFV default for N=8192 at 128-bit target security	Determines much of the available noise budget; increasing it without increasing N can invalidate the security target
Plaintext modulus t	A 20-bit batching prime	Defines arithmetic modulo t and satisfies the congruence required by the batch encoder
Slot count	8192	Number of integers processed in parallel by one packed ciphertext
Tested multiplicative depth	3	Three dependent squarings, ending at x^8

Table 10: Demonstration parameters and the engineering property controlled by each one.

These are teaching parameters, not a reusable production profile. The key points are:

• N must be a supported power of two.
• The coefficient modulus and N jointly constrain security and computational capacity.
• The plaintext modulus does not define an ordinary maximum integer. It defines modular arithmetic.
• A batching-compatible t permits N slots, but operations remain slotwise until rotations and cross-slot reductions are added.
• The context must validate the complete parameter set before key generation.

For this run, the helper selects t=1{,}032{,}193. The visible values and products are smaller than t, so their modular representatives equal their ordinary nonnegative values.

Run an exact BFV workflow

Save the following program as bfv_demo.py:

import seal


def make_bfv_context():
    poly_modulus_degree = 8192

    parameters = seal.EncryptionParameters(seal.scheme_type.bfv)
    parameters.set_poly_modulus_degree(poly_modulus_degree)
    parameters.set_coeff_modulus(
        seal.CoeffModulus.BFVDefault(
            poly_modulus_degree,
            seal.sec_level_type.tc128,
        )
    )
    parameters.set_plain_modulus(
        seal.PlainModulus.Batching(poly_modulus_degree, 20)
    )

    context = seal.SEALContext(
        parameters,
        True,
        seal.sec_level_type.tc128,
    )

    if not context.parameters_set():
        raise RuntimeError(context.parameter_error_message())

    if not context.first_context_data().qualifiers().using_batching:
        raise RuntimeError

    return parameters, context


def decode_unsigned(decryptor, encoder, ciphertext):
    plaintext = decryptor.decrypt(ciphertext)
    return encoder.decode_uint64(plaintext)


def main():
    parameters, context = make_bfv_context()
    plaintext_modulus = parameters.plain_modulus().value()

    key_generator = seal.KeyGenerator(context)
    secret_key = key_generator.secret_key()
    public_key = key_generator.create_public_key()
    relinearization_keys = key_generator.create_relin_keys()

    encryptor = seal.Encryptor(context, public_key)
    evaluator = seal.Evaluator(context)
    decryptor = seal.Decryptor(context, secret_key)
    encoder = seal.BatchEncoder(context)

    slot_count = encoder.slot_count()
    left_values = [0] * slot_count
    right_values = [0] * slot_count
    left_values[:4] = [12, 5, 7, 9]
    right_values[:4] = [23, 3, 4, 11]

    left_ciphertext = encryptor.encrypt(
        encoder.encode(left_values)
    )
    right_ciphertext = encryptor.encrypt(
        encoder.encode(right_values)
    )

    fresh_noise_budget = min(
        decryptor.invariant_noise_budget(left_ciphertext),
        decryptor.invariant_noise_budget(right_ciphertext),
    )

    sum_ciphertext = evaluator.add(
        left_ciphertext,
        right_ciphertext,
    )
    product_ciphertext = evaluator.multiply(
        left_ciphertext,
        right_ciphertext,
    )

    product_size_before = product_ciphertext.size()
    evaluator.relinearize_inplace(
        product_ciphertext,
        relinearization_keys,
    )
    product_size_after = product_ciphertext.size()

    sum_noise_budget = decryptor.invariant_noise_budget(
        sum_ciphertext
    )
    product_noise_budget = decryptor.invariant_noise_budget(
        product_ciphertext
    )

    decoded_sum = [
        int(value)
        for value in decode_unsigned(
            decryptor,
            encoder,
            sum_ciphertext,
        )[:4]
    ]
    decoded_product = [
        int(value)
        for value in decode_unsigned(
            decryptor,
            encoder,
            product_ciphertext,
        )[:4]
    ]

    expected_sum = [
        (left + right) % plaintext_modulus
        for left, right in zip(
            left_values[:4],
            right_values[:4],
        )
    ]
    expected_product = [
        (left * right) % plaintext_modulus
        for left, right in zip(
            left_values[:4],
            right_values[:4],
        )
    ]

    assert decoded_sum == expected_sum
    assert decoded_product == expected_product
    assert product_size_before == 3
    assert product_size_after == 2

    depth_values = [0] * slot_count
    depth_values[:4] = [2, 3, 4, 5]
    depth_ciphertext = encryptor.encrypt(
        encoder.encode(depth_values)
    )

    depth_noise_budgets = [
        decryptor.invariant_noise_budget(depth_ciphertext)
    ]
    sizes_before_relinearization = []

    for _ in range(3):
        evaluator.square_inplace(depth_ciphertext)
        sizes_before_relinearization.append(
            depth_ciphertext.size()
        )
        evaluator.relinearize_inplace(
            depth_ciphertext,
            relinearization_keys,
        )
        depth_noise_budgets.append(
            decryptor.invariant_noise_budget(depth_ciphertext)
        )

    decoded_depth = [
        int(value)
        for value in decode_unsigned(
            decryptor,
            encoder,
            depth_ciphertext,
        )[:4]
    ]
    expected_depth = [
        pow(value, 8, plaintext_modulus)
        for value in depth_values[:4]
    ]

    assert decoded_depth == expected_depth
    assert all(
        size == 3
        for size in sizes_before_relinearization
    )
    assert depth_ciphertext.size() == 2
    assert depth_noise_budgets[-1] > 0

    print(f"SEAL-Python version: {seal.__version__}")
    print(
        "Polynomial modulus degree:"
        f" {parameters.poly_modulus_degree()}"
    )
    print(f"Plaintext modulus: {plaintext_modulus}")
    print(f"Batching slots: {slot_count}")
    print(f"Decoded sums: {decoded_sum}")
    print(f"Decoded products: {decoded_product}")
    print(
        "Ciphertext size around relinearization:"
        f" {product_size_before} -> {product_size_after}"
    )
    print(
        "Noise budget for fresh, sum, and product ciphertexts:"
        f" {fresh_noise_budget}, {sum_noise_budget},"
        f" {product_noise_budget}"
    )
    print(f"Decoded x^8 values: {decoded_depth}")
    print(
        "Noise budget across depth 0 to 3:"
        f" {depth_noise_budgets}"
    )


if __name__ == "__main__":
    main()

The numbered regions implement the following responsibilities:

1. Select a batching-compatible plaintext modulus. The helper chooses a 20-bit prime satisfying the algebraic requirement of BFV batching.
2. Reject invalid contexts. A parameter object is not usable merely because its setters accepted the values.
3. Generate each key type once. The relinearization keys are evaluation material; they are not regenerated inside the multiplication loop.
4. Create complete slot vectors. Only the first four slots carry application values; the remaining slots are explicitly zero.
5. Encode before encrypting. Encoding maps an application vector into a BFV plaintext. Encryption then randomizes that plaintext into a ciphertext.
6. Evaluate without decrypting. Addition and multiplication consume ciphertexts and produce new ciphertexts.
7. Relinearize the product. Multiplying two size-two ciphertexts produces a size-three ciphertext. Relinearization returns it to size two.
8. Decrypt and decode at the client. The unsigned decoder exposes canonical residues in \{0,\ldots,t-1\}.
9. Assert semantics, not merely successful execution. A program that runs without exceptions can still implement the wrong modular computation.
10. Measure a depth-three circuit. Each iteration squares the current ciphertext and relinearizes it before the next multiplication.
11. Check both the value and remaining capacity. The final result must match x^8\bmod t, and the local diagnostic must report a positive remaining budget.

Run the program with:

python bfv_demo.py

One representative run prints:

SEAL-Python version: 4.4.0
Polynomial modulus degree: 8192
Plaintext modulus: 1032193
Batching slots: 8192
Decoded sums: [35, 8, 11, 20]
Decoded products: [276, 15, 28, 99]
Ciphertext size around relinearization: 3 -> 2
Noise budget for fresh, sum, and product ciphertexts: 146, 146, 114
Decoded x^8 values: [256, 6561, 65536, 390625]
Noise budget across depth 0 to 3: [146, 114, 81, 48]

The exact noise-budget figures can vary slightly because encryption is randomized. The decoded values, ciphertext-size transition, and assertions are the stable correctness checks.

Read the output as an HE developer

The addition consumes almost no multiplicative capacity in this example, while one ciphertext multiplication reduces the reported budget substantially. The repeated-squaring trace makes the depth cost visible:

Circuit state	Multiplicative depth	Expected first four slots	Representative remaining budget
Fresh encryption of x	0	2,3,4,5	146 bits
x^2	1	4,9,16,25	114 bits
x^4	2	16,81,256,625	81 bits
x^8	3	256,6561,65536,390625	48 bits

Table 11: Value evolution and representative BFV noise budget across three dependent squarings.

The budget is a diagnostic, not an application result. Once correctness capacity is exhausted, decryption is not guaranteed to produce a recognizable failure; it may return an apparently ordinary but incorrect plaintext. Correct programs therefore derive a depth requirement before selecting parameters and test that circuit over bounded application inputs.

Relinearization addresses a different problem. It reduces ciphertext component count after multiplication, improving the cost of later operations. It does not erase accumulated error, replenish the noise budget, or convert a fixed-depth computation into an unbounded one. This distinction is the same one summarized in Table 4.

Batching also has a precise meaning. One addition updates all 8192 slots in parallel, and one multiplication computes 8192 slotwise products. It does not automatically perform a dot product or matrix multiplication. Those operations require slot rotations, additions across slots, an explicit packing layout, and compatible Galois keys.

Experiments that teach the right lessons

The following modifications expose distinct engineering constraints.

Force modular wraparound

Replace one input pair with 2000 and 1000. The ordinary product is 2{,}000{,}000, but BFV returns:

2{,}000{,}000 \bmod 1{,}032{,}193 = 967{,}807. \tag{58}

This is correct BFV behavior. If the application expects the ordinary product, its numeric bounds or representation are wrong.

Increase multiplicative depth one layer at a time

Change the squaring loop from three iterations to four. The target becomes x^{16}\bmod t, not x^8. Record runtime, ciphertext size before and after relinearization, and remaining budget after every layer. Do not conclude that a parameter set supports a circuit merely because one input decrypts correctly; test the full input bounds and retain a deliberate correctness margin.

Add rotations

Generate Galois keys and rotate a batched vector by one slot. Then combine rotations to sum selected slots. Measure the size of the Galois keys and the time spent in rotations. This experiment shows why a packing plan is part of circuit design rather than a late optimization.

Move evaluation into another process

Serialize the parameters, public evaluation material, and input ciphertexts. Load them in a process that has no secret key, evaluate the circuit, and return only result ciphertexts. Confirm independently that the evaluator cannot construct a decryptor. This turns the logical split in Figure 5 into an enforceable deployment boundary.

Reimplement the task with CKKS

Do not merely replace BFV with CKKS in the scheme selector. A CKKS version needs a coefficient-modulus chain, an initial scale, rescaling after multiplication, compatible levels and scales before addition, and tolerance-based assertions. The output contract also changes from exact equality modulo t to an explicit numerical error bound.

Keep diagnostics inside the trusted environment

The example calls invariant_noise_budget only on ciphertexts created and evaluated locally. That method depends on the secret key. Microsoft warns that repeated calls on attacker-chosen ciphertexts can leak the secret key, so an evaluator must not receive a noise-budget oracle and the resulting measurements must not cross the trust boundary.³³

The same security guidance states that Microsoft SEAL ciphertexts are not authenticated and that the library does not provide circuit privacy. Successful deserialization or decryption therefore does not prove ciphertext origin, evaluator honesty, or correct execution. A production protocol must separately address authenticated transport, replay protection, input provenance, output authorization, malformed objects, and verification of the requested computation.

Developer completion checklist

Before treating an HE prototype as an application design, record the following:

Question	Evidence to retain
What arithmetic does the application require?	Exact modular contract or approximate-error contract
What are the maximum input and intermediate values?	Bound analysis proving that wraparound or loss of precision is acceptable
What is the multiplicative depth?	Circuit graph and longest dependent multiplication path
How are values packed?	Slot layout, required rotations, and expected utilization
Which evaluation keys are required?	Relinearization and minimal Galois-key set
Which party owns each key and object?	Trust-boundary and serialization design
How were parameters accepted?	Library validation result, security target, version, and parameter fingerprint
How was correctness tested?	Known-answer, boundary, randomized property, and negative tests
What metadata remains visible?	Ciphertext sizes, timing, circuit, traffic, and access pattern
How is evaluator misconduct detected?	Protocol-level integrity, freshness, and verification controls

Table 12: Minimum evidence for moving an HE experiment toward an application design.

This example establishes the practical transition from algebra to HE engineering: the evaluator can transform ciphertexts without a secret key, but the developer must still specify the arithmetic domain, circuit depth, packing layout, key boundary, correctness margin, and protocol protections. Those decisions, rather than the calls to add and multiply alone, determine whether the encrypted computation implements the intended application.

Recap and the challenges ahead for privacy-preserving computation

At its core, FHE changes one trust boundary. A party can evaluate an allowed function without receiving the plaintext or the decryption key. For an exact scheme, the defining contract is:

\operatorname{Dec}_{sk} \left( \operatorname{Eval}_{f} \left( evk, \operatorname{Enc}_{pk}(m) \right) \right) = f(m). \tag{59}

For an approximate scheme such as CKKS, equality is replaced by a declared numerical tolerance. In both cases, the evaluator returns a ciphertext rather than the exposed result.

That capability is substantial, but its boundary must remain visible. FHE does not make sensitive data cease to exist in plaintext. Plaintext normally exists before encryption, after authorized decryption, and wherever the application creates or consumes the final output. FHE reduces the locations in which plaintext must appear; it does not abolish trusted endpoints.

Nor is FHE equivalent to complete privacy. Privacy concerns what data are collected, why they are processed, which inferences are permitted, what metadata remain visible, who receives the output, how long information is retained, and what consequences individuals may experience. NIST accordingly treats FHE as one privacy-enhancing cryptographic tool alongside MPC, ZKPs, PSI, and other techniques rather than as a complete privacy architecture.³⁴ Its Privacy Framework treats privacy risk across the full data-processing lifecycle, including effects that can arise even when confidentiality is not breached.³⁵

What this tutorial has established

The progression from algebra to executable BFV code supports seven durable lessons.

1. A homomorphism is an operation-preserving map, not a security guarantee. Textbook RSA preserves multiplication, yet its determinism and unrestricted malleability make it unsuitable as secure general-purpose encryption.
2. An HE scheme is a coordinated system of algorithms. Key generation, encoding, encryption, evaluation, maintenance, decryption, and decoding must share compatible parameters and an explicit trust model.
3. The plaintext domain is part of the application contract. BFV and BGV compute exact modular results; CKKS computes approximate real or complex results; Boolean and lookup-table-oriented schemes expose different operations.
4. Functional completeness does not imply practical efficiency. A function may be expressible as an arithmetic or Boolean circuit while remaining too deep, too wide, or too data-movement-intensive for the available parameters and budget.
5. FHE and leveled HE are operationally different. A leveled deployment selects capacity for a bounded circuit. An FHE deployment must also refresh ciphertexts when arbitrary continuation is required.
6. Packing changes the program. Batching improves throughput by applying operations slotwise, but reductions, permutations, matrix products, and convolutions require deliberate layouts and rotations.
7. Confidential evaluation is not verified evaluation. Ordinary HE does not prove that the evaluator used the requested function, processed the correct inputs, returned the freshest result, or preserved output policy.

The Microsoft SEAL lab made these points concrete. The useful achievement was not merely that add and multiply executed. It was that the program specified modular semantics, validated parameters, separated secret and evaluation keys, measured depth, relinearized multiplication results, asserted outputs, and kept secret-key-dependent diagnostics within the trusted boundary.

FHE is one layer of a privacy system

The following table separates the protection supplied by FHE from the controls required around it.

Privacy or security objective	What FHE contributes	What remains to be supplied
Hide inputs from an external evaluator	Encrypts operands while preserving authorized computation	Secure collection, endpoint protection, input minimization, and correct encoding
Protect stored and transmitted objects	Produces ciphertexts for evaluated data	Authenticated transport, storage controls, freshness, replay protection, and safe serialization
Ensure correct computation	Preserves the semantic relation for honestly executed evaluation	Verifiable computation, ZKPs, redundancy, attestations, or application-specific checks
Hide the access pattern and circuit	May hide plaintext values	ORAM, PIR, circuit privacy, traffic shaping, padding, and timing controls
Limit what outputs reveal	Returns the result as a ciphertext	Authorization, purpose limitation, query controls, DP, aggregation, and disclosure review
Support several independent data owners	Can be extended through multiparty constructions	Distributed key generation, threshold decryption, multi-key protocols, and governance
Protect keys and plaintext endpoints	Keeps the evaluator from needing the secret key	Hardened clients, HSMs, secure recovery, rotation, revocation, and side-channel defenses
Demonstrate accountability	Can produce reproducible cryptographic artifacts	Logs, policy evidence, data lineage, legal basis, human oversight, and incident response

Table 13: FHE contributes one layer to a complete privacy and security architecture.

The complete workflow therefore contains controls before encryption, around evaluation, and after decryption:

flowchart TB
  subgraph Client[Trusted client]
    direction TB
    P[/Authorized plaintext inputs/]:::plaintext
    K([Govern keys parameters and policy]):::trusted
    E([Minimize encode encrypt and authenticate]):::trusted
    C[/Input ciphertexts/]:::ciphertext
    G([Verify authorize decrypt and govern release]):::trusted
    O[/Minimum necessary output/]:::plaintext
    P --> E
    K --> E
    E --> C
    K --> G
    G --> O
  end
  subgraph Service[External evaluator]
    direction TB
    V[Evaluate approved circuit]:::evaluator
    R[/Result ciphertext/]:::ciphertext
    V --> R
  end
  C --> V
  K -. Public context evaluation keys and approved circuit .-> V
  R --> G
  V -. Supporting evidence .-> G

  classDef trusted fill:#DCFCE7,stroke:#15803D,color:#14532D,stroke-width:2px;
  classDef evaluator fill:#FEF3C7,stroke:#B45309,color:#78350F,stroke-width:2px;
  classDef ciphertext fill:#DBEAFE,stroke:#1D4ED8,color:#1E3A8A,stroke-width:2px;
  classDef plaintext fill:#FEE2E2,stroke:#B91C1C,color:#7F1D1D,stroke-width:2px;
  linkStyle default stroke:#475569,stroke-width:2px;

Figure 6: FHE embedded within a governed privacy-preserving computation

The diagram is a target architecture, not a claim that HE provides every depicted control. HE supplies the ciphertext transformation and its decryption contract. Authentication, evidence production, verification, authorization, and release governance require additional protocol and organizational mechanisms. Message sizes, timing, circuit structure, and communication patterns may also remain visible along the arrows.

Twelve challenges that must be overcome

The following challenges are not speculative trends. They are acceptance conditions for moving from successful demonstrations to broadly available private computation.

1. Reduce total cost, not merely operation time. Published multiplication or bootstrapping latency captures only one part of a deployment. A useful benchmark must include parameter setup, key generation, evaluation-key transfer, encoding, encryption, rotations, evaluation, serialization, network transfer, decryption, memory, storage, energy, and concurrency. Hardware acceleration is valuable only when its cost, portability, side-channel behavior, and utilization are included.

2. Make ordinary programs compile into efficient encrypted circuits. Developers think in branches, comparisons, arrays, objects, databases, and variable-length loops. HE libraries expose additions, multiplications, rotations, rescaling, and lookup-oriented primitives. Compilers must bridge that gap while making the transformed semantics, depth, approximation, and data layout inspectable rather than hiding them behind an opaque optimization pass.

3. Make bootstrapping and scheme switching routine. FHE requires ciphertext refresh when computation must continue beyond the initial capacity. Bootstrapping must become predictable in latency, numerical behavior, key size, memory use, and failure probability. Applications that mix exact arithmetic, approximate arithmetic, comparisons, and lookups also need safe transitions between representations without forcing developers to become scheme specialists.

4. Automate parameter selection without obscuring evidence. Parameters jointly determine concrete security, supported depth, failure probability, precision, ciphertext size, and performance. A production toolchain should derive a candidate configuration from a circuit and security target, reject unsafe combinations, and emit machine-readable evidence explaining every choice. Current security guidance emphasizes that FHE parameter selection cannot be separated from the operations the system must support.³⁶

5. Make numerical correctness auditable. Exact schemes require proofs that intermediate values do not wrap unexpectedly modulo the plaintext modulus. Approximate schemes require end-to-end error budgets covering encoding, polynomial approximation, multiplication, rescaling, and decoding. Tests on typical samples are insufficient; applications need input bounds, worst-case analysis, tolerances, and failure handling that survive library and compiler updates.

6. Combine confidentiality with integrity and verifiability. A server that cannot read the data can still omit work, substitute a circuit, replay an old ciphertext, mix tenants, or return arbitrary bytes. Broad adoption requires practical ways to bind inputs, function, parameters, version, and output. Depending on the threat model, that may involve authenticated protocols, ZKPs, verifiable computation, replication, trusted execution, or domain-specific consistency checks.

7. Solve key governance for real organizations. A single long-lived secret key held by one client does not fit many collaborative, regulated, or high-availability systems. Deployments need distributed key generation, threshold decryption, rotation, revocation, recovery, separation of duties, auditable release ceremonies, and safe handling of evaluation keys. Multi-owner data should not silently become data controlled by one decryption authority.

8. Protect metadata, access patterns, and the circuit where required. FHE can hide values while revealing who communicated, when, how much data were processed, which parameters were used, which circuit ran, and which database locations were touched. These signals can disclose categories, behavior, or business logic. Circuit privacy, PIR, ORAM, padding, batching policy, traffic shaping, and constant-pattern execution must be selected according to a stated leakage budget.

9. Secure endpoints, runtimes, and untrusted inputs. Encryption clients, decryptors, key services, compilers, accelerators, and serialization code remain attack surfaces. Memory corruption, timing leakage, fault injection, malformed ciphertexts, compromised randomness, secret-dependent diagnostics, and decryption oracles can invalidate the scheme’s mathematical security. Implementations need hardened parsing, fuzzing, side-channel analysis, dependency control, key isolation, and explicit trust-boundary tests.

10. Govern decrypted outputs and repeated queries. A perfectly protected computation can release a result that identifies an individual, reveals a sensitive attribute, enables model extraction, or leaks information through repeated adaptive queries. Output minimization, aggregation, DP, query budgets, recipient authorization, purpose enforcement, and audit are therefore part of the privacy design. FHE protects computation from the evaluator; it does not decide whether the answer itself should be disclosed.

11. Create interoperable and crypto-agile infrastructure. Ciphertexts, parameter identifiers, keys, encodings, circuit descriptions, and proof artifacts need portable formats and stable compatibility rules. The current community standard concentrates on scheme descriptions, security properties, and secure parameters; a common API and programming model remain incomplete standardization goals.³⁷ Long-lived systems must also preserve algorithm and parameter agility. LWE-based FHE is a post-quantum candidate, not a proof against all future quantum or classical attacks.

12. Make private computation accessible and accountable. Privacy cannot be for all if deploying it requires scarce cryptographers, proprietary accelerators, hyperscale budgets, or unauditable services. Broad use requires open conformance tests, representative benchmarks, maintainable libraries, safer defaults, reproducible builds, training, procurement criteria, independent review, and clear allocation of responsibility when a system fails. Economic accessibility and institutional accountability are deployment properties, not consequences of the FHE equation.

What broad success would look like

FHE will be ready for broad, responsible application when a development team can do all of the following without relying on undocumented expert judgment:

• state exactly which parties must not learn each input, intermediate value, output, circuit, and metadata field;
• compile the required function into an inspectable circuit with bounded depth, precision, and data movement;
• derive validated parameters and retain reproducible security and correctness evidence;
• separate secret-key operations from the evaluator through enforceable technical boundaries;
• authenticate inputs and outputs and verify that the approved computation was performed;
• govern multi-owner keys, rotations, recovery, revocation, and output authorization;
• quantify end-to-end latency, throughput, memory, network, storage, energy, and cost against a plaintext baseline;
• test malformed inputs, boundary values, numerical failures, side channels, version changes, and recovery procedures;
• document residual leakage and combine FHE with the complementary privacy technique that addresses it;
• operate the system under clear ownership, audit, incident-response, retention, and decommissioning rules.

This target is stricter than making a demonstration decrypt correctly, but it is the appropriate threshold. A privacy-preserving system must remain secure, correct, governable, and economically usable throughout its lifecycle.

The durable takeaway

FHE resolves a specific contradiction that conventional encryption leaves open: an evaluator can compute a function while remaining unable to read the protected operands. That is a foundational capability, not a complete privacy outcome.

The path forward is therefore not to apply FHE indiscriminately to every byte and every program. It is to use FHE wherever removing plaintext from an evaluator materially reduces risk, then combine it with the controls that protect endpoints, metadata, computation integrity, keys, and outputs. When those layers become interoperable, auditable, affordable, and understandable to ordinary development teams, private computation can move from a specialist technique to dependable infrastructure available to everyone.

See also cryptography longforms

Quantum-Safe HTTPS Certificates: Google’s Structural Innovation, Technical Foundations, and Governance Implications

Engineering quantum resistant web authentication through Merkle commitments, transparency logs, and scalable trust infrastructure

When Digital Trust Expires: Quantum Computing and the Collapse of Signature-Based Security

How quantum attacks turn long-lived signatures into silent integrity and impersonation risks

See also mathematics longforms

The Mathematics Behind a Racing Shell

Why rowing-boat simulation is a difficult multiphysics engineering problem

Sudoku and Satisfiability Modulo Theories

You can solve it the standard way or... with Python and math

The Relationship Between Category Theory, Lambda Calculus, and Functional Programming in Haskell

The power of compositionality

See also software development longforms

VEX Standards from First Principles

From software inventories to defensible vulnerability-exploitability decisions

The Mathematics Behind a Racing Shell

Why rowing-boat simulation is a difficult multiphysics engineering problem

Sudoku and Satisfiability Modulo Theories

You can solve it the standard way or... with Python and math

See also posts

AI Agents Are Solving Open Problems and Changing What Mathematics Is For

Navier–Stokes, machine-scale mathematical search, and the changing meaning of mathematical progress

When Formalization Became Industrial

Fermat's Last Theorem, Prove2Me, and the transition from proof abundance to formalization abundance

After Proof Abundance: Palomar and the New Infrastructure of Mathematical Trust

Formal verification, provenance, semantic fidelity, and institutional governance in machine-scale mathematics

The Industrialization of Mathematical Intelligence: Beyond Proof Abundance to Open Questions of Governance

Jacob Tsimerman, Timothy Gowers, and the changing roles of human judgment, agency, and mathematical culture

When AI Failure Became a Theorem: What the Grothendieck Constant Breakthrough Reveals About Human–AI Mathematical Collaboration

How a long-horizon research system, human judgement, and rigorous verification turned a stalled search into new bounds for one of mathematics’ most elusive constants

Growing Abundance of AI Math: Progress around the Riemann Hypothesis and a Counterexample to the Maxwell Conjecture

Two more research-level results strengthen the case that AI-assisted mathematical discovery is becoming a recurring phenomenon rather than a sequence of isolated demonstrations

Footnotes

1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. DOI. Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134. IEEE. DOI

2. National Institute of Standards and Technology. (2023). Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197, Update 1. DOI. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219. ACM. DOI

3. Goldwasser, S., & Micali, S. (1984). Probabilistic encryption. Journal of Computer and System Sciences, 28(2), 270–299. DOI. Bellare, M., & Rogaway, P. (1995). Optimal asymmetric encryption: How to encrypt with RSA. Advances in Cryptology: EUROCRYPT 1994, 92–111. Springer. DOI

4. Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology: EUROCRYPT 1999, 223–238. Springer. DOI

5. Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 169–178. ACM. DOI

6. Dwork, C., & Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4), 211–407. DOI

7. Yao, A. C. (1982). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 160–164. IEEE. DOI

8. Goldwasser, S., Micali, S., & Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1), 186–208. DOI

9. McKeen, F., Alexandrovich, I., Berenzon, A., Rozas, C., Shafi, H., Shanbhogue, V., & Savagaonkar, U. R. (2013). Innovative instructions and software model for isolated execution. Proceedings of the 2nd International Workshop on Hardware and Architectural Support for Security and Privacy. ACM. DOI

10. López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012). On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 1219–1234. ACM. DOI

11. McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Agüera y Arcas, B. (2017). Communication-efficient learning of deep networks from decentralized data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 1273–1282. PMLR. Paper

12. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1998). Private information retrieval. Journal of the ACM, 45(6), 965–981. DOI

13. Angel, S., Chen, H., Laine, K., & Setty, S. T. V. (2018). PIR with compressed queries and amortized query processing. 2018 IEEE Symposium on Security and Privacy, 962–979. IEEE. DOI. Microsoft Research. (2018). SealPIR. Research software repository. Source code

14. Bossuat, J.-P., Cammarota, R., Chillotti, I., Curtis, B., Dai, W., Gong, H., Hales, E., Kim, D., Kumara, B., Lee, C., Lu, X., Maple, C., Pedrouzo-Ulloa, A., Player, R., Polyakov, Y., Ruiz Lopez, L. A., Song, Y., & Yhee, D. (2025). Security guidelines for implementing homomorphic encryption. IACR Communications in Cryptology, 1(4). DOI

15. Microsoft. (n.d.). Microsoft SEAL. Open-source homomorphic encryption library. Source code. OpenFHE Project. (n.d.). OpenFHE. Open-source fully homomorphic encryption library. Project website

16. Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. In R. A. DeMillo, D. P. Dobkin, A. K. Jones, & R. J. Lipton (Eds.), Foundations of Secure Computation (pp. 169–179). Academic Press. Author copy

17. Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. Advances in Cryptology: EUROCRYPT 2010, 1–23. Springer. DOI

18. Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012). Leveled fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 309–325. ACM. DOI

19. Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. Advances in Cryptology: ASIACRYPT 2017, 409–437. Springer. DOI

20. Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., & Vaikuntanathan, V. (2021). Homomorphic encryption standard. In K. Lauter, W. Dai, & K. Laine (Eds.), Protecting Privacy through Homomorphic Encryption (pp. 31–62). Springer. DOI

21. Buhler, J. P., Lenstra, H. W., Jr., & Pomerance, C. (1993). Factoring integers with the number field sieve. In A. K. Lenstra & H. W. Lenstra Jr. (Eds.), The Development of the Number Field Sieve (pp. 50–94). Springer. DOI

22. Rivest, R. L., & Kaliski, B. (2003). RSA problem. Prepublication manuscript. Author copy

23. Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3), 300–317. DOI. Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128–138. DOI

24. Barker, E., & Kelsey, J. (2015). Recommendation for random number generation using deterministic random bit generators. NIST Special Publication 800-90A Revision 1. National Institute of Standards and Technology. DOI

25. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. DOI

26. Moriarty, K., Kaliski, B., Jonsson, J., & Rusch, A. (2016). PKCS #1: RSA cryptography specifications version 2.2. RFC 8017. Internet Engineering Task Force. RFC

27. Goldwasser, S., & Micali, S. (1984). Probabilistic encryption. Journal of Computer and System Sciences, 28(2), 270–299. DOI

28. Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology: EUROCRYPT 1999, 223–238. Springer. DOI

29. Moriarty, K., Kaliski, B., Jonsson, J., & Rusch, A. (2016). PKCS #1: RSA cryptography specifications version 2.2. RFC 8017. Internet Engineering Task Force. RFC

30. Microsoft. (2026). Microsoft SEAL 4.4.3. Open-source homomorphic-encryption library. Source code Release

31. Huelse. (2026). SEAL-Python 4.4.0. Python Package Index. Package Source code

32. Pireddu, L. (2014). Seal 0.4.0-rc2. Python Package Index. Package

33. Microsoft. (2026). Correct use of Microsoft SEAL. Microsoft SEAL security guidance. Security guidance

34. National Institute of Standards and Technology. (2026). Fully homomorphic encryption. Privacy-Enhancing Cryptography project. Project page

35. Boeckl, K., & Lefkovitz, N. (2020). NIST Privacy Framework: A tool for improving privacy through enterprise risk management, version 1.0. NIST Cybersecurity White Paper. DOI

36. Bossuat, J.-P., Cammarota, R., Chillotti, I., Curtis, B. R., Dai, W., Gong, H., Hales, E., Kim, D., Kumara, B., Lee, C., Lu, X., Maple, C., Pedrouzo-Ulloa, A., Player, R., Polyakov, Y., Ruiz Lopez, L. A., Song, Y., & Yhee, D. (2025). Security guidelines for implementing homomorphic encryption. IACR Communications in Cryptology, 1(4). DOI

37. Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., & Vaikuntanathan, V. (2018). Homomorphic encryption security standard. HomomorphicEncryption.org. Standard