Encrypted Lookup

Definition

Lookup returns the element stored at a secret index of a secret table:

with both the table $A$ and the index $i$ arriving encrypted. The machine that computes $v$ never learns which entry was requested.

Context

A lookup table is the oldest optimization in computing — precompute the answers, then index into them — and it turns any function small enough to tabulate into a single access. Encrypting the index turns that access into private information retrieval: the query is the index, and the index is nobody's business. On plaintext hardware indexing is free; homomorphically it becomes a selection over all $N$ entries, because the circuit cannot branch on a value it cannot see. Over an exact-integer scheme the selection can be an exact $0/1$ mask; over an approximate scheme it is a polynomial that must land close to a one-hot selector.

Parameters Defined by Specifications

A specification narrows the general operation into a concrete problem by pinning:

• the scheme and correctness regime — exact element recovery, or an approximation scored by closeness;
• the element domain and width, and the table length $N$;
• the index domain, $0 \le i < N$;
• the packing of the table and where the index rides;
• the rotation keys the answer may use, and what is measured.

Applications

Private information retrieval, oblivious RAM, and any table-driven computation over encrypted arguments: activation tables, S-boxes, piecewise functions, and branchy small functions all become a lookup the moment their argument is encrypted. It is a building block of confidential databases and of encrypted virtual machines, where an opcode's dispatch is itself a table indexed by secret state.