<gh_stars>10-100
%   rep.tex
%   2020-01-31  <NAME> <<EMAIL>>
%   Copyright (c) 2020, PQShield Ltd. All rights reserved.

\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{datetime}

%   urls
\usepackage{url}
\usepackage{hyperref}

%   note: tables require these -- add US-style thousand separator
\usepackage{numprint}
\npthousandsep{,}
\npdecimalsign{.}

\begin{document}

\begin{center}
    {\large {\bf r5embed numbers \pdfdate}}

\vspace{3ex}
\begin{tabular}{l p{90mm}}
{\bf Changelog} \\
\hline
2020-01-31  & <NAME> \verb|<<EMAIL>>| \\
            & {\it First measurements for new parameters.}  \\
2020-04-10  & {\it TupleHash, optimizations.}   \\
\hline
\end{tabular}
\end{center}

%   body text

\section{Round5 on Embedded, Mobile, and IoT}

A separate source distribution of Round5 without external library
dependencies is available from: \url{https://github.com/r5embed/r5embed}.

This codebase is smaller and more portable than the NIST reference code and
has been tested on various architectures (32/64 bit targets, big-endian, etc).
It forms the basis for our embedded testing and hardware-software codesign
(although those hardware drivers are not included in the above distribution).

\subsection{IoT Embedded Performance (Cortex M4)}

We used the ST STM32F407 Discovery board and the ``r5embed'' code base for our
for Cortex M4 performance and size measurements. This implementation
includes some ARMv7 assembler code for speeding up core ring and matrix
arithmetic for this ARM Cortex M4 (ARMv7E-M) reference target.

This particular MCU (and Cortex M4 in general) does not deploy a data cache --
a separate flash cache exists on the instruction bus. Code execution paths are
therefore designed to be constant, while there is some variation in the data
access paths. This implementation may be considered \emph{hardened} or
\emph{resistant} against a time-channel attack, while not strictly constant
time.

This updated implementation will be made available to the PQM4 joint Cortex M4
benchmarking effort\footnote{PQM4: Cortex-M4 post-quantum cryptography library:
\url{https://github.com/mupq/pqm4}.}. We note that during the second round of
the NIST competition Round5 had overall leading embedded performance according
to PQM4 data, although the margin is not particularly large. Compared to
some other candidates, the ``r5embed'' implementation is much smaller and more
of it is written in a high-level language, as it was written for portability.

Table \ref{tab:m4cycles} summarizes performance on the Cortex M4 target.
Note that the \verb|R5N1_3CCA_0smallCT| target has been excluded due to its
relatively large RAM requirement. Table \ref{tab:m4size} summarizes the
RAM, ROM (Flash), and bandwidth requirements of the ARMv7 implementation.

\begin{table}
\begin{center}
\begin{tabular}{| l | n{5}{0} n{5}{0} n{5}{0} | n{5}{0} |}
    \hline
    \multicolumn{1}{|l|}{\bf Variant} &
    \multicolumn{1}{r}{\bf KG} &
    \multicolumn{1}{r}{\bf Enc} &
    \multicolumn{1}{r|}{\bf Dec} &
    \multicolumn{1}{r|}{\bf Tot} \\
    \hline
    \verb|R5ND_1CPA_5d| & 425   & 607   & 247   & 1280  \\
    \verb|R5ND_3CPA_5d| & 839   & 1136  & 400   & 2376  \\
    \verb|R5ND_5CPA_5d| & 1455  & 1976  & 697   & 4129  \\
    \verb|R5ND_1CCA_5d| & 384   & 593   & 755   & 1734  \\
    \verb|R5ND_3CCA_5d| & 840   & 1253  & 1567  & 3661  \\
    \verb|R5ND_5CCA_5d| & 1386  & 2011  & 2563  & 5961  \\
%   \verb|R5ND_1CPA_0d| & 360   & 474   & 155   & 990   \\
%   \verb|R5ND_3CPA_0d| & 1223  & 1615  & 555   & 3393  \\
%   \verb|R5ND_5CPA_0d| & 1593  & 2141  & 719   & 4455  \\
%   \verb|R5ND_1CCA_0d| & 504   & 750   & 926   & 2181  \\
%   \verb|R5ND_3CCA_0d| & 832   & 1241  & 1505  & 3579  \\
%   \verb|R5ND_5CCA_0d| & 1161  & 1714  & 2047  & 4923  \\
    \verb|R5N1_1CPA_0d| & 6625  & 4488  & 1209  & 12323 \\
    \verb|R5N1_3CPA_0d| & 9935  & 7063  & 1849  & 18849 \\
    \verb|R5N1_5CPA_0d| & 34833 & 20891 & 4455  & 60181 \\
    \verb|R5N1_1CCA_0d| & 4166  & 3723  & 4051  & 11942 \\
    \verb|R5N1_3CCA_0d| & 17094 & 11986 & 13572 & 42654 \\
    \verb|R5N1_5CCA_0d| & 23206 & 16681 & 17949 & 57837 \\
    \verb|R5ND_0CPA_2iot| & 393 & 517   & 195   & 1106  \\
    \verb|R5ND_1CPA_4longkey| & 423 & 628 & 271 & 1324  \\
    \hline
\end{tabular}
\caption{Round5 performance on ARM Cortex M4 (STM32F407 Discovery)
    clocked at 24 Mhz. All of these numbers are in 1000s of cycles;
    {KG} = keypair generation, {Enc} = encapsulation, {Dec} = decapsulation,
    Tot = KG+Enc+Dec measured as a whole (both sides of an ephemeral
    key exchange). }
\label{tab:m4cycles}
\end{center}
\end{table}

\begin{table}
\begin{center}

    \begin{tabular}{| l | n{5}{0} n{5}{0} n{5}{0} | n{5}{0} n{5}{0} | n{5}{0} | }
    \hline
    &
    \multicolumn{3}{r|}{RAM (Stack) Usage in}   &
    \multicolumn{2}{r|}{Bandwidth for}  &
    \multicolumn{1}{r|}{ROM}        \\
    \multicolumn{1}{|l|}{\bf Variant}   &
    \multicolumn{1}{r}{\bf KG}          &
    \multicolumn{1}{r}{\bf Enc}         &
    \multicolumn{1}{r|}{\bf Dec}        &
    \multicolumn{1}{r}{\bf PK}          &
    \multicolumn{1}{r|}{\bf CT}         &
    \multicolumn{1}{r|}{\bf Code} \\
    \hline
    \verb|R5ND_1CPA_5d| & 3862  & 4317  & 2124  & 445   & 549   & 5894 \\
    \verb|R5ND_3CPA_5d| & 5598  & 6173  & 2708  & 780   & 859   & 7332 \\
    \verb|R5ND_5CPA_5d| & 7038  & 7717  & 3468  & 972   & 1063  & 4828 \\
    \verb|R5ND_1CCA_5d| & 3958  & 4405  & 5028  & 461   & 620   & 6248 \\
    \verb|R5ND_3CCA_5d| & 5638  & 6229  & 7164  & 780   & 934   & 7788 \\
    \verb|R5ND_5CCA_5d| & 7078  & 7781  & 9068  & 978   & 1285  & 5412 \\
%   \verb|R5ND_1CPA_0d| & 4526  & 4765  & 1716  & 634   & 682   & 3054 \\
%   \verb|R5ND_3CPA_0d| & 6054  & 6565  & 3676  & 909   & 981   & 3114 \\
%   \verb|R5ND_5CPA_0d| & 7542  & 8205  & 4628  & 1178  & 1274  & 3160 \\
%   \verb|R5ND_1CCA_0d| & 4518  & 4877  & 5620  & 676   & 740   & 3440 \\
%   \verb|R5ND_3CCA_0d| & 6150  & 6669  & 7772  & 983   & 1103  & 3554 \\
%   \verb|R5ND_5CCA_0d| & 8078  & 8757  & 10268 & 1349  & 1509  & 3586 \\
    \verb|R5N1_1CPA_0d| & 19286 & 19501 & 12996 & 5214  & 5236  & 3796 \\
    \verb|R5N1_3CPA_0d| & 26950 & 27221 & 19556 & 8834  & 8866  & 3804 \\
    \verb|R5N1_5CPA_0d| & 40934 & 41213 & 32324 & 14264 & 14288 & 3910 \\
    \verb|R5N1_1CCA_0d| & 19878 & 20109 & 25900 & 5740  & 5788  & 3892 \\
    \verb|R5N1_3CCA_0d| & 30206 & 30485 & 40204 & 9660  & 9716  & 4228 \\
    \verb|R5N1_5CCA_0d| & 37638 & 37933 & 52644 & 14636 & 14708 & 4164 \\
    \verb|R5ND_0CPA_2iot| & 3198  & 3501  & 1740  & 342 & 394   & 3618 \\
    \verb|R5ND_1CPA_4longkey| & 3830 & 4357 & 2180 & 453 & 563  & 5764 \\
    \hline
    \end{tabular}
    \caption{Round5 RAM (Stack) / ROM (Flash) and bandwidth usage on
        Cortex M4 (or any ARMv7). All numbers are in bytes:
        {KG} = keypair generation RAM,  {Enc} = encapsulation RAM,
        {Dec} = decapsulation RAM,      {PK} = public key (transmit),
        {CT} ciphertext (transmit),     {Code} = firmware size excluding
        Keccak and other standard  components (ROM or Flash).}
    \label{tab:m4size}
\end{center}
\end{table}

\subsection{Hardware-Software Codesign}

The lattice and ring arithmetic coprocessor in PQSoC\footnote{PQSoC:
Post-Quantum Crypto IP Data Sheet \url{https://pqsoc.com}} can support
Round5 directly. PQSoC is a self-contained SoC platform with a
RISC-V Core (RV32IMC ``Pluto'') and other peripherals such as a very
fast SHA-3 Keccak core.

We synthesized PQSoC with and without the ring arithmetic accelerator on
a Xilinx Artix-7 platform (Digilent Arty A7-35T board). Table
\ref{tab:fpgasize} indicates its relative size, which is very small.
Even with the CPU the implementation is smaller than some proposed
hardware modules; as a codesign it is minuscule.
From Table \ref{tab:pqsoc} we see that the performance advantage
gained from the coprocessor is between $664\%$ and $1382\%$, depending
on the variant.

Four DSP units are used by the multiplication unit of the RV32 CPU core,
and 1 by the the lattice unit. However, that is actually needed when
executing Round5 but are required by an another PQC algorithms. The ring
multiplication in Round5 is constructed entirely from additions and
subtractions.

\begin{table}
\begin{center}

    \begin{tabular}{| l | r r r |}
    \hline
    Artix-7 FPGA    & \multicolumn{2}{r}{Coprocessor?} & Area \\
    {\bf Component} & {\bf No } & {\bf Yes} & {\bf Delta} \\
    \hline
    SLICEL          & 1,525     & 1,533     & +8    \\
    SLICEM          &   626     &   691     & +64   \\
    LUT as Logic    & 7,064     & 7,720     & +656  \\
    LUT as Memory   &    48     &    48     & +0    \\
    Slice Registers & 2,626     & 3,336     & +710  \\
    DSP48E1         &     4     &     5     & +1    \\
    \hline
\end{tabular}
    \caption{Synthesis of PQSoC with and without the Round5 lattice
    coprocessor on a Xilinx Artix-7 (XC7A35) FPGA platform (Arty 7),
    indicating its size.}
    \label{tab:fpgasize}
\end{center}
\end{table}

The design achieves timing closure at 100 MHz -- that was also the clock
frequency used in timing runs. As can be seen, depending on (ring variant)
security level key generation requires $1.3 - 3.4$ ms,
encapsulation $1.7 - 4.5$ ms, and decapsulation
$0.9 - 6.2$ ms. What is noteworthy in comparison to monolithic
hardware implementations is that all of these options are available
\emph{simultaneously} via the same hardware module with very small additional
cost.

\begin{table}
\begin{center}
    \begin{tabular}{| l | n{3}{0} n{3}{0} n{3}{0}
                        | n{4}{0} n{4}{0} n{4}{0} | n{3}{2} |}
    \hline
        & \multicolumn{3}{c|}{With coprocessor}
        & \multicolumn{3}{c|}{Plain C Code} & {Speed} \\
    {\bf Variant}   & {\bf KG} & {\bf Enc} & {\bf Dec}
                    & {\bf KG} & {\bf Enc} & {\bf Dec} & {\bf Factor}     \\
    \hline
\verb|R5ND_1CPA_5d| & 137   & 195   & 89    & 888   & 1578  & 724   & 7.59  \\
\verb|R5ND_3CPA_5d| & 205   & 273   & 105   & 1937  & 3222  & 1329  & 11.12 \\
\verb|R5ND_5CPA_5d| & 346   & 450   & 164   & 4001  & 6595  & 2663  & 13.82 \\
\verb|R5ND_1CCA_5d| & 130   & 195   & 276   & 789   & 1387  & 1997  & 6.94  \\
\verb|R5ND_3CCA_5d| & 207   & 290   & 401   & 1939  & 3248  & 4575  & 10.86 \\
\verb|R5ND_5CCA_5d| & 338   & 458   & 627   & 3794  & 6257  & 8758  & 13.22 \\
\verb|R5ND_0CPA_2iot| & 127 & 166   & 73    & 761   & 1193  & 473   & 6.64  \\
\verb|R5ND_1CPA_4longkey| & 132 & 196 & 91  & 884   & 1653  & 801   & 7.96  \\
    \hline
    \end{tabular}
    \caption{Performance of Round5 on a lightweight RISC-V SoC with the
    lattice coprocessor and without. The numbers are in 1000s of cycles
    at 100 MHz (equivalent to 10 $\mu s$). Neither of the implementations
    uses assembly language. The hardware accelerator can be used with
    other CPU architectures as well.}
    \label{tab:pqsoc}
\end{center}
\end{table}

\end{document}

