Introduction

I saw this tweet and found the concept interesting:

Liz Lovelace @liz_love_lace

Correction 2: your age-gap dating example is actually a Multi-Party Computation (MPC) problem, not an FHE problem.

View on Twitter

Suppose Alice and Bob want to enter into a relationship, and both are interested in a problematic age gap, a situation in which partners have an age difference that is socially taboo.

This post sets out to explore the question: Can Alice and Bob prove to each other that their age gap is problematic without revealing their ages?

Let's define some parameters:

• a is Alice's age
• b is Bob's age
• Alice and Bob want to ensure the other is 18 or older.
• The standard rule for age gaps states that one should never date someone less than half their age plus seven. I'm going to stick with this rule, but I'm sure there are any number of functions f(a: u8, b: u8) -> bool that could be substituted here. To keep things in the integer domain, we'll define acceptable(a, b) as 2a >= b + 14. Note that this only represents a one-way relationship. For full social acceptability, we would want acceptable(a, b) && acceptable(b, a)

Based on these constraints, Alice and Bob want to communicate the truth value of the following properties:

• p1: acceptable(a, b) (Alice is old enough for Bob)
• p2: acceptable(b, a) (Bob is old enough for Alice)
• p3: a >= 18
• p4: b >= 18

Alice and Bob are freaky, so they would prefer (p1, p2, p3, p4) to be (true, false, true, true) or (false, true, true, true). More normal individuals would of course prefer (true, true, true, true).

MPC (Mutually Problematic Computation)

What we want is a protocol where Alice and Bob each provide their age as a private input, and both of them learn (p1, p2, p3, p4) without leaking their age to the other party.

Garbled circuits

Garbled circuits are a good fit here, since we have two parties, private inputs, and a super simple computation. I could summarize how garbled circuits work here, but the Wikipedia page does a good job of it. Our problem actually isn't that far off from Yao's Millionaire Problem, a scenario where Alice and Bob want to know who is wealthier without revealing their wealth to each other.

For our problem, we want to make sure p1, p2, p3, p4 are a single circuit. If we had separate circuits, a malicious participant could strategically choose a different age each time to narrow down the other person's age.

The circuit itself is fixed: a comparator and an adder per direction, wired up to compute 2a ≥ b + 14, 2b ≥ a + 14, a ≥ 18, and b ≥ 18. We pre-compile the circuit once, hash the bytes, and pin the hash on this page so both parties can independently verify the circuit.

Demo

This demo uses the Tandem engine which wraps a circuit written in Garble. For communication, we use peer.js for the initial peer connection and WebRTC for the MPC communication. The STUN and TURN servers are from Cloudflare.

Information Leakage

Assuming our MPC protocol is secure and both parties have successfully communicated whether they have a problematic (but not overly problematic) age gap, information leakage is still a concern.

Human age is a pretty small set, wouldn't this potentially leak a lot of information?

This wikipedia page says the oldest person was ~123, so let's constrain a and b to [0, 123]. These numbers may vary in the case of LEV.

Let's say Bob is a three-letter agent tasked with investigating problematic age gaps. He doesn't care about his own gap, just learning the true age of his target (Alice).

The constraints

Bob knows b and observes (p1, p2, p3, p4). Each bit is an inequality on a:

• p1 = (2a ≥ b + 14) → a ≥ ⌈(b + 14) / 2⌉
• p2 = (2b ≥ a + 14) → a ≤ 2b − 14
• p3 = (a ≥ 18)
• p4 = (b ≥ 18) → tells Bob nothing about a (he already knows b)^{From Alice's perspective, p3 is the one that's free, and p4 carries information.}

Per-pair set size

The heatmap below shows, for every (a, b), how many ages Alice could be from Bob's vantage point after one MPC round. Hover for the actual interval.

Minimizing the age range

If Bob is picking his own b adversarially (and Alice doesn't know he's doing this), some choices are much better than others. Below: average size of Alice's possible-age set across all a ∈ [0, 123], as a function of b. Lower is better for Bob.

Under a uniform prior over Alice's age, the prior entropy is log₂(124) ≈ 6.95 bits. Bob's expected residual entropy is minimised at b = … with … bits remaining (~… equally-likely possible ages), an information gain of … bits per session.

Population-weighted

Real ages aren't uniform. Using single-year frequencies approximated from UN WPP 2024 5-year aggregates (World, both sexes) over ages 0..99^{5-year aggregate totals are spread evenly over their constituent ages. Truncated at 100 since WPP doesn't break out single-year counts in the 100+ band. Source: UN Population Division, World Population Prospects 2024.}, the prior entropy of Alice's age drops to … bits before any MPC round.

The per-b mean set size below is now weighted by P(a) instead of treating every age as equally likely. Set sizes for a values that are common (twenty-somethings) count more, set sizes for ages that are rare (the elderly) count less.

Bob's best b under the population prior is …, dropping conditional entropy to … bits (~… effective possible ages), an information gain of … bits in a single round. The optimum shifts down from b = 49 (uniform) to a younger value because the population's mass is concentrated on the young: a b near the mode of P(a) lets the half-your-age-plus-seven cutoffs slice the densest part of the distribution into the smallest groups.

For comparison, the worst case session for Bob leaks only … bits.

Conclusion

You probably clicked this thinking it was about the recent wave of age verification laws. Nope, that's a boring topic with a known answer. I've been putting 1/1/1990 into age selectors since I was in middle school and will continue to do so when it requires me to fake a smart card or whatever.

Age gap discourse on the other hand, is a more interesting topic. To answer the question we started with: Yes, Alice and Bob can determine whether they have a problematic age gap privately, but even that information leaks entropy, so they should be cautious. Some unsolved problems:

• Can a scheme be developed for multiple parties, e.g. polycules?
• "Half age plus seven" is a sort of rough rule. What properties do other rules have?
• Is someone going to use this demo for a kink thing and I just have to live with that?

I probably won't be exploring these questions further, but I had fun!

Source for the Rust crate that backs the demo (Garble circuit, Tandem glue, wasm-bindgen exports, Nix derivation): age-mpc-source.tar.gz.