Editing One-instruction set computer (section)

=== Cryptoleq ===
[[File:Cryptoleq Processor.jpeg|thumb|Cryptoleq processor made at NYU Abu Dhabi]]
Cryptoleq<ref name=crq /> is a language similar to Subleq. It consists of one [[eponymous]] instruction and is capable of performing general-purpose computation on encrypted programs. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations {{math|''O''<sub>1</sub>}} and {{math|''O''<sub>2</sub>}} on three values A, B, and C:

 '''Instruction''' <syntaxhighlight lang="nasm" inline>cryptoleq a, b, c</syntaxhighlight>
     Mem[b] = O<sub>1</sub>(Mem[a], Mem[b])
     '''if''' O<sub>2</sub>(Mem[b]) ≤ 0
         IP = c
     '''else'''
         IP = IP + 3

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

In Cryptoleq operations {{math|''O''<sub>1</sub>}} and {{math|''O''<sub>2</sub>}} are defined as follows:

:<math>\begin{array}{lcl} O_1(x,y) & = & x^{-1} y \,\bmod\, N^2  \end{array}</math>

:<math>\begin{array}{lcl} O_2(x) & = & \left \lfloor \frac{x-1}{N} \right \rfloor  \end{array}</math>

The main difference with Subleq is that in Subleq, {{math|''O''<sub>1</sub>(''x,y'')}} simply subtracts {{mvar|y}} from {{mvar|x}} and {{math|''O''<sub>2</sub>(''x'')}} equals to {{mvar|x}}. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of {{math|''O''<sub>2</sub>}} corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. However, Cryptoleq implements fully homomorphic calculations and is capable of multiplications. Multiplication on an encrypted domain is assisted by a unique function G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the {{math|''O''<sub>2</sub>}} operation:

:<math>G(x,y) = \begin{cases} \tilde{0}, & \text{if }O_2(\bar{x})\text{ }\leq 0 \\ \tilde{y}, & \text{otherwise} \end{cases}</math>

where <math>\tilde{y}</math> is the re-encrypted value of {{mvar|y}} and <math>\tilde{0}</math> is encrypted zero. {{mvar|x}} is the encrypted value of a variable, let it be {{mvar|m}}, and <math>\bar{x}</math> equals {{tmath|Nm + 1}}.

The multiplication algorithm is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches. Cryptoleq encryption is based on [[Paillier cryptosystem]].