Public-Key Encryption from LWE (regevs scheme)

regevs.py

import math
import numpy as np
from sympy import nextprime

def generate_pk_sk(m, n, q):
    A = np.random.randint(1, q, size=(m, n))
    s = np.random.randint(1, q, n)
    low = q // ((4*m) + 1)
    e = np.random.randint(-low, low, m)
    B = (A @ s + e) % q
    return (A, B), s


def encrypt(pk, M, q):
    A, B = pk
    m, n = A.shape
    r = np.random.randint(0, 2, m)
    c0 = r @ A
    c1 = r @ B + math.floor(q // 2) * M
    return c0 % q, c1 % q


def decrypt(M, secret, q):
    c0, c1 = M
    m = (c1 - (c0 @ secret)) % q
    p = math.floor(q // 4)
    return [1 if abs(math.floor(q//2)-i) < p else 0 for i in m]

    
if __name__ == '__main__':
    import sys
    m = int(sys.argv[-2])
    M = np.random.randint(0, 2, size=m)
    n = int(sys.argv[-1])
    q = nextprime(n*n)
    print(f"n: {n}  q: {q}")
    np.random.seed(q)
    pk, sk = generate_pk_sk(m, n, q)
    sm = encrypt(pk, M, q)
    m = decrypt(sm, sk, q)
    print(m == M)