MATLAB Model

function S = generatePrivateKey(m)
    global q;
    S = randi(q, [m, 1]);
end

function [A, B] = generatePublicKey(S, m, n)
  global q;
  A = randi(q, [n, m]);
  e = round(randn(n, 1));
  B = mod(A*S, q) + e;
end

function [u, v] = encryptBit(M, A, B)
  global q;
  sampleSize = fix(numel(B) / 4);
  samplesChoices = randsample(1:length(B), sampleSize);
  u = mod(sum(A(samplesChoices,:)), q);
  v = mod(sum(B(samplesChoices,:)) - M * fix(q/2), q);
end

function M = decryptBit(u, v, S)
  global q;
  D = mod(v - dot(S, u), q)
  M = D > q/4 & D < 3*q/4;
end

Source: lwe.m

Decryption Statistics

Decryption Statistics - Bad Private Key

m is sort of useless…

n has a negative effect

Large values of q are good

What Does This Mean?

• m - … whatever
• n - Keep this small!
• q - Make this large!

Team Orange

Andrew Nicholson

Andrew Wong

Arpit Rulania

Ziyue Lian