Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures

Abstract

We study a relaxed notion of lattice trapdoor called approximate trapdoor, which is defined to be able to invert Ajtai’s one-way function approximately instead of exactly. The primary motivation of our study is to improve the efficiency of the cryptosystems built from lattice trapdoors, including the hash-and-sign signatures.

Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert [Eurocrypt 2012]. In particular, we show how to use the approximate gadget trapdoor to sample short preimages from a distribution that is simulatable without knowing the trapdoor. The analysis of the distribution uses a theorem (implicitly used in past works) regarding linear transformations of discrete Gaussians on lattices.

Our approximate gadget trapdoor can be used together with the existing optimization techniques to improve the concrete performance of the hash-and-sign signature in the random oracle model under (Ring-)LWE and (Ring-)SIS assumptions. Our implementation shows that the sizes of the public-key & signature can be reduced by half from those in schemes built from exact trapdoors.

A The Smoothing Parameter of \(\varLambda _{ \mathbf {L} }\)

Recall the notations that $\mathbf {R} ' = \begin{bmatrix} \mathbf {R} \\ \mathbf {I} _{n(k-l)} \end{bmatrix}\in \mathbb {Z}^{m\times (n(k-l))}$, $\varSigma _p := s^2 \mathbf {I} _m - \mathbf {R} '( \mathbf {R} ')^t$. Here we derive the conditions of s so that $\sqrt{\varSigma _p \oplus \sigma ^2 \mathbf {I} _{n(k-l)}} \ge \eta _{\epsilon }(\varLambda _{ \mathbf {L} })$ holds, where $\varLambda _{ \mathbf {L} }$ is the lattice generated by

$$\begin{aligned} \mathbf {B} := \begin{bmatrix} - \mathbf {R} ' \\ \mathbf {I} _{n(k-l)} \end{bmatrix} . \end{aligned}$$

We do this in three steps: first we write out the dual basis of $\mathbf {B}$, then we reduce $\sqrt{\varSigma _p \oplus \sigma ^2 \mathbf {I} _{n(k-l)}} \ge \eta _{\epsilon }(\varLambda _{ \mathbf {L} })$ to a statement about the smoothing parameter of $\mathbb Z^{n(k-l)}$, and finally we find when $\sqrt{\varSigma _p \oplus \sigma ^2 \mathbf {I} _{n(k-l)}} \ge \eta _{\epsilon }(\varLambda _{ \mathbf {L} })$ as a function of s.

Dual basis, $\mathbf {B} ^*$ : Let $\varSigma = \varSigma _p \oplus \sigma ^2 \mathbf {I} _{n(k-l)}$. By definition, we need $\rho (\sqrt{\varSigma }^t \varLambda _{ \mathbf {L} }^*) \le 1 + \epsilon$. In general, the dual basis $\varLambda ^*$ is generated by the dual basis $\mathbf {B} ( \mathbf {B} ^t \mathbf {B} )^{-1}$. In the case of $\varLambda _{ \mathbf {L} }$, we can write the dual basis as

$$ \mathbf {B} ^* := \begin{bmatrix} - \mathbf {R} ' \\ \mathbf {I} _{n(k-l)} \end{bmatrix} \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-1}.$$

Reducing to $\eta _\epsilon (\mathbb Z^{n(k-l)})$ : Next, the gaussian sum $\rho (\sqrt{\varSigma }^t \varLambda _{ \mathbf {L} }^*)$ is equal to

$$\sum _{ \mathbf {x} \in \mathbb Z^{n(k-l)}} \exp (-\pi \mathbf {x} ^t( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^* \mathbf {x} ).$$

This reduces to showing $\sqrt{( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^*} \ge \eta _\epsilon (\mathbb Z^{n(k-l)})$.

Now we write out the matrix product $( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^*$,

$$\begin{aligned} ( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^*&= \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-t} \begin{bmatrix} -( \mathbf {R} ')^{t}&\mathbf {I} \end{bmatrix} \begin{bmatrix} \varSigma _p &{} \mathbf {0} \\ \mathbf {0} &{} \sigma ^2 \mathbf {I} \end{bmatrix} \begin{bmatrix} - \mathbf {R} ' \\ \mathbf {I} \end{bmatrix} \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-1} \\&= \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-t} \begin{bmatrix} ( \mathbf {R} ')^t \varSigma _p \mathbf {R} ' + \sigma ^2 \mathbf {I} \end{bmatrix} \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-1}. \end{aligned}$$

Before we continue, we consider the structure of the middle matrix:

$$\begin{aligned} \varSigma _s := ( \mathbf {R} ')^t \varSigma _p \mathbf {R} '&= \begin{bmatrix} \mathbf {R} ^t&\mathbf {I} \end{bmatrix} \left( s^2 \mathbf {I} - \sigma ^2\begin{bmatrix} \mathbf {R} \\ \mathbf {I} \end{bmatrix} \begin{bmatrix} \mathbf {R} ^t&\mathbf {I} \end{bmatrix} \right) \begin{bmatrix} \mathbf {R} \\ \mathbf {I} \end{bmatrix} \\&= \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + \mathbf {I} \end{bmatrix}\left( s^2 \mathbf {I} - \sigma ^2\begin{bmatrix} \mathbf {R} ^t \mathbf {R} + \mathbf {I} \end{bmatrix} \right) . \end{aligned}$$

Derive the condition for s : Now we will derive the condition for s so that

$$ \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-t}[\varSigma _s + \sigma ^2 \mathbf {I} ]\begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-1} \ge \eta ^2_\epsilon (\mathbb Z^{n(k-l)}). $$

Claim

All invertible matrices of the form $( \mathbf {R} ^t \mathbf {R} + \alpha \mathbf {I} )^i$ for $i \in \mathbb Z, \alpha \in \mathbb {R}$ commute.

Proof

Let $\mathbf {Q} \mathbf {S} \mathbf {V} ^t$ be $\mathbf {R}$’s singular value decomposition. Now, $\mathbf {R} ^t \mathbf {R} + \alpha \mathbf {I} = \mathbf {V} \mathbf {D} \mathbf {V} ^t + \mathbf {V} (\alpha \mathbf {I} ) \mathbf {V} ^t$ where $\mathbf {D} = \mathbf {S} ^t \mathbf {S} = \text {diag}(s^2_i( \mathbf {R} ))$ since $\mathbf {V} , \mathbf {Q}$ are orthogonal. Equivalently, we have $\mathbf {R} ^t \mathbf {R} + \alpha \mathbf {I} = \mathbf {V} \mathbf {D} _\alpha \mathbf {V} ^t$ where $\mathbf {D} _\alpha = \text {diag}(s^2_i( \mathbf {R} ) + \alpha ) = \mathbf {S} ^t \mathbf {S} + \alpha \mathbf {I} _{2n}$. By induction, we have $( \mathbf {R} ^t \mathbf {R} + \alpha \mathbf {I} )^i = \mathbf {V} \mathbf {D} _\alpha ^i \mathbf {V} ^t$, $i \in \mathbb Z$. Finally, $\mathbf {D} _\alpha ^i$ is a diagonal matrix so $\mathbf {D} _{\alpha }^i$ and $\mathbf {D} _{\alpha '}^j$ commute for all $\alpha , \alpha '$ since diagonal matrices commute. The result follows from the orthogonality of $\mathbf {V}$ ($\mathbf {V} ^t \mathbf {V} = \mathbf {I}$).

Claim A allows us to lower-bound the smallest eigenvalue of

$$\begin{aligned}( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^*&= \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-2} \left( \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + \mathbf {I} \end{bmatrix} \left[ s^2 \mathbf {I} - \sigma ^2\begin{bmatrix} \mathbf {R} ^t \mathbf {R} + \mathbf {I} \end{bmatrix}\right] +\sigma ^2 \mathbf {I} \right) \\&= \begin{bmatrix} \mathbf {R} ^t \mathbf {R} + 2 \mathbf {I} \end{bmatrix}^{-2} \left( s^2[ \mathbf {R} ^t \mathbf {R} + \mathbf {I} ] - \sigma ^2[2 \mathbf {R} ^t \mathbf {R} + ( \mathbf {R} ^t \mathbf {R} )^2]\right) .\end{aligned}$$

Viewing these matrices as their diagonal matrices of eigenvalues, we see $( \mathbf {B} ^*)^t\varSigma \mathbf {B} ^*$’s least eigenvalue is lower-bounded by

$$\begin{aligned} \lambda _{lb}(s, \mathbf {R} ) := \frac{s^2(s_{2n}^2( \mathbf {R} )+1) - \sigma ^2(s_1^4( \mathbf {R} )+2s_1^2( \mathbf {R} ) ) }{(s_1^2( \mathbf {R} )+2)^2} . \end{aligned}$$

Next, we assume $\sigma = \sqrt{b^2+1}\eta _\epsilon (\mathbb Z^{nk}) \ge \eta _\epsilon (\varLambda ^\perp _q( \mathbf {G} ))$ and solve for s using $\lambda _{lb}(s, \mathbf {R} ) \ge \eta ^2_\epsilon (\mathbb Z^{n(k-l)})$,

$$s^2 \ge \frac{s_1^2( \mathbf {R} )+ 1}{s_{2n}^2( \mathbf {R} )+ 1}\eta ^2_\epsilon (\mathbb Z^{n(k-l)}) + \frac{(b^2 + 1)(s_1^4( \mathbf {R} ) + 2s_1^2( \mathbf {R} ))}{s_{2n}^2( \mathbf {R} )+ 1} \eta ^2_\epsilon (\mathbb Z^{nk}).$$

This is

$$s \gtrsim \sqrt{b^2+1}\frac{s_1^2( \mathbf {R} )}{s_{2n}( \mathbf {R} )} \eta _\epsilon (\mathbb Z^{nk}).$$

We remark that the ratio $\frac{s_1( \mathbf {R} )}{s_{2n}( \mathbf {R} )}$ is a constant for commonly-used subgaussian distributions for $\mathbf {R}$’s entries [51].