Hospitals, banks and governments increasingly want two things at once. They want to outsource large fact databases (patient records, transactions) to a cloud server without the server learning anything. They also want to ask questions that need logical inference over those facts, such as "which patients have a condition that is a subtype of a cardiac disorder, treated by someone in a department that is part of cardiology?" The rules that license such inferences live in an ontology, a formal vocabulary of concepts and the logical relationships between them. The ontology is usually public or shared, like a standard medical terminology. Only the instance facts are secret. Encrypted databases built on fully homomorphic encryption (FHE), which lets a server compute on ciphertexts without ever decrypting them, can now filter, sort and aggregate encrypted tables. None of them can follow a chain of rules across linked records, because none support joins or recursion.
This note proposes to treat the public ontology as a program that is compiled, in plaintext and ahead of time, into a fixed, data-independent homomorphic circuit. The circuit runs over encrypted per-predicate bitmaps of the facts. Since the rules are public, the server knows the exact sequence of joins and the recursion bound in advance, and only the data stays hidden. That makes the oblivious, branch-free evaluation FHE requires a natural fit rather than a handicap. The technical core is a scheduler that delays the expensive "is this count nonzero?" tests until a logical conjunction actually needs them. That test is the main nonlinear cost in encrypted logic.
Core Claim
Database-integrated reasoning already splits knowledge bases into a small schema part, the TBox, and a huge instance part, the ABox. Systems like The Instance Store and Description Logic-Ground Knowledge Integration and Management process the schema in memory and push instance work to a database. We keep that split but change where the line falls. The schema is reasoned about in plaintext, and the instance work becomes homomorphic arithmetic. For Horn ontologies, which are ontologies whose rules have no disjunction in their conclusions, From Horn-SRIQ to Datalog gives a data-independent translation into Datalog that preserves answers to instance queries. We take its output, a recursive rule program, and compile it into a depth-optimized circuit. In that circuit, unary predicates are encrypted bit vectors packed into ciphertext slots, and binary predicates are encrypted adjacency bitmaps. Each rule then becomes one of three operations: slotwise multiplication, which handles conjunctions on one individual; packed matrix-vector products, which handle one-hop existential joins; or repeated squaring, which handles transitive roles in a logarithmic number of rounds.
The algebra that makes this work is counting. Take a rule such as $A(x) \leftarrow R(x,y) \wedge B(y)$. The server computes encrypted counts $c_A = M_R\, b_B$, where $M_R$ is the encrypted adjacency bitmap of role $R$ and $b_B$ is the encrypted membership vector of concept $B$. Disjunction then comes for free as addition. The only nonlinear step is converting a count back into a bit,
$$b_A = c_A^{\,p-1} \bmod p,$$
which by Fermat's little theorem equals 1 exactly when $c_A \neq 0$, provided the plaintext modulus $p$ is a prime larger than any count that can arise. This test costs about $\log_2 p$ levels of multiplicative depth. Our claim is that a compiler which knows the whole public rule program can place these tests only where a later multiplication needs a clean bit. It can also bound the counts statically to keep $p$ small, and schedule recursion with a bound the program determines. Together these should cut multiplicative depth and bootstrapping by a large factor compared with evaluating rule by rule. Bootstrapping is the costly noise-reset operation, the dominant cost according to Circuit Bootstrapping: Faster and Smaller. We expect this reduction to be what makes encrypted ontology query answering feasible at the 10^4-individual scale that current encrypted databases handle.
Relation to Prior Work
The encrypted-database line supplies the operators but motivates the gap. HE3DB performs SQL filters, aggregates and decision-tree inference over encrypted tables. ArcEDB adds arbitrary-precision comparison and sorting, and explicitly removed JOIN conditions from its TPC-H evaluation. Engorgio adds homomorphic sorting and Top-k for hybrid relational-vector tables. All three are single-table engines that compare encrypted values. We do not compare encrypted foreign keys at all, because we encode relations as bitmaps indexed by individual. That turns joins into linear algebra. The earlier Private Database Queries Using Somewhat Homomorphic Encryption encodes index sets as polynomial roots and answers flat conjunctions. It is a precedent for set-algebra encodings, but it has no rules and no multi-hop paths.
Penguin supplies a method. Its two-dimensional packing of node and feature data into slots reduces costly slot rotations for encrypted graph convolution, which is a continuous $A X W$ product. We reuse that packing for Boolean-valued adjacency products. Our circuit differs in that it is discrete, multi-relational and recursive, and these properties are exactly what force nonlinear normalization steps that a graph network never needs.
On the reasoning side, Pan et al. and SOR show that rewriting ontology queries into relational operations scales on plaintext. We change the target of the rewriting from SQL plans to homomorphic circuits. Scallop evaluates Datalog over provenance semirings. Our count encoding is in effect the counting semiring, but run under encryption, and we deliberately leave Scallop's top-k probabilistic proofs aside, because those require encrypted sorting inside the fixed point. Two papers constrain the design. Rewriting the Infinite Chase shows that non-Horn constructs blow up rewritings. For those, we borrow the strategy of PAGOdA, which computes Datalog lower and upper bounds and sends only the residual gap to a full reasoner. In our setting, the server computes both bounds homomorphically. The client decrypts a single gap bitmap and resolves those few candidates locally, in one extra round.
Research Program
The first component is the compiler. It takes a Horn ontology, applies the Datalog translation, and computes the predicate dependency graph. From that graph it derives the non-recursive depth and the strongly connected components that need fixed-point iteration. It then solves a scheduling problem: decide where to insert nonzero tests, and how to bound counts so that $p$ stays small, in order to minimize total multiplicative depth. For example, an intermediate count that only feeds further additions never needs a test. A count whose maximum is bounded by a role's maximum out-degree, published as a deliberate and measured leakage parameter, allows a smaller $p$. The second component is the packed runtime. It is built on a BFV-style integer scheme, with Penguin-style packing for adjacency bitmaps and ArcEDB-style bit circuits as an alternative for the nonzero test. The third component is the bounded, gap-resolving extension for non-Horn ontologies. The fourth is an analysis of exactly what leaks to the server: the number of individuals, the published degree bounds, and the query's predicate shape. We report this leakage alongside every result.
Baselines
The naive reference point is plaintext reasoning with no confidentiality: the same queries answered by PAGOdA and its Datalog engine on unencrypted data. This defines correctness, and we will judge answers with the degree-of-completeness and degree-of-soundness measures from Large Scale Knowledge Base Systems. It also defines the ideal latency. PAGOdA reports average query time "under 13 seconds for the vast majority of queries, even on datasets with hundreds of millions of facts," and reports that Datalog bounds matched for over 99% of 4,000+ queries. We do not expect to approach that latency. The baseline exists to measure the price of privacy, and to check that our bounds-matching rate on encrypted data equals PAGOdA's on plaintext.
The strongest competitor is materialize-then-encrypt. The data owner computes all inferences in plaintext with the same Datalog engine, encrypts the closed bitmaps, and the server answers queries with lookups using the same scheme, packing and hardware we use. This competitor is fair only if it is charged for what it actually costs: owner-side recomputation, re-encryption and re-upload whenever the ontology or the data changes, and one full encrypted copy per ontology when several ontologies are served. We beat it when, at equal hardware and a matched security level of 128 bits, our total cost over a workload is lower. The workload is defined by the number of ontologies, the update rate and the query rate. We will report the crossover honestly, including the regime where materialization wins outright.
The obvious encrypted-database composition is the third baseline. Here the ontology is rewritten into a union of SQL-style conjunctive queries, and each join is executed as all-pairs encrypted equality using the HE3DB or ArcEDB comparison operators, on the same data. HE3DB reports 241 seconds for a TPC-H query over a 16-bit 10K-row database. Engorgio reports amortized runtimes under 3 seconds for 10K-row relational queries on 48 cores. Both figures are for join-free queries. We found no reported result on Lacuna for homomorphic joins or recursion, so we will implement this baseline ourselves. Beating it means lower latency at equal or better completeness on join-bearing queries.
The fourth baseline is client-side decryption. The client downloads the encrypted ABox, decrypts it, and reasons locally. We measure its bandwidth and client memory.
The key ablation isolates the compiler. It runs our runtime with a nonzero test after every rule and a generic recursion bound equal to the number of individuals. A second ablation removes the published degree bounds, forcing the worst-case $p$. If the full compiler is not at least several times shallower and faster than the eager ablation, the central claim fails.
Why not just…?
Why not just materialize all inferences before encrypting? This is the real threat, and the bitmap encoding makes it stronger. Closing a bitmap under unary inferences adds no extra ciphertexts, so the storage-explosion argument from the research file mostly evaporates in our representation. What remains is that materialization fixes one ontology and one data snapshot, and every change requires the data owner to be online to recompute and re-encrypt. Our proposal is only worthwhile when several public ontologies or ontology versions are applied to the same encrypted data, or when the rules change faster than the owner can re-upload. The crossover experiment below exists to show whether that regime is real and how large it is. If materialization dominates even at many ontologies, we will say so.
Why not just download and reason on the client? Encrypted machine-learning studies such as A Systematic Comparison of Encrypted ML Solutions find that communication often dominates. More to the point, transferring the whole ABox defeats the purpose of outsourcing and puts the ABox memory problem back on the client. We still include this baseline, because for small ABoxes on a fast network it may genuinely win, and we will report where that happens.
Why not just use secure enclaves or multi-party computation? Enclaves change the trust model to trusting the hardware vendor, and they leak memory-access patterns. That is a different security claim, so we treat enclaves as a comparison point in the discussion rather than an equivalent. Multi-party protocols need communication rounds for every nonlinear gate. A recursive fixed point has many sequential nonlinear layers, so latency grows with round-trip time. Our design needs at most one optional round, for the gap. We do not run either alternative, and a reviewer may reasonably want an enclave latency number for context.
Proposed Experiments
The main benchmark is LUBM, the Lehigh University Benchmark, a synthetic university-domain knowledge base. We use its Horn-expressible queries, with the instance data scaled from roughly 10^3 to 10^4 individuals. This matches the 10K-row regime where HE3DB, ArcEDB and Engorgio report results. We include LUBM's transitive role and its existential-path queries. UOBM, which adds disjunction, tests the bounds-plus-gap extension, and we check that the encrypted bounds reproduce PAGOdA's plaintext gaps exactly. Cora and Citeseer, at 2,708 and 3,327 nodes, serve as adjacency-shape controls, so that our packing overhead can be compared against Penguin's setting. For each configuration we report answer correctness against plaintext RDFox/PAGOdA, end-to-end latency, multiplicative depth, bootstrapping count, ciphertext and evaluation-key sizes, and client bandwidth.
Two checks decide the outcome. The first is the compiler ablation: lazy nonzero tests must reduce depth and runtime substantially compared with eager evaluation, or the mechanism is not doing the work. The second is the multi-ontology crossover. We take several LUBM-derived TBox variants of increasing depth over one encrypted ABox, add a controlled update stream, and plot total cost for our approach against materialize-then-encrypt. A clear crossover at a modest number of ontologies or update rate would establish when server-side encrypted reasoning is worth paying for. The absence of any crossover would be a useful negative result: the community should stop at materialization.
References
- The Instance Store: DL Reasoning with Large Numbers of Individuals
- Description Logic-Ground Knowledge Integration and Management
- From Horn-SRIQ to Datalog: A Data-Independent Transformation That Preserves Assertion Entailment
- Circuit Bootstrapping: Faster and Smaller
- HE3DB: An Efficient and Elastic Encrypted Database Via Arithmetic-And-Logic Fully Homomorphic Encryption
- ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic Encryption
- Engorgio: An Arbitrary-Precision Unbounded-Size Hybrid Encrypted Database via Quantized Fully Homomorphic Encryption
- Private Database Queries Using Somewhat Homomorphic Encryption
- Penguin: Parallel-Packed Homomorphic Encryption for Fast Graph Convolutional Network Inference
- Approximating OWL-DL Ontologies
- SOR: A Practical System for Ontology Storage, Reasoning and Search
- Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning
- Rewriting the Infinite Chase
- PAGOdA: Pay-as-you-go ABox Reasoning
- Large Scale Knowledge Base Systems: An Empirical Evaluation Perspective
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification