Point and Permute

As described in the last subsection, the evaluator has to decrypt all the four ciphertexts of all the garbled gates, and extracts the valid label. This trial decryption results in 4 decryption operations and ciphertext expansion.

The point-and-permute optimization of garbled circuit in BMR90 only needs 1 decryption and no ciphertext expansion. It works as follows.

• For the two random labels of each wire, the garbler assigns uniformly random color bits to them. For example for the wire $a$, the garbler chooses uniformly random labels $X_a^0,X_a^1$, and then sets $\mathsf{LSB}(X_a^1)=1\oplus \mathsf{LSB}(X_a^0)$. Note that the random color bits are independent of the truth bits.

• Then the garbled gate becomes the following. Suppose the relation of the labels and color bits are $(X_a^0,X_a^1)\leftrightarrow (0,1)$, $(X_b^0,X_b^1)\leftrightarrow (1,0)$, $(X_c^0,X_c^1)\leftrightarrow (0,1)$

• Reorder the 4 ciphertexts canonically by the color bits of the input labels as follows.

• When the evaluator gets the input label, say $X_a^1,X_b^1$, the evaluator first extracts the color bits $(\mathsf{LSB}(X_a^1),\mathsf{LSB}(X_b^1))=(1,0)$ and decrypts the corresponding ciphertext (the third one in the above example) to get a output label.

Encryption Instantiation

The encryption algorithm is instantiated with hash function (modeled as random oracle) and one-time pad. The hash function could be truncated $\mathsf{SHA}256$. The garbled gate is then as follows.

For security and efficiency reasons, one usually uses tweakable hash functions: $\mathsf{H}(\mathsf{tweak},\cdot )$, where $\mathsf{tweak}$ is public and unique for different groups of calls to $\mathsf{H}$. E.g., $\mathsf{tweak}$ could be the gate identifier. Then the garbled gate is as follows. The optimization of tweakable hash functions is given in following subsections.