Study group: On the Circular Security of Bit-Encryption

The study group on May 8th 2012 was done by Anna Lisa and Gaven. They were talking about circular security.
In particular, they focused on the paper by Rothblum titled: ``On the circular security of Bit-Encryption`` .
Gaven started by intuitively introducing circular security: an attacker is able to obtain encryptions of messages that are related to the private key; and then pointed out the following conjecture:

(Conjecture 1) every semantically secure public-key bit-encryption scheme is circular secure.

Afterwards, he moved to formally define the notion of circular security by means of three different definitions: (1) with respect to key recovery; (2) with respect to message recovery; (3) with respect to indistinguishabilty of oracles.
All definitions allow the adversary to query an oracle (called KDM oracle) which on input a value i, outputs the encryption of the i-th bit of the private key. In the first definition, the adversary's goal is that of recovering the entire key on input the public key. In the second definition, the attacker on input the public key and the encryption of a bit b is asked to find out the value of b. Finally, in the third definition the adversary must distinguish whether she is talking to the KDM oracle or an oracle that always outputs the encryption of zero. The three definitions above are equivalent.
Gaven gave the ideas behind the proofs that definition (i) is equivalent to definition (i+1), for i in {1,2}; and to complete the equivalence circle, he showed that indistinguishability of oracles implies key-recovery: intuitively, given a key-recovery adversary, it can be used to distinguish between the KDM oracle and the other oracle ( that always answering with an encryption of zero). Indeed, if such adversary is talking to the KDM oracle then with non-negligible probability she finds the decryption key, otherwise it should be infeasible to find the key.  

Anna Lisa described and analyzed a bit-encryption scheme which is semantically secure but is not circular secure. The semantically security of the scheme relies on the l-multilinear Symmetric External Diffie Hellmann (l-MSXDH) assumption which is an extension of the SXDH.
To recall, SXDH assumption extends the Decisional Diffie Hellman (DDH) assumption to bilinear groups by assuming that there exist two cyclic groups of order prime p equipped with a bilinear map e, such that DDH assumption holds in both groups.  The l-MSXDH assumption extends SXDH assuming that there exist l groups G₁,…,G_l,  equipped with a multilinear map e, such that DDH assumption holds in all groups.
While there exist l-multilinear groups, for l>2, there is no candidate l-multilinear groups for which SXDH is conjectured to be hard. On the other hand there is also no evidence that such groups do not exist. Therefore, the construction that Anna Lisa explained should not be interpreted as a counterexample, but rather as an obstacle to proving the bit-encryption conjecture (Conjecture 1).

The encryption scheme (KeyGen, Enc, Dec) is as follows:
Let GS be any l-multilinear group scheme, i.e. a probabilistic polynomial-time algorithm that for every security parameter n produces a description of l+1 groups G₁,…,G_l,G_T of order p with generators, respectively g₁,…,g_l,g_T along with an efficiently computable l-multilinear map e that maps the first l groups to the (l+1)-th group.

KeyGen(1ⁿ)

  1.     Invoke the group scheme algorithm to obtain  
                                      params = (p, (G₁,…,G_l,G_T), ( g₁,…,g_l,g_T), e).
  2.     Select a 2 x l matrix X whose elements are in Z_p.
  3.     Set the 2 x l matrix U in such a way that, for each j=1, ..., l:
          - U[0,j] = g_j^{X[0,j]};
          - U[1,j] = g_j^{X[1,j]};

  4.     Select s at random in {0,1}^l and set α=\sum_{i=1}^{l}X[s_i,i] mod p.
  5.     The public encryption-key is (params,U,α) and the private decryption-key is (X,s).
         
         
Enc_{(params,U,α)}(σ)
   1.   Select at random r₁,…,r_l in  Z_p.
   2.   Output (g₁^{r₁},(U[σ,1])^{r₁}),...,(g_l^{r_l},(U[σ,1])^{r_l}).
         
Dec_{(X,s)}((c₁,d₁),...,(c_l,d₁))

   1. If  c₁^{X[0,1]} = d₁ output 0, otherwise 1.
  
Anna Lisa let us notice that the bit string s and the public value α are never used neither in the encryption or in the decryption algorithm. Indeed, they are meant to help the KDM attacker. If α is ignored and l=1, the scheme is semantically secure under DDH, hence there would be no need to use a bigger l. The idea is that having a big l>>log p, helps to keep semantic security even though α (which is public) is related to s. In the KDM setting instead, the attacker can obtain extra information about s (which is part of the private key) and use them to verify that α is consistent with s. 
         
Afterwards, Anna Lisa showed the correctness of the scheme which is straightforward and then moved to sketch the proof that the scheme is semantically secure under the l-multilinear SXDH assumption. The proof follows a standard hybrid argument.
Finally, she described the attack that shows the scheme to be not circular secure. The details of the attack can be found in the paper [Ro12] (pag.12).            


Gaven, then presented a further result: the bit-encryption conjecture (Conjecture 1) cannot  be proved by a black-box reduction. In other words, there cannot be any reduction of circular security of a bit-encryption scheme to semantic security of the same scheme that uses both the encryption scheme and the adversary as black-box.  In particular, a stronger result has been proved, that the circular security of every CCA-2 secure bit-encryption cannot be shown by means of a black box result.
Finally, Gaven has stressed the meaning of this last result. Such an impossibility result does not rule out the possibility that there exists a black-box construction of a circular secure bit-encryption scheme from any semantically secure bit-encryption scheme, it only rules out the possibility of proving (via black box reduction) that each semantically secure scheme is also circular secure without making any change to the encryption scheme.