# Cryptoleq

Cryptoleq is a language consisting of one, the eponymous, instruction, is capable of performing general-purpose computation on encrypted programs and is a close relative to Subleq. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations ${\displaystyle O_{1}}$ and ${\displaystyle O_{2}}$ on three values ${\displaystyle a}$, ${\displaystyle b}$, and ${\displaystyle c}$:

{\displaystyle {\begin{aligned}{\mathsf {Cryptoleq}}\ a,b,c\qquad [b]&=O_{1}([a],[b])\ ;\\\mathrm {IP} &=c,\ {\mathsf {if}}\ O_{2}([b])\leq 0\\\mathrm {IP} &=\mathrm {IP} +3,\ {\mathsf {otherwise}}\end{aligned}}}

where ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle c}$ are addressed by the instruction pointer, IP, with the value of IP addressing ${\displaystyle a}$, IP + 1 point to ${\displaystyle b}$ and IP + 2 to ${\displaystyle c}$.

In Cryptoleq operations ${\displaystyle O_{1}}$ and ${\displaystyle O_{2}}$ are defined as follows:

{\displaystyle {\begin{aligned}O_{1}(x,y)&=x_{N^{2}}^{-1}y\quad {\bmod {N}}^{2}\\O_{2}(x)&=\left\lfloor {\frac {x-1}{N}}\right\rfloor \\\end{aligned}}}

where ${\displaystyle x}$ and ${\displaystyle y}$ are encrypted values based on a cryptographic parameter, ${\displaystyle N}$.

The main difference with Subleq is that in Subleq, ${\displaystyle O_{1}(x,y)}$ simply subtracts ${\displaystyle y}$ from ${\displaystyle x}$ and ${\displaystyle O_{2}(x)}$ equals to ${\displaystyle x}$. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of ${\displaystyle O_{2}}$ corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. Cryptoleq though, implements fully homomorphic calculations and since the model is be able to do multiplications. Multiplication on an encrypted domain is assisted by a unique function ${\displaystyle G}$ that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the ${\displaystyle O_{2}}$ operation. ${\displaystyle G(x,y)}$ equals to encrypted zero if the ${\displaystyle O_{2}}$ of the value ${\displaystyle Nm+1}$ is equal or less than zero, ${\displaystyle m}$ being the unencrypted ${\displaystyle x}$, or equals to the re-encrypted ${\displaystyle y}$ otherwise. The multiplication algorithm is a top-down model that is based on addition and subtraction, uses the function ${\displaystyle G}$ and does not have conditional jumps nor branches.