A Gentle Introduction to Encrypted Decision Trees with Homomorphic Encryption

Sefik Serengil

Decision trees are the most honest models in machine learning. You can print one, pin it on the wall, and explain it to anyone in five minutes. That transparency is also exactly why banks, insurers and hospitals guard them so carefully: a credit scoring tree is the credit policy. Leak the tree and anyone can reverse engineer how to game it.

Chalk drawing of a head with swirling arrows represents mental activity and thought process by pexels

Now flip the table. The customer who is being scored has private data too: income, age, debt, health records. They don’t want to hand all of that over just to learn a single number.

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

Cryptography Basiscs From Scratch In Python

So we have two parties who don’t trust each other, and we want to run one party’s secret model on the other party’s secret data. In the old days the answer was “find a trusted third party”, which in practice meant “find someone you both distrust equally”. In this post we will do it with homomorphic encryption instead, using LightPHE, and we will do it in Python, Go, Java and TypeScript. In the academic literature, this problem is called private decision tree evaluation. We’ll stick with “encrypted decision trees” because it fits on a T-shirt.

Here’s the twist, before we start. LightPHE ships with more than 25 cryptosystems, but only two of them can evaluate a decision tree on encrypted data:

  • Ishai-Paskin, for trees that ask yes / no questions, and
  • Damgard-Geisler-Kroigaard (DGK), for trees that compare numbers against thresholds.

Everything else, including household names like RSA, ElGamal and Paillier, falls short. This isn’t snobbery. Each of them is missing at least one feature that a private decision tree needs, and by the end of this post you’ll know exactly which one.

The Setting

Let’s put names on things.

  • The bank owns a secret decision tree that outputs a credit limit.
  • The customer owns private features (or yes / no answers).
  • The customer generates the key pair and keeps the private key. The bank only ever sees the public key.

The goals:

  1. The bank learns **nothing** about the customer’s data. Not the features, not the path taken through the tree, not even the result.
  2. The customer learns **only** the credit limit. Not the thresholds, not the questions asked on other branches, not the other leaves.

The flow looks like this:

 customer                                         bank
 --------                                         ----
 generate keys
 encrypt features        ── public key + E(x) ──▶
                                                  run the tree on E(x),
                                                  never decrypting anything
                         ◀── E(credit limit) ──
 decrypt credit limit

The bank is basically a very sophisticated vending machine that operates in the dark. It pushes ciphertexts around, it never sees what’s inside them, and it still serves the right snack.

LightPHE supports two flavours of this, depending on what kind of questions the tree asks:

Nominal decisionsNumeric decisions
Node looks like“has stable income?” (yes / no)“income <= 40?"
AlgorithmIshai-PaskinDamgard-Geisler-Kroigaard (DGK)
Rounds of interaction12
Cost grows withdepth of the treenumber of nodes

We’ll set up the libraries first, go through both protocols, and then look at which cryptosystems can and cannot do this and why.

We’ll set up the libraries first, go through both protocols, and then look at which cryptosystems can and cannot do this and why.

One Protocol, Four Languages

LightPHE is a family of libraries with the same algorithms and the same API shape: LightPHE for Python, lightphe-go for Go, lightphe4j for Java and lightphe-ts for TypeScript. This matters more than it sounds. In real life, the customer is probably a browser or mobile app and the bank is probably a JVM or Go backend. Because all four ports use the same algorithms, a customer in TypeScript and a bank in Java can play the protocol together.

Every protocol snippet in this post comes in all four languages. Installation:

The only real difference between them is how each language writes down a tree: tuples in Python, nested arrays in TypeScript, `Node` / `Leaf` builders in Go and static `node` / `leaf` factories in Java. Also, TypeScript returns plaintexts as `bigint` (`5n` rather than `5`), because ciphertexts are huge numbers and JavaScript’s `number` would quietly round them into nonsense.



Part 1: Decision Trees with Nominal Decisions (Ishai-Paskin)

Here is the bank’s secret tree. Questions are numbered 0, 1 and 2, and leaves are credit limits in thousand dollars.

                  Q0: has stable income?
                 /no                    \yes
     Q2: owns a house?              Q1: has existing debt?
       /no        \yes               /no           \yes
      0            5               20         Q2: owns a house?
                                                /no       \yes
                                               5          10

Notice that Q2 appears twice. That’s fine: the customer answers each question once, and the tree can ask it wherever it likes.

Each question is written as `(question number, what to do if no, what to do if yes)`, and leaves are plain integers. Each language spells this in its own way:

The trick: selecting a branch without knowing which one

The key question is: how do you choose between two branches when you don’t know the answer?

You don’t choose. You compute both and blend them. Suppose a node asks bit `x`, the “no” branch evaluates to `v0` and the “yes” branch evaluates to `v1`. Then

v0 + x * (v1 - v0)

is `v0` when `x = 0` and `v1` when `x = 1`. That’s an arithmetic `if` statement. With an additively homomorphic scheme, the bank can compute it on an encrypted bit without the private key:

E(x)^(v1 - v0) * E(v0) = E(v0 + x * (v1 - v0)) = E(v_x)

Raising a ciphertext to a plain power is scalar multiplication, and multiplying two ciphertexts is homomorphic addition. Both are available with the public key alone.

Let’s walk through our customer, who answers stable income = yes, existing debt = yes, owns a house = no, so `x = [1, 1, 0]`. The bank evaluates bottom-up:

  1. The deepest Q2 node has leaves 5 and 10. The bank computes `E(x2)^(10 – 5) * E(5) = E(5 + 0 * 5) = E(5)`.
  2. Q1 has the leaf 20 on its “no” side and the result of step 1 on its “yes” side. And here is the catch: one side is a plain number and the other is already a ciphertext.

Step 2 is where it gets interesting. To blend `20` with `E(5)`, the bank needs to treat a ciphertext as if it were a plaintext and encrypt on top of it. In other words, it needs encryption layers like a Russian doll.

Layers of encryption, courtesy of Damgard-Jurik

Ishai-Paskin is built on the length-flexible Damgard-Jurik cryptosystem. At level `s`, Damgard-Jurik encrypts messages in `Z_{n^s}` into ciphertexts in `Z_{n^(s+1)}`. So a level-`s` ciphertext fits perfectly into the plaintext space of level `s+1`. That’s the property that makes everything work: every level of the tree wraps one more layer of encryption around the result.

That’s also why the customer encrypts each answer at every level up to the tree depth. The bank picks the level it needs at each node. When I ran the example with default settings, the encrypted bit at levels 1, 2 and 3 was 2041, 3065 and 4085 bits long. The ciphertext gets fatter by roughly one modulus per level, like me during the holidays.

The customer then peels the layers one by one, from outermost to innermost, and finds the credit limit at the center of the doll.

The code

Here is the full protocol in Python, Go, Java and TypeScript.

Path: stable income → existing debt → no house → 5K. Sorry, customer.

A few things worth pointing out, all of them covered by the unit tests:



  • The bank cannot peek. `bank_cs.decrypt(encrypted_limit)` raises `You must have private key to perform decryption`.
  • The output is re-randomized. Evaluating the same tree on the same input twice gives two different ciphertexts that decrypt to the same value. Without this, the bank could recognize repeated results.
  • The output is sealed. You cannot add to it or multiply it any more: `Output of a decision tree can only be decrypted. Homomorphic operations are not supported on it.` It’s a multi-layer onion, and the usual homomorphic operations aren’t defined on it.
  • Shared subtrees work. The tests build XOR and majority vote functions as trees where the same subtree object is referenced twice, and it is evaluated only once. Technically these are branching programs (DAGs), which is the term the original paper uses.
  • Shallow trees only, please. The result size depends on the depth, not on the number of nodes. That’s great. But each extra level adds a layer of bigger modular arithmetic, so things slow down noticeably as depth grows. Evaluating the 3-level tree above took about 0.65 seconds on my laptop with default keys.

Part 2: Decision Trees with Numeric Decisions (Damgard-Geisler-Kroigaard)

Real trees rarely ask “do you have a job?”. They ask “is income <= 40?". You *could* convert every threshold into a yes / no answer on the customer side, but that would require the customer to know the thresholds, which are exactly the bank’s secret. So we need the bank to compare an encrypted number with its own plain threshold. That is secure comparison, and it’s what Damgard-Geisler-Kroigaard (DGK) was built for.

The tree

Features are numbered 0 (age), 1 (income in thousand dollars) and 2 (number of open loans).

                  F1: income <= 40?
                 /yes                \no
       F0: age <= 25?          F2: open loans <= 2?
        /yes      \no            /yes           \no
       0           5            20              10

Each node is `(feature index, threshold, what to do if feature <= threshold, what to do otherwise)`, and leaves are plain integers. In each language:

Ingredient 1: secure comparison, bit by bit

The customer encrypts each feature **bit by bit**. For a node with threshold `y`, the bank computes for every bit position `i` something like

c_i = s + x_i - y_i + 3 * sum_{j > i} (x_j xor y_j)

The sum term is zero only above the most significant bit where `x` and `y` differ. So `c_i` can be zero only at that bit, and only if the difference goes in the direction we’re looking for. The bank then multiplies each `c_i` by a fresh random number, re-randomizes it, and shuffles the list. All the customer can learn from the list is “is there a zero in here or not?”

Two details I like a lot:

  • To handle `x == y` cleanly, the implementation compares `2x` with `2y + 1`. These two can never be equal, and `x <= y` holds exactly when `2x < 2y + 1`. Ties are boring, so we just make them impossible.
  • DGK’s plaintext space `u` is deliberately small (a prime of about 32 bits; mine was 3,565,056,647). That makes checking “does this decrypt to zero?” a single modular exponentiation. The customer never has to fully decrypt the blinded values.

Here’s what the customer actually receives when checking `120 <= 150` with 16-bit inputs: 17 ciphertexts, which decrypt to

[85587422, 2723005871, 3166605034, ..., 1940396645, 0, 595433989, ...]

There’s one zero in a pile of random numbers, so the answer is True. The customer learns nothing else, not even where the zero came from.

Ingredient 2: random flips so the customer cannot follow the path

If the customer learned every comparison result, they could reconstruct their path through the tree, and with a few queries, the thresholds too. So the bank flips a secret coin for each node and sometimes asks the opposite question (`x > y` instead of `x <= y`).

In my run, the bank flipped all three nodes. Here is what each side saw:

NodeReal AnswerCustomer Saw
income <= 40?FalseTrue
age <= 25?FalseTrue
open loans <= 2?TrueFalse

The customer is looking at a funhouse mirror. They encrypt their (meaningless to them) answers and send them back.

Ingredient 3: path costs and masked leaves

The bank now un-flips the encrypted answers homomorphically. For a bit `b`, `E(1 – b) = E(1) * E(b)^(u – 1)`, so negating is just public-key arithmetic. Then the bank walks the tree and computes an encrypted path cost for every leaf: the number of wrong turns on the path to it. Only the leaf actually reached has cost 0.

For each leaf with cost `c` and label `L`, the bank sends back the pair

( E(r1 * c),  E(r2 * c + L) )

with fresh random `r1, r2`, in shuffled order. For the reached leaf, `c = 0`, so the pair decrypts to `(0, L)`. For every other leaf, both parts are random junk. Here is what the customer got in my run:

[(3443173712, 1211872218), (3163581321, 242431768), (0, 20), (2803513138, 1482937286)]

Four leaves, one of them says `(0, 20)`, and the rest are noise. The customer can tell the tree has 4 leaves, but not which branch theirs was or what the other limits are.



The code

Here is the full protocol in Python, Go, Java and TypeScript.

Some notes:

  • `bank_state` holds the tree and the flips. It must never leave the bank. If it does, the funhouse mirror becomes a regular mirror.
  • Features and thresholds must be non-negative integers that fit into `bit_length` bits. So you need to quantize: income in thousands, age in years, ratios times 100, and so on.
  • Leaf labels must be integers in `[0, u)`, which is plenty for class labels or credit limits.
  • Since the flips are random, the unit tests run each sample several times and check every input combination against a plaintext evaluator. Randomized protocols deserve paranoid tests.

What Cryptographic Features Do We Actually Need?

Here’s the shopping list. If a cryptosystem is missing any of these, it can’t play.

Required for both:

  • Public-key encryption. The bank must encrypt (constants, leaf values, fresh layers) without being able to decrypt.
  • Additive homomorphism. To add things like `v0 + …`, path costs and masks.
  • Scalar multiplication (ciphertext to a plain power). To compute `x * (v1 – v0)`, to blind values with random multipliers, and to negate bits.
  • Ciphertext re-randomization. So two encryptions of the same value look unrelated. Without it, the customer or the bank could match ciphertexts and infer the path.

Required for nominal trees (Ishai-Paskin):

  • Layered encryption. A ciphertext at level `s` must be a valid plaintext at level `s+1`. This is what lets the result of a subtree become the input of its parent.

Required for numeric trees (DGK):

  • Secure comparison of an encrypted value against a plain one.
  • A cheap zero test The customer has to check many blinded values for zero, so this has to be fast.
  • Blinding and shuffling, so that everything except the bit we want to reveal looks random.
  • A bit of interaction DGK needs two round trips, while Ishai-Paskin needs one.

The first group is standard equipment for any additively homomorphic scheme. The last two items, layered encryption and cheap secure comparison, are the rare ones, so let’s open them up.

Layered Encryption, Up Close

Think of envelopes. A normal cryptosystem gives you one envelope size. Layered encryption gives you a whole set of envelopes, where each one is just big enough to hold a sealed envelope of the previous size.

Damgard-Jurik provides exactly that. At level `s`, it encrypts as

E_s(m) = g^m * r^(n^s) mod n^(s+1)

and the spaces line up like this, with a 1024-bit modulus `n`:

Level `s`Plaintext spaceCiphertext spaceCiphertext size
1`Z_n``Z_{n^2}`~2048 bits
2`Z_{n^2}``Z_{n^3}`~3072 bits
3`Z_{n^3}``Z_{n^4}`~4096 bits

Look at the diagonal: `Z_{n^2}` is the ciphertext space of level 1 and the plaintext space of level 2. So `E_2(E_1(m))` is well defined. A level-1 ciphertext is just a (big) number that level 2 is happy to encrypt. This matches what I measured earlier: 2041, 3065 and 4085 bits.

Now let’s trace the bank’s work on our customer (`x = [1, 1, 0]`) bottom-up. The *height* of a node is how far it is above the leaves, and a node at height `h` uses the customer’s bit encrypted at level `h`.

1- Deepest Q2 (height 1). Both children are plain: 5 and 10. The bank computes `E_1(x2)^(10 – 5) * E_1(5) = E_1(5)`. Result: a level-1 ciphertext.

2- Q1 (height 2). One child is plain 20, the other is `E_1(5)`. They’re at different levels, so the bank first *lifts* 20 by wrapping it in a fresh layer: `E_1(20)`. Now both children are level-1 ciphertexts, which are valid level-2 plaintexts, so the bank computes the formula below.

E_2(x1)^(E_1(5) - E_1(20)) * E_2(E_1(20)) = E_2(E_1(5))      since x1 = 1

Yes, the exponent is the difference of two ciphertexts treated as plain numbers modulo `n^2`. This line is the whole trick.



3- Q0 (height 3). The left child (the other Q2 node) evaluates to `E_1(0)` and gets lifted to `E_2(E_1(0))`. The right child is `E_2(E_1(5))`. With `E_3(x0)` and `x0 = 1`, the bank gets `E_3(E_2(E_1(5)))`.

The customer then peels the onion: decrypting at level 3 gives `E_2(E_1(5))`, at level 2 gives `E_1(5)`, and at level 1 gives `5`. The bank sent back one ciphertext, never decrypted anything and never learned which branch won.

Some consequences fall out of this picture:

  • Why the customer encrypts each answer at every level. A question can appear at any height in the tree, and the bank shouldn’t have to tell the customer where. So the customer sends `E_1(x_i)`, `E_2(x_i)` and so on up to the depth, and the bank picks what it needs. The input is `questions × depth` ciphertexts.
  • Why the output depends on depth, not size. The final result has as many layers as the tree has levels, no matter how many nodes are inside. A wide tree costs more work, but the answer doesn’t get bigger.
  • Why deep trees get slow. A node at height `h` does arithmetic modulo `n^(h+1)`. Each level up means bigger numbers, and exponentiation cost grows faster than the number size.
  • Why Paillier can’t do this. Paillier is Damgard-Jurik stuck at level 1. Its ciphertext `E_1(5)` is a ~2048-bit number, while its plaintext space is only `Z_n` (~1024 bits). Try to put the envelope inside an envelope of the same size, and half of it gets cut off by the modular reduction.

Cheap Secure Comparison, Up Close

The comparison has two parts: a formula that turns “is `x < y`?" into "is there a zero?", and a cryptosystem that answers "is this a zero?" very quickly.

Part 1: turning a comparison into a zero. Take a small example. The customer has `x = 5 = 0101` and the bank has threshold `y = 6 = 0110`. To check `x < y`, the bank computes for each bit `i`, from the most significant down:

c_i = 1 + x_i - y_i + 3 * (number of differing bits above i)
Bit `i`x_iy_iDiffering bits abovec_i
30001
21101
10100
01015

Why this works:

  • Above the first differing bit, `x_i – y_i = 0` and nothing differs above, so `c_i = 1`. Never zero.
  • At the first differing bit, `c_i = 1 + x_i – y_i`. That’s zero exactly when `x_i = 0` and `y_i = 1`, which is exactly when `x < y`.
  • Below it, the `3 * (…)` term is at least 3, and `1 + x_i – y_i` is between 0 and 2, so `c_i` is at least 3. Never zero.

So there is a zero in the list if and only if `x < y`. To ask the opposite question (the random flip from earlier), the bank replaces the leading `1` with `-1`.

The neat part is that the bank can compute all of this with the customer’s bits still encrypted. `y` is the bank’s own plain number, so XOR with a known bit is linear: `x_j xor 0 = x_j` and `x_j xor 1 = 1 – x_j`. Everything in `c_i` is a sum of encrypted bits and plain constants, so it’s just homomorphic addition and scalar multiplication. No ciphertext-by-ciphertext multiplication needed.

The bank still can’t send `[1, 1, 0, 5]` as it is, because that would leak the bit position and more. So it blinds each value by multiplying it with a fresh random `r_i` in `[1, u)`. Zero times anything is still zero. Since `u` is prime, a non-zero value times a random non-zero `r_i` is uniformly random. After re-randomizing and shuffling, the customer gets something like `[random, 0, random, random]`, and the only thing they can learn is “there’s a zero in there”.

Part 2: answering “is this zero?” fast. Look at how many zero checks the customer has to do. Each comparison produces `bit_length + 1` values (the extra one comes from the `2x` vs `2y + 1` tie trick), and each tree node is one comparison:

  • our tree: 3 nodes × 9 values = 27 zero tests
  • a 100-node tree on 16-bit features: 100 × 17 = 1,700 zero tests

With a general-purpose scheme, every zero test is a full decryption. DGK has a shortcut. A DGK ciphertext is

c = g^m * h^r mod n

where `n = p * q`, and the plaintext space `u` is a deliberately small prime of about 32 bits. The private key contains `p` and a secret 160-bit number `v_p` chosen so that `h^(v_p) = 1 mod p`, which kills the randomness, and `g^(v_p)` has order exactly `u`. So:

c^(v_p) mod p = (g^(v_p))^m mod p     which equals 1   if and only if   m = 0

That’s a single exponentiation with a 160-bit exponent modulo a 512-bit prime. Nothing more. Here is what it costs on my laptop with 1024-bit keys:

OperationTime
DGK zero test0.32 ms
DGK full decryption (baby-step giant-step over `u`)1.08 ms
Paillier full decryption14.3 ms

For the 1,700-test tree, that’s about half a second with DGK zero tests versus roughly 24 seconds if every check were a Paillier decryption. That’s a 45x difference, which is roughly the difference between “the app is loading” and “the user has left to make coffee”.

And the small plaintext space isn’t a weakness here. It’s the point. Comparison values never exceed `3 * (bit_length + 1)` (LightPHE checks that they fit into `u`), leaf labels and path costs are small integers, and the security comes from factoring `n` and the hidden subgroup, not from the size of `u`.



Which Algorithms Can Be Used, Which Cannot, and Why

LightPHE ships with more than 25 cryptosystems, and only two of them have the “Decision Tree Evaluation” checkmark in the feature table. That isn’t laziness. Let’s go through the rest and see why they don’t make the cut.

AlgorithmTree typeWhy it works
Ishai-PaskinNominal (yes / no)Built on Damgard-Jurik’s layered encryption, so a ciphertext can be encrypted again at the next level. Additive and scalar-multiplicative, so it can blend branches. Single round.
Damgard-Geisler-KroigaardNumeric (thresholds)Additive and scalar-multiplicative, with a tiny plaintext space (~32 bits) and a cheap zero test. Built specifically for secure comparison.

Caveats, Sincerely

I’d rather you hear these from me than from your security auditor:

  • Semi-honest model. Both protocols assume each party follows the steps faithfully and is only curious about the other’s data. A malicious bank could, for example, use a different tree than it claims. Protecting against that needs zero-knowledge proofs on top, which is a separate post.
  • Tree shape leaks a little. The customer learns the depth (Ishai-Paskin needs it to prepare the input) or the number of nodes and leaves (DGK). If that’s sensitive, pad the tree with dummy nodes.
  • Integers only. Features, thresholds and leaves must be integers, so quantize your floats. Your model was probably trained on floats. Don’t forget to scale them the same way at inference time.
  • Shallow beats deep for Ishai-Paskin. Every level adds a fatter layer. For deep trees, DGK’s cost scales more gently (linearly in the number of nodes), at the price of an extra round trip.

Conclusion

Encrypted decision trees let a bank keep its model secret and a customer keep their data secret, and both still get a correct answer. Out of the more than 25 cryptosystems in LightPHE, exactly two can pull this off:

  • Ishai-Paskin handles trees on yes / no questions in a single round, by nesting Damgard-Jurik encryption layers like a Russian doll.
  • Damgard-Geisler-Kroigaard handles trees on numeric thresholds, using secure comparison, random flips and masked path costs, so the customer finds exactly one `(0, label)` in a pile of noise.

Why only these two? A private decision tree needs additive homomorphism, scalar multiplication and re-randomization, plus either layered encryption (Ishai-Paskin’s superpower) or cheap secure comparison (DGK’s superpower). RSA and ElGamal can’t add. The XOR and AND schemes can’t scale values. Paillier and its additive cousins can evaluate a single node but can’t stack layers. The schemes that allow one multiplication stop after a single level. So if you remember just one thing from this post: yes / no questions → Ishai-Paskin, numeric thresholds → DGK.

And because the same algorithms are available in Python, Go, Java and TypeScript, the customer and the bank don’t even have to agree on a programming language. Considering how hard it is to get two engineers to agree on tabs vs spaces, that may be the most impressive part.

Everything in this post is in the LightPHE repo, along with its Go, Java and TypeScript ports. If you find it useful, a ⭐ on GitHub helps a lot. If you find a bug, open an issue. I promise not to evaluate it with a secret decision tree.

Support this blog financially if you do like!

Buy me a coffee      Buy me a coffee

Leave a Reply