Cryptoleq

From Esolang
Jump to: navigation, search

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 O1

and O2 on three values a, b, and c :

Cryptoleq a, b, c      [b] = O1([a],[b]) ;
                       IP = c ,  if O2[b] ≤ 0
                       IP = IP + 3 , otherwise

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 O1 and O2 are defined as follows:

O1(x,y) = x-1N2  y  mod N2 
O2(x) = x-1 / N

where x and y are encrypted values based on a cryptographic parameter, N.

The main difference with Subleq is that in Subleq, O1(x,y) simply subtracts y from x and O2(x) equals to x. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of O2 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 G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the O2 operation. G(x,y) equals to encrypted zero if the O2 of the value Nm + 1 is equal or less than zero, m being the unencrypted x, or equals to the re-encrypted y otherwise. The multiplication algorithm is a top-down model that is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches.

External Resources