Breaking Anonymity in IBE from Higher Residuosity

Wednesday 25th December 2019

In this post I want to address anonymity of an identity-based encryption scheme in my paper from PKC 2019 available here. Basically, the assumption presented in the paper to achieve anonymity for my scheme has been recently broken by Zhao et al. in this paper by describing a generalized Galbraith test for an IBE scheme, such as that described in my paper (extended from Boneh, Lavigne and Sabin), with $e > 2$ . So the new cryptograhic assumption made in my paper, namely the Special Polynomial Equation Solvability (SPES) assumption, turns out not to be a true. I was taking the wrong approach in the brief cryptanalysis section in the paper. In this post, I will describe the new Galbraith Test of Zhao et al and how it breaks the assumption along with code for it in Sage. Before that, before descrbing SPES, I will recall a definition from my paper but familiarity with the notation and terminology from the paper is advised.

Definition: Algebraic Equation Set

The algebraic equation set for a ciphertext $c(x) \in \hat{C}$ with respect to $a = H(\mathsf{id})$ is derived as follows. The unknowns are the coefficients $z_0, ..., z^{e - 1}$ of the polynomial $f(x)$ generated during encryption. Raising $f(x)$ to the power of $e$ and reducing according to the equivalence relation $x^e \equiv a$ induced by the quotient of the ring $\mathbb{Z}_N^\ast[x]/(x^e - a)$ yields a set of $e$ multivariate polynomials in $z_0, ..., z^{e - 1}$ of degree $e$ , one for each coefficient of the result. The algebraic equation set is formed by letting the polynomial for the $i$ -th coefficient of the result equal to $c_i$ for $i \in {0, \ldots, e - 1}$ . For example, the algebraic equation set for $e = 3$ is $$\begin{align} z_0^3 + a z_1^3 + a^2 z_2^3 + 6a z_0 z_1 z_2 = c_0 \\\\ 3z_0^2 z_1 + 3a z_0 z_2^2 + 3a z_1^2 z_2 = c_1 \\\\ 3z_0^2 z_2 + 3z_0 z_1^2 + 3a z_1 z_2^2 = c_2 \end{align}$$

So basically, SPES is the assumption that checking solvability of the above set of multivariate polynomial equations is hard. This turns out to be an invalid assumption because there is a better way to look at the problem that yields an efficient generalized Galbraith test that breaks anonymity in the Boneh, Lavigne and Sabin (BLS) scheme and related schemes.

Galbraith Test of Zhao et al. for small $e \ge 2$

I suggest reading Zhao et al. first; I will briefly recall the ideas here. Now let $a = H(\mathsf{id})$ and consider a ciphertext polynomial $tf(x)^e \in \mathbb{Z}_N[x]/(x^e - a)$ , which is in simplified (albeit less efficient) BLS form as considered in my paper, where $t \xleftarrow{\$} \mathbb{Z}_N$ and $f(x)$ is a random polynomial of degree $e - 1$ over $\mathbb{Z}_N$ . Now consider the power residue symbol over a function field $\mathbb{F}_p[x]$ , which we denote as $\left(\frac{\cdot}{\cdot}\right)_{e, \mathbb{F}_p}$ . The derivation in equation (1) in Section 5.2 of Zhao et al. shows that \[\left(\frac{tf(x)^e}{x^e - a}\right)_{e, \mathbb{F}_p} = 1 \mod{\mathfrak{p}}\] where $(\mathfrak{p})$ is the ideal defined in Section 3.1 of my PKC paper. The same identity holds over $\mathbb{F}_q[x]$ and with the ideal $(\mathfrak{q})$ . If we compute the above with a random ciphertext, we will get a random residue symbol. The next question that arises is how to compute $\left(\frac{tf(x)^e}{x^e - a}\right)_{e, \mathbb{F}_p}$ . The trick is to repeatedly apply the general reciprocity law to $\left(\frac{tf(x)^e}{x^e - a}\right)_{e, \mathbb{F}_p}$ until we get a polynomial of degree $1$ i.e. we have \[\left(\frac{tf(x)^e}{x^e - a}\right)_{e, \mathbb{F}_p} \equiv \left(\frac{c_p}{\mathfrak{p}}\right)_e \left(\frac{\alpha_p}{\mathfrak{\Phi(x)}}\right)_e \mod{\mathfrak{p}}\] where $\alpha_p, c_p \in \mathbb{F}_p$ and $\Phi(x) \in \mathbb{F}_p[x]$ with $\mathsf{deg}(\Phi(x)) = 1$ . The analogous congruence holds for $(\mathfrak{q})$ . Of course we will be working over $\mathbb{Z}_N[x]$ so when we apply the reciprocity law, we will get $\gamma_N \equiv \alpha_p \mod{p}$ (think of the analogous for $q$ ) and $ c_N \equiv c_p \mod{p}$ . So in short, the Galbraith test $G_e$ for small $e \ge 2$ is defined as follows \[G_e(a, c(x)) = \left(\frac{c_N\gamma_N}{\mathfrak{N}}\right)_e\]. This is the familar power residue symbol we compute in our paper (i.e. with the ideal $(\mathfrak{N})$ ). For random ciphertexts $c(x)$ , the value $G_e(a, c(x))$ is conjectured by Zhao et al. to be uniform on the set of residue symbols whereas for a ciphertext that is genreated honestly with identity $\mathsf{id}$ (recall that $a = H(\mathsf{id})$ ) then with all but negligible probability we have that $G_e(a, c(x)) = 1$ . Therefore, we have an efficient test that breaks anonymity in BLS and related schemes. So now, I will give the code in Sage that implements the Galbraith test and allows you to run it on honest ciphertexts and random ciphertexts and see the results. The variable name conventions follow Zhao et al. You must first call setup_ideal with parameters $N$ , $e$ and $\mu$ where $\mu$ is a generator in $\mathbb{Z}_N$ . Because Sage does not implement an efficient algorithm for the residue symbol with composite (in our case, semiprime) ideals, you can only experiment for the moment with toy parameters i.e. small $N$ . The class BLSAnonTester can be instantiated with $R_{\mathsf{id}} = H(\mathsf{id})$ , prime $e$ and the ideal generated by setup_ideal. Then you can create honest ciphertexts or random ciphertexts and run the method gt to evaluate the Galbraith test. Now the code:


def setup_ideal(N, e, mu):
    F.<z> = NumberField(cyclotomic_polynomial(e))
    a1 = N*F.ring_of_integers() + (z - mu)*F.ring_of_integers()
    return a1

def find_params(a, b):
    c = 1
    while a.degree() > 0:
        next_a = b % a
        next_b = a

        c *= -1^(a.degree() * b.degree()) * a.lc()^b.degree() * b.lc()^(-a.degree())
        a = next_a
        b = next_b
    gamma = a
    return (c, gamma)

def rand_inv_elem(ZN):
    r = ZN.random_element()
    while not r.is_unit():
        r = ZN.random_element()
    return r

class BLSAnonTester(object):
    def __init__(self, Rid, e, a1):
        self.Rid = Rid
        self.e = e
        self.a1 = a1
        self.ZN = Rid.parent()
        R.<x> = ZN['x']
        self.R = R
        self.S = R.quotient(x^e - Rid)

    def gen_ct(self, m):
        f = self.S([rand_inv_elem(self.ZN) for i in range(self.e)])
        g = f^self.e
        t = rand_inv_elem(self.ZN)
        while J(t) != m:
            t = rand_inv_elem(self.ZN)
        return t*g

    def rand_ct(self):
        return self.S([rand_inv_elem(self.ZN) for i in range(self.e)])

    def J(self, t):
        z = self.a1.ring().gen()
        smap = {z^i : i for i in range(e)}
        return smap[self.a1.ring()(t).residue_symbol(self.a1, self.e)]

    def gt(self, c):
        c = self.R(c.list())
        modulus = self.R.gen()^self.e - self.Rid
        try :
            cn, gamma = find_params(c, modulus)
            return self.J(cn * gamma)
        except Exception as ee:
            return None

So that's it. We can break anonymity in BLS and related schemes. Thanks for reading and Happy Christmas.

home / posts

Breaking Anonymity in IBE from Higher Residuosity

Galbraith Test of Zhao et al. for small $e \ge 2$