SOLILOQUY: a New Primitive and a Quantum Attack

This week, Ana gave a study group talk based on the paper Soliloquy: a Cautionary Tale by Campbell, Groves and Shepherd of CESG (the Information Security arm of GCHQ).

The paper describes a new primitive, SOLILOQUY, a Key Encapsulation Mechanism, which was proposed secretly in 2007, found to resist classical cryptanalysis (for reasons omitted by the authors), but then abandoned due to the development of "a reasonably efficient quantum attack on the primitive". The paper is very complicated and appears to skip over a number of technical details, so we will present here a very high level view of SOLILOQUY and the attack, before mentioning some of the discussion about this result that has taken place, both in our study group and elsewhere in the academic community.

Construction of SOLILOQUY

Let $n$ be a prime, about 10 bits in size, and $\zeta$ a primitive $n$th root of unity. Let $K$ be the number field $\mathbb{Q}(\zeta)$ and $\mathcal{O}=\mathbb{Z}[\zeta]$ the ring of integers in $K$. One selects a candidate private key $\alpha = \sum_{i = 1}^{n}a_i\zeta^i \in \mathcal{O}$ where the coefficients $a_i$ are sampled from a discrete Gaussian distribution of mean 0 (so they are small). Let $p$ be the norm of $\alpha$. The pair $(\alpha, p)$ can be used as a SOLILOQUY key pair if

1. $p$ is prime
2. $c = 2^{\frac{(p-1)}{n}} \not\equiv 1 \: (\mathrm{mod}\: p)$

where condition 2 occurs with probability $1 - \frac{1}{n}$.

We check these conditions because, for a prime $p \equiv 1 \: (\mathrm{mod} \: n)$, the principal ideal $p\mathcal{O}$ decomposes into a product of prime ideals $\mathcal{P}_i$, each with a representation of the form $\mathcal{P}_i = p\mathcal{O} + (\zeta - c_i)\mathcal{O}$ where the $c_i$ are the non-trivial $n$th roots of unity mod $p$. The conditions above ensure that $\alpha\mathcal{O}$ is one of these $\mathcal{P}_i$ and that one of these $\mathcal{P}_i$ has the form $\mathcal{P} = p\mathcal{O} + (\zeta - c)\mathcal{O}$ for the particular choice $c = 2^{\frac{(p-1)}{n}}$. Then, since the Galois group $\mathrm{Gal}(K/\mathbb{Q})$ permutes the prime ideals $\mathcal{P}_i$, we can make sure that $\alpha\mathcal{O} = \mathcal{P}$ by taking some Galois conjugate of $\alpha$ (which will just reorder the coefficients $a_i$).

Now there is a natural homomorphism $\psi : \mathcal{O} \to \mathcal{O}/\mathcal{P} \simeq \mathbb{F}_p$ given by \[\psi(\epsilon) = \psi \left ( \sum_{i = 1}^{n}e_i \zeta^i \right) = \sum_{i = 1}^{n}e_i c^i \: (\mathrm{mod} \: p) = z\] and this is the encryption function in SOLILOQUY. One samples an ephemeral key $\epsilon$ from $\mathcal{O}$ as above, (whose coefficients must again be sampled with a mean of 0) and encapsulates it as $z$, viewed as a (rational) integer $0 \leq z < p$.

To decrypt, one computes $\epsilon = z - \lceil z\alpha^{-1} \rfloor \cdot \alpha$ where $\lceil - \rfloor$ is coordinate-wise rounding. That this is correct is not proved in the paper, but roughly corresponds to $\epsilon$ being small enough that $\lceil \epsilon \cdot \alpha^{-1} \rfloor = 0$. 

The Quantum Attack
Key recovery is an example of the small principal ideal problem: we have a representation $p\mathcal{O} + (\zeta - c)\mathcal{O}$ of the principal ideal $\mathcal{P} = \alpha\mathcal{O}$ of $\mathcal{O}$ and wish to compute the small generator $\alpha$. There are classical sub-exponential attacks for such a problem but the authors claim to provide the first 'practical' quantum algorithm for it. First, they make some simplifications, citing a 2004 result in Algebraic Number Theory that shows it suffices to look at the real subfield $\mathbb{Q}\left( \zeta + \zeta^{-1} \right)$ of $K$ and find $\alpha' = \alpha \cdot (\alpha)^*$ in the ring of integers $\mathcal{O}' = \mathbb{Z}\left [ \zeta + \zeta^{-1} \right ]$. Furthermore, they claim that in this setting it is easy to find a short generator of a principal ideal given any generator. So, to find $\alpha'$ (and hence find $\alpha$), it suffices to find any generator of $\alpha' \mathcal{O}'$.

The attack itself uses complicated ideas, but essentially amounts to using a logarithm function to transform the group of units $\mathcal{O}'^{\times}$ (with multiplicative structure) into a lattice $\Lambda$ (with additive structure). Then we consider an encoding of $\alpha'$ as a hidden, high-dimensional lattice $\Lambda_{\alpha'}$ with known sublattice $\Lambda$ of co-dimension 1. Then, using a "quantum fingerprint" of the hidden lattice, one can approximate the dual lattice $\Lambda_{\alpha'}^*$ (and iterate this procedure to produce many samples close to the true dual lattice). Then, with $\Lambda_{\alpha'}^*$, one can find a basis for $\Lambda_{\alpha'}$, determine the value of $\alpha'$ and hence find the secret key $\alpha$.

Discussion
While we were unable to examine the algorithm closely during the study group, some felt it was unclear how efficient the proposed attack is (even with quantum computers). Indeed, there has been a fair bit of discussion about the meaning of this paper in the academic community: see, for example, this thread.

While it is welcome that the researchers at GCHQ are sharing some of their work with the wider community, the paper is slightly unclear in places. It was felt that greater clarification was needed for the new attack to have impact beyond SOLILOQUY itself.