International Association
for Cryptologic Research

We show how to generalize lattice reduction algorithms to module lattices. Specifically, we reduce $\gamma$-approximate ModuleSVP over module lattices with rank $k \geq2$ to $\gamma'$-approximate ModuleSVP over module lattices with rank $2 \leq \beta \leq k$. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a high-dimensional generalization of the ($\Z$-)basis of a lattice. The particular value of $\gamma$ that we achieve depends on the underlying number field $K$, the order $R \subseteq \mathcal{O}_K$, and the embedding (as well as, of course, $k$ and $\beta$). However, for reasonable choices of these parameters, the approximation factor that we achieve is surprisingly close to the one achieved by ``plain'' lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension. In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehl\'e, and Wallet, which works in the important special case when $\beta = 2$ and $R = \mathcal{O}_K$ is the ring of integers of $K$ under the canonical embedding. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that block reduction generalizes LLL reduction.

Consider the representative task of designing a distributed coin-tossing protocol for n processors such that the probability of heads is $$X_0\in [0,1]$$. This protocol should be robust to an adversary who can reset one processor to change the distribution of the final outcome. For $$X_0=1/2$$, in the information-theoretic setting, no adversary can deviate the probability of the outcome of the well-known Blum’s “majority protocol” by more than $$\frac{1}{\sqrt{2\pi n}}$$, i.e., it is $$\frac{1}{\sqrt{2\pi n}}$$ insecure.In this paper, we study discrete-time martingales $$(X_0,X_1,\dotsc ,X_n)$$ such that $$X_i\in [0,1]$$, for all $$i\in \{0,\dotsc ,n\}$$, and $$X_n\in {\{0,1\}} $$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the information-theoretic setting mentioned above. In particular, for any $$X_0\in [0,1]$$, we construct martingales that yield $$\frac{1}{2}\sqrt{\frac{X_0(1-X_0)}{n}}$$ insecure coin-tossing protocols. For $$X_0=1/2$$, our protocol requires only 40% of the processors to achieve the same security as the majority protocol.The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $$X_0\in [0,1]$$, we show that there exists a stopping time $$\tau $$ such that The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, i.e., a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that any stopping time $$\tau $$ has Our lower-bound holds for all $$X_0\in [0,1]$$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $$X_0$$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018).By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.