paper.md

title	tags	authors	affiliations	date	bibliography
Hypercomplex: abstract & fast header-only C++ template library for lattice-based cryptosystems in high-dimensional algebras	Cryptography Algebra Arbitrary-precision arithmetic C++	name orcid affiliation Maciek Bak 0000-0003-1361-7301 1	name index Independent Researcher, Switzerland 1	6 February 2023	paper.bib

Summary

The following work presents a C++ library that is dedicated to performing arbitrary-precise calculations on hypercomplex numbers from the Cayley-Dickson algebras [@schafer2017introduction]. Basic arithmetical operations as well as a few miscellaneous functions are implemented. Its most important feature is the support for encryption/decryption procedures for public-key lattice-based cryptosystems in high-dimensional algebras over truncated polynomial rings.

Statement of need

This is a highly specialised software package aimed mostly at computational mathematicians and scientists who operate on high-dimensional numbers, need to carry out arbitrary-precise calculations, or whose focus is the study of lattice-based, post-quantum cryptography (PQC). The library is well suited for a wide range of computationally-challenging projects, from investigating general algebraic properties per se to applied research where a hypercomplex framework serves merely as a mean to an end (as in previously mentioned cryptosystems).

Key features

• As a header-only C++ template code, its greatest advantage is the combination of speed, generic programming, and convenience for the end user. An open source license together with a template specialisation mechanism allows contributors to add support for custom objects, define specific functions, and extend the scope of the library.
• The most important specialisation, already included in the library itself, is the introduction of operations in hypercomplex algebras over truncated polynomial rings. These allow for many cryptographic applications as described in a dedicated section below.
• A template class specialisation introduces support for arbitrary high precision of calculations via the GNU MPFR library [@fousse:inria-00070266], for which the operators have been overloaded such that all the instructions are carried out on specific data structures.
• State of the art technology for software engineering:
  • CI/CD mechanism set up with GitHub Actions: automatic tests for library installation, source code inclusion, compilation, and execution,
  • extensive unit testing with the Catch2 framework [@catch2] alongside code coverage measurement uploaded to Codecov; current coverage: 100%,
  • source code linting with cpplint [@cpplint] - Google code style enforced, and
  • automatic documentation generation and hosting on GitHub Pages: building via Doxygen [@doxygen], publishing via GitHub Actions.

Cryptographic applications

In the following section we shall describe the mathematical foundations for the previously mentioned family of cyptosystems. Consider a polynomial convolution ring $\mathcal{R} = \mathbb{Z}[x] / (x^N - 1)$ with $N > 2$ being prime. Let $\mathcal{R}_p$ and $\mathcal{R}_q$ denote derived modular structures with coefficients from $\mathbb{Z}/p\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$, respectively. Every element of $\mathcal{R}$, $\mathcal{R}_p$, $\mathcal{R}_q$ may be writted down as:

\begin{equation}\label{eq:element} f = \sum_{i=0}^{N-1} f_i x^i \equiv [f_0, \ldots ,f_{N-1}] \end{equation}

where the addition operation $+$ refers to a regular element-wise addition of coefficients (modular for $\mathcal{R}_p$ and $\mathcal{R}_q$). Multiplication $\star$ within this structure is defined as:

\begin{equation}\label{eq:ringmul} f \star g = \sum_{i=0}^{N-1} (\sum_{k=0}^i f_k g_{i-k} + \sum_{k=i+1}^{N-1} f_k g_{N+i-k})x^i \end{equation}

with a final reduction modulo $p$ or $q$ in the modular quotient rings.

Based on the above, let us pick an integer $\lambda \geq 0$ and define three corresponding algebras, generated by the Cayley-Dickson process:

\begin{equation}\label{eq:algebras} \begin{aligned} \mathcal{A^\lambda} = { x_0 + \sum_{i=1}^{2^\lambda-1} x_i e_i | x_i \in \mathcal{R}}\ \mathcal{A_p^\lambda} = { x_0 + \sum_{i=1}^{2^\lambda-1} x_i e_i | x_i \in \mathcal{R_p}}\ \mathcal{A_q^\lambda} = { x_0 + \sum_{i=1}^{2^\lambda-1} x_i e_i | x_i \in \mathcal{R_q}} \end{aligned} \end{equation}

where the addition operation $+$ refers to ring addition defined above.

Note that $\forall x\in \mathcal{A^\lambda}: x = (a, b)$, where $a, b \in \mathcal{A^{\lambda-1}}$.

Multiplication $\times$ is defined recursively based on the conjugation operation $^*$ as below:

\begin{equation}\label{eq:recursivemultiplication} \begin{aligned} \mathcal{A^\lambda} \ni x^* = \begin{cases} x, & \lambda = 0\ (a, b)^* = (a^*, -b), & \lambda > 0 \end{cases}\ \ (a, b) \times (c, d) = (ac - d^b, da+bc^) \end{aligned} \end{equation}

which as well holds for the modular algebras, given a final reduction modulus $p$ or $q$.

Based on the above, let us define a general scheme for hypercomplex-based cyptosystems. Having agreed on $(N, p, q)$, Bob selects $F, G \in \mathcal{A^\lambda} : \exists F_p^{-1}\in\mathcal{A_p^\lambda} \wedge \exists F_q^{-1}\in\mathcal{A_q^\lambda}$.
A procedure to generate the public key $H\in\mathcal{A_q^\lambda}$ is then given by:

\begin{equation}\label{eq:publickey} H = F_q^{-1} \times G \mod q \end{equation}

Alice encrypts her message $M\in\mathcal{A_p^\lambda}$ into $E\in\mathcal{A_q^\lambda}$ with the use of a blinding element $\Phi\in\mathcal{A_q^\lambda}$ according to:

\begin{equation}\label{eq:encryption} E = p \otimes H \times \Phi + M \mod q \end{equation}

The following decryption consist of three steps:

\begin{equation}\label{eq:decryption} \begin{aligned} \mathcal{A_q^\lambda} \ni D_1 = (F \times E) \times F \mod q\ \mathcal{A_p^\lambda} \ni D_2 = D_1 \mod p\ \mathcal{A_p^\lambda} \ni D_3 = F_p^{-1} \times (D_2 \times F_p^{-1}) \mod p\ \end{aligned} \end{equation}

If the decryption was successfull, Bob receives $D_3 = M$ (up to coefficients' centered lift in $\mathcal{A_p^\lambda}$). Please remember that the lattice-based cryptography is always burdened with a chance of decryption failure due to an incorrect recovery of polynomial's coefficients. Also, for $\lambda \geq 4$ note that $\mathcal{A^\lambda}$ is neither alternative nor associative; thus successful decryption relies on a careful initial choice of $F$ (e.g. $F: \exists! i\in{0, \ldots ,2^\lambda-1}: F_i \neq 0$). For a more detailed coverage of similar cryptosystems please see publications presenting QTRU [@QTRU] and OTRU [@OTRU].

Three examples of matrix encryption-decryption are presented in the Figure 1. All of the data and code required to reproduce these results is available in the code repository.

   

State of the field

When it comes to a general hypercomplex framework, the well-known boost C++ libraries deserve the most notable mention here [@boost]. Unfortunately their scope is limited as they only implement classes for quaterions and octonions (however, as an upside, all the operations are well optimised). Moreover, these libraries do not support operations on MPFR types natively. It may also be worth mentioning the existence of smaller projects like those by @quaternions and @cd, but, unlike our work, they often lack proper test suites, code coverage reports, and documentation, and are also significantly restricted in functionality, which is a major drawback.

However, (most importantly) to our best knowledge, there is currently no high-quality open-source library that natively supports cryptosystems based on truncated polynomial rings. Previous research described distinct versions of NTRU [@NTRU], among others: 4-dimensional QTRU [@QTRU], 8-dimensional OTRU [@OTRU]; and a proposed 16-dimenisional STRU [@STRU], the correctness of which has not yet been verified. Despite these efforts, no generalization has been provided yet. Our work is the first to present that these procedures are vaild in arbitrarily high-dimensional Cayley-Dickson algebras (provided a careful choice of parameters of the system) and to provide reproducible examples of a successful encryption/decryption procedures. Finally, it has not escaped our notice that the specific polynomial-based hypercomplex multiplication scheme we presented immediately suggests a possible hashing mechanism for string messages.

Acknowledgments

We would like to express our wholehearted gratitude towards: the members of a Facebook group >implying we can discuss mathematics, who aided us with clarifications and suggestions related to the topic of research as well as a Cryptography Stack Exchange user DanielS, who helped us analyse and understand specifics of lattice-based cryptosystems.

References