Logo IMG
HOME > PAST ISSUE > Article Detail


Alice and Bob in Cipherspace

A new form of encryption allows you to compute with data you cannot read

Brian Hayes

Noisy Arithmetic

In broad outline, here is Gentry’s FHE construction kit. He creates a cryptosystem with the usual encrypt and decrypt functions, which convert bits from plaintext to ciphertext and back. He also builds an evaluate function that accepts a description of a computation to be performed on the ciphertext. The computation is specified not as a sequential program but as a circuit or network, where input signals pass through a cascade of logic gates. Such circuits are most often assembled from Boolean gates (AND, OR, NOT, etc.), but they can also be specified in terms of addition and multiplication steps.

The evaluate function amounts to a complete computer embedded in the cryptosystem. In principle, it can calculate any computable function, provided that the circuit representing the function is allowed to extend to arbitrary depth. The depth of a circuit is the number of gates on the longest path from input to output. A full-powered computer must be able to handle circuits of arbitrary depth. Here the homomorphic system runs into a barrier. The problem is that ciphertext data are contaminated with numerical “noise”—slight discrepancies from their ideal values. Every arithmetic operation amplifies the noise, until eventually it overwhelms the signal.

2012-09HayesFC.jpgClick to Enlarge ImageThe origin of the noise lies in the probabilistic encryption process. Think of each ciphertext value as a point in space. The probabilistic encrypt function injects a smidgen of randomness into each of the point’s coordinates, displacing it slightly from the position it would occupy in a deterministic cryptosystem. The decrypt function filters out the noise by treating each point as if it were located at the nearest unperturbed position. When the noise is amplified by homomorphic computations, however, the point wanders farther from its correct position, until finally the decrypt function will associate it with an incorrect plaintext value.

Roughly speaking, each homomorphic addition doubles the noise, and each multiplication squares it. Hence the number of operations must be limited or errors will accumulate. Because of the limit on circuit depth, this version of the cryptosystem cannot be called fully homomorphic but only “somewhat homomorphic.”

The depth limit could be evaded in the following way: Whenever the noise begins to approach the critical threshold, decrypt the data and then re-encrypt it, thereby resetting the noise to its original low level. The trouble is, decryption requires the secret key, and the whole point of FHE is to allow computation in a context where that key is unavailable.

comments powered by Disqus


Subscribe to American Scientist