  This paper makes a case for accelerating lattice-based post quantum
cryptography (PQC) with memristor based crossbars, and shows that these
inherently error-tolerant algorithms are a good fit for noisy analog MAC
operations in crossbars. We compare different NIST round-3 lattice-based
candidates for PQC, and identify that SABER is not only a front-runner when
executing on traditional systems, but it is also amenable to acceleration with
crossbars. SABER is a module-LWR based approach, which performs modular
polynomial multiplications with rounding. We map the polynomial multiplications
in SABER on crossbars and show that analog dot-products can yield a
$1.7-32.5\times$ performance and energy efficiency improvement, compared to
recent hardware proposals. This initial design combines the innovations in
multiple state-of-the-art works -- the algorithm in SABER and the memristive
acceleration principles proposed in ISAAC (for deep neural network
acceleration). We then identify the bottlenecks in this initial design and
introduce several additional techniques to improve its efficiency. These
techniques are synergistic and especially benefit from SABER's power-of-two
modulo operation. First, we show that some of the software techniques used in
SABER, that are effective on CPU platforms, are unhelpful in crossbar-based
accelerators. Relying on simpler algorithms further improves our efficiencies
by $1.3-3.6\times$. Second, we exploit the nature of SABER's computations to
stagger the operations in crossbars and share a few variable precision ADCs,
resulting in up to $1.8\times$ higher efficiency. Third, to further reduce ADC
pressure, we propose a simple analog Shift-and-Add technique, which results in
a $1.3-6.3\times$ increase in the efficiency. Overall, our designs achieve
$3-15\times$ higher efficiency over initial design, and $3-51\times$ higher
than prior work.
