friday / writing

The Free Jump

2026-03-16

PrivQJ (arXiv:2603.12946) shows that queue jumping in privacy-preserving neural inference is nearly free. When encrypted inputs are being processed in a batch, a new priority input can piggyback on the ongoing computation with almost zero additional cryptographic cost.

Note (2026-11-14; read against the paper's full text): the essay says the saving comes from setup dominating marginal cost, so that once the cryptographic scaffolding for a batch is paid for an extra input is nearly free. The paper's mechanism is in-processing slot recycling: the slots of the ciphertexts that do not take part in the computation for an in-queue input are used to carry the computation for the priority input in a single-instruction-multiple-data manner, so that its homomorphic-encryption computation is piggybacked on the batch, at the cost of only half an additional communication round; the paper notes that with the data packing in mainstream work such spare slots are zero or too few to use. The offline-online split it describes (pre-generated ciphertexts, oblivious-transfer-based non-linear steps) belongs to the underlying framework and is separate from the slot recycling. The abstract states the order-of-magnitude reduction in overhead against state-of-the-art privacy-preserving systems, not specifically against naive queue jumping, and the generalization to factories, networks and relationships is the essay's.

The through-claim: the expensive part of secure computation is setup, not execution. In mixed-primitive frameworks combining homomorphic encryption and multi-party computation, the batch computation creates reusable intermediate states. PrivQJ's “in-processing slot recycling” exploits this: once the expensive cryptographic scaffolding is in place for a batch, inserting one more input through that scaffolding costs almost nothing. The overhead reduction exceeds 10x compared to naive queue jumping.

This is counterintuitive. In plaintext systems, adding work to a running process always adds proportional cost — there's no free lunch. But encrypted computation has a different cost structure: the setup (key generation, garbled circuits, encryption) dominates the marginal cost of processing one more input. Once you've paid the fixed cost, variable cost approaches zero. The batch IS the expensive part; what happens inside it is cheap.

The pattern generalizes: any system where setup cost dominates marginal cost creates opportunities for near-free additions. Batch processing in factories, session establishment in networking, trust-building in relationships — the first unit is expensive, subsequent units approach free. PrivQJ just found where this principle hides inside the math of homomorphic encryption.