The Construction. →Let C : Fn F be the circuit to be compiled. In the following, let r = r (σ) denote the number ofmaskinginputs used in a circuit compiled according to the compiler of [11]. Recall that our compiler, given a circuit C, generates two copies C1, C2 of C (that operate on two copies of the inputs); compiles C1, C2into circuits Cˆ1, Cˆ2 using the circuit-compiler of [11]; generates the circuit Cˆ′TTT Tthat outputs the AND of Cˆ1, Cˆ2; generates a circuit 0 verifying that at least one of the copies Cˆ1, Cˆ2 uses well-formed masking inputs (i.e., its masking inputs are well-formed vectors); compiles 0 into ˆ0 using the circuit-compiler of [11]; and finally verifies “in the clear” that ˆ0 uses well-formed masking inputs. Wenow describe these ingredients in more detail.

The Construction. ∈ { }∈ ⌊ ⌋ ∈ { }−− −For any positivereal p < 1/2 and ε, we construct a code of rate R = 1 H(p) ε that is p-CCAsecure. We assume that 2ε < 1/2 p. For a messagelengthk N, the code length is n = k/R . For any message m 0, 1 k, the encoded codeword c 0, 1 n consists of ℓ blocks (B1, . . . , Bℓ), where each block Bi is of length b = c log n for some constant c > 0, and thus ℓ = n/(c log n). We setthe followingparameters: λ = nγ for a constant γ ∈ (0, 1), n′ = ⌊(k + λ)/R′⌋ = (ℓ − κ)b, κ = ⌈6λ/(R1R2b)⌉, where R′ is the rate ofREC, R1 = O(ε2/L2) is the rate of RS over F with |F| = 2R2b/2, and R2 = εO(1) is the rate of PRC.Setup Algorithm. On input a parameter 1n, the setup algorithm chooses four randomkeyss1, s2, s3, s4 ∈ {0, 1}n for two PRFfamilies F1 and F2, a MAC (Tag, Vrfy), and a PRC family PRC, respectively. The first PRF F1 consists