5
$\begingroup$

If I would like to focus on only one signature scheme, and only one encryption based on lattices in a pedagogical context (to introduce the concept of lattice-based crypto to people familiar with cryptography)?

Is it possible to consider only one cryptographic problem in this context?

$\endgroup$
2
  • 1
    $\begingroup$ If you really want to see the lattices, but not go into to much crypto technicalities this is how I introduced it: github.com/lducas/bamenda/blob/master/notes.pdf $\endgroup$
    – LeoDucas
    Jan 30 at 4:49
  • $\begingroup$ I don't remember the full details of how to formulate this, so I'm not posting this as an answer, but I recall that there is a way to reduce RSA to a problem of finding the "best" lattice basis for a lattice with a fundamental region with volume $N$ (that's the determinant of the basis matrix if I recall). I think it is elementary to see that if $N=pq$ for two primes $p$ and $q$ then the "best" basis for the lattice on $\mathbb{Z}^2$ is $\{(p,0), (0,q)\}$ $\endgroup$
    – Amit
    Feb 2 at 17:27

1 Answer 1

2
$\begingroup$

This answer will only discuss LWE/SIS, but much of what is said could be extended to other assumptions (namely NTRU).

For encryption, the following is (roughly) canonical. It's also historically important --- it's the (secret key) cryptosystem Regev initially introduced in his paper introducing LWE.

You fix some distribution $\chi$ on $\mathbb{Z}_q^n$ (typically $\chi$ being i.i.d. Gaussians, or i.i.d. bounded uniform for simplicity). The secret is $s\gets \chi$ a draw from this distribution. To encrypt $m\in\mathbb{Z}_q$, you sample $A\gets \mathbb{Z}_q^n$, then output $(A, b:= As + e + m)$ where $e\gets \chi$.

This doesn't yet yield a correct cryptosystem (decrypting $b - As = m + e\neq m$). It can be made to be correct by encoding $m$ in an error-tolerant way, for example starting with $m\in\mathbb{Z}_p$ and encoding $m\mapsto (q/p) m\in\mathbb{Z}_q$. This is the cryptosystem Regev suggested (perhaps with $p = 2$), namely

  1. $\mathsf{KeyGen}$: sample $s\gets \chi$
  2. $\mathsf{Enc}_s(m)$ sample $A\gets \mathbb{Z}_q^n$, $e\gets \chi$, and return $(A, As + e + (q/p)m)$
  3. $\mathsf{Dec}_s(A, b)$: Return $\lfloor (b - As) / (q/p)\rceil = \lfloor m + e / (q/p)\rceil$. This is equal to $m$ if $|e / (q/p)| < 1/2$, or if $|e| <q / (2p)$.

I say this is roughly canonical as it is a key subroutine in

  • both methods of constructing PKE from lattices (random linear combinations of encryptions of zero, and "noisy diffie hellman")
  • all constructions of FHE.

in fact, most lattice-based encryption can be seen as doing the above, and

  • varying the ring $R = \mathbb{Z}_q$ arithmetic occurs over,
  • varying the encoding $m\mapsto (q/p)m$ one works with, or
  • applying an aforementioned generic (for lattices) SKE to PKE transformation,
  • using an LWR variant instead of an LWE variant (i.e. using "deterministic noise").

For signatures, things are a little less simple, because there are (at least) two main approaches to lattice-based signatures, namely

  • "Hash and Sign" (or "GPV") signatures, and
  • "Fiat Shamir with Aborts" (or "Lyubashevsky") signatures

that a priori seem quite different. They can be presented in a uniform way though, see theorem 1.4 of this paper.

Theorem 1.4 (Informal). Lattice-based Lyubashevsky signatures using the bit-decomposition Fiat-Shamir hash function are equivalent to lattice-based Hash-and-Sign signatures.

So in principle you can uniformly present a single lattice-based identification scheme that you convert into a signature in various ways, namely leading to either Hash and Sign or Fiat Shamir with Aborts signatures. I won't write as much about this though, as I haven't thought about it as much.

$\endgroup$

Your Answer

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

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