1
$\begingroup$

The question is mainly stated in the title. I am new to lattices and I have a basic understanding of them but not something in depth. I was watching a presentation of of a VSS (Verifiable Secret Sharing) scheme that was using lattice based encryption and they mentioned that "We are using lattice based encryption which may come to a suprise because our protocol has good bandwidth in contrast to most lattice based schemes".

Questions:

  • I was wondering what is the crucial factor that makes lattice cryptographic schemes not bandwidth efficient?
  • As a follow up question are there any other resources that lattices are not efficient on them?
$\endgroup$
1
  • $\begingroup$ There are things that can be said (for example, I've recently written a paper on this topic for encryption), but its not clear to me how much of it is universal --- lattice-based encryption and signatures can be fairly different. $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 23, 2022 at 10:17

1 Answer 1

2
$\begingroup$

Efficiency is of course a relative term. Usually lattice-based systems are considered bandwidth inefficient in comparison to, say, RSA and elliptic curve systems where cryptograms are typically 1000s and 100s of bits respectively. For example for a notional level of security where breaking the cryptograms takes as much work as breaking AES-128 with a classical computer (128-bits of exhaustion work), it is widely held that an RSA modulus of 3072-bits or an elliptic curve group of 256-bits would be necessary.

There's some debate as to the correct way to assess the cost of attacks on lattice systems, but one can talk in broad brush strokes about where the increased bandwidth requirement comes from. Essentially, almost all lattice based cryptography will have a cryptogram where of the form an $n$-long vector of integers of size less than some value $q$. Such a cryptogram will be at least $n\lg q$-bits in size. The security of the system will rely on the hardness of finding a short vector among a lattice generated by similarly sized vectors. In an asymptotic and not very reliable sense, many people believe that it is possible to find such a vector with roughly $0.292n$-bits of work (see The General Sieve Kernel and New Records in Lattice Reduction by Albrecht et al for a deep technical survey). This coarse estimate suggests that $n$ should be taken at least 438 for the AES-128 level of security (and if we look at proposal such as Kyber, NTRU and SABER that aim to hit this level of security they typically have $n=500-512$).

The choice of $q$ is also somewhat arcane. Early proposals suggested taking $n^2<q<2n^2$, though recent parameter sets are closer to $q\approx n\log n$. I can't recall ever seeing a proposal with $q$ less than $n$ (ETA: Mark points out that the NIST 2nd round candidate and Chinese CACR choice algorithm LAC does have $q<n$). For the systems mentioned above $q$ is between 11 and 13 bits. The bandwidth for a single vector is now looking like 7144-bits of any scheme that aspires to the same level of (classical) security as AES-128 (these numbers are all very ballpark and should not be mistaken for a rigorous analysis). This is more than twice the bandwidth of RSA which many already consider quite heavyweight in terms of bandwidth. It is perhaps worth noting that for higher levels of security, the bandwidth requirements of RSA grow faster than those of lattice systems, but both look very inefficient in comparison to elliptic curves.

This analysis applies only to cryptograms and there are also questions as to the costs of transmitting public keys or systems where more information than a single vector is required. It should give some sense of the issues however.

$\endgroup$
8
  • 1
    $\begingroup$ Two things: 1. Some schemes use $q < n$ (although it is highly non-standard), namely LAC (NIST PQC rd 2, standardized by Chinese gov) uses $q = 257$ iirc. Second, even though elements of $\mathbb{Z}_q^n$ appear naturally in cryptosystems, one can often "compress" them to elements of $\mathbb{Z}_p^n$ for some $p < q$. This is done for all (round 3) NIST PQC KEMs. $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 23, 2022 at 13:40
  • 1
    $\begingroup$ One can say something (structurally) about why lattice-based cryptosystems are poor bandwidth (I sent a paper to TCC on precisely this topic, but haven't publicly posted it yet), but this at most half-answers the question, as it doesn't address the topic of signatures (and related topics). $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 23, 2022 at 13:44
  • 1
    $\begingroup$ @Mark The lattice signature schemes that I am familiar with have a vector as described as part of the signature and have key recovery solvable by the problem staled so that the same heuristic applies to blocking key recovery. I agree that there are other headaches around sampling blinding values that add additional contstraints but the $(\lambda\lg\lambda)/0.292$ analysis is still a lower bound. $\endgroup$
    – Daniel S
    Commented Jun 23, 2022 at 14:11
  • 1
    $\begingroup$ @Mark I agree that there are second order effects of bandwidths saving by rounding/modulus switching, but had hoped to avoid them and other variational details for a simple heuristic answer. The LAC is example is interesting and I shall add it. The main point though is that heuristically for a security level of $\lambda$ the cryptographic data will need to be asymptotically of size $c\lambda\lg\lambda$ and $c=1/0.292$ is not a terrible estimate at these sizes. $\endgroup$
    – Daniel S
    Commented Jun 23, 2022 at 14:15
  • 2
    $\begingroup$ @Mark, CACR is actually an academic association. It's SCA that makes the standards, and is a government organ. $\endgroup$
    – DannyNiu
    Commented Jun 24, 2022 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.