How to compare performances of lattice-based and pairing-based IBE schemes

Question

I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption).

I've observed that performances of lattice-based schemes are often expressed in terms of $n$ (the dimension of the lattice) whereas pairing problems use the bit size $|G|$ of the elements of the underlying group(s) $G$ (and the cost of basic operations such as exponentiation or pairing).

Are these 2 quantities "equivalent"? For instance, is it relevant to say:

• keys of length $O(n)$ (in a lattice scheme) and $O(|G|)$ (in a pairing scheme) will have roughly the same size in practice
• encryption of cost $O(n^2)$ (in a lattice scheme) is quicker than $O(|G|^3)$ (in a pairing scheme)
• ...

Answer 1

It is very hard to give a concrete, "apples-to-apples" comparison of lattice-based and pairing-based IBE schemes. There are many reasons: the research surrounding concrete secure parameters for LWE is still evolving, efficient implementations of operations used in lattice-based IBE (e.g., discrete Gaussian sampling) are still works in progress, one can consider more efficient ring-based analogues, etc. etc.

However, it is possible to give meaningful asymptotic comparisons, at least up to poly-logarithmic factors, under reasonable hardness conjectures about lattices and pairings (so that we're normalizing to equivalent security levels).

To your specific questions: no, the dimension $n$ for LWE and the bit size $\log |G|$ are not equivalent. However, they are asymptotically close, up to polylog factors, in the following sense: for conjectured $2^\lambda$ security, we can set $\log |G| = O(\lambda)$ and $n = \tilde{O}(\lambda)$. For pairings, this implies that all key sizes are $O(\lambda)$. For lattices it implies:

• master public keys of size $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].

• user secret keys of size $\tilde{O}(n \cdot \ell)$ for $\ell$-bit messages [plain LWE], or $\tilde{O}(n)$ [ring LWE] for $\ell = O(n)$.

• encryption time of $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].

• etc. etc.

In short, for ring-LWE all relevant sizes and runtimes can be made $\tilde{O}(n)$, though the hidden polylog factors can be significant in practice.

Answer 2

No. The key factor is the security level - a scheme has n bits of security if it takes roughly $2^n$ work ($\approx$ time x space) to break. So one can compare for example Diffie-Hellman key exchange in finite fields and over elliptic curves at the 128 bit security level and conclude that EC are more efficient (that is why they were invented, after all).

For pairing-based schemes, there are pretty good and standardised heuristics that you'll find in the usual places such as the ENISA key lengths report. It depends a bit on the type of curve you use too.

For lattices - I'd personally consider all lattice-based cryptography highly experimental, as we don't have a well-agreed set of standards to define security levels there yet. I would expect that for any reasonable definition, ECC beats lattices hands down for efficiency though.