README.org

regev-crypto-system

About

An implementation of the cryptosystem proposed by Oded Regev

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Build and exec

You need stack to do it:

# build
rm -rf .stack-work && stack build
# exec
stack exec regev-crypto-system-exe

Analysis

Input

The app/Main.hs file contains the call of encryption and decryption of a byte [0, 0, 1, 0, 1, 0, 0, 1] with the following parameters:

• Security parameter n = 80
• Prime number p = 1973 between n^2 and 2n^2

Output

Since the algorithm is probabilistc, the encrypted message will be probably different on each call:

the encrypted msg is
[EncryptedBit {sumA = [181,373,1334,299,348,533,1537,1737,996,1094,1028,340,233,939,1583,1079,16,
1532,243,1749,1115,735,770,1006,948,699,1201,1500,797,1965,577,1558,198,734,678,872,299,1454,477,
485,448,1526,1004,1439,574,920,685,1138,582,867,602,16,812,1776,186,1014,1110,75,923,12,451,1480,
1635,829,122,72,272,1649,172,300,1081,978,1152,1847,1269,74,1599,1821,1072,392], sumB = 988},
EncryptedBit {sumA = [501,1318,1505,1359,216,1787,1163,668,1080,102,1267,684,656,599,1526,576,954,
1814,418,1922,1887,1698,251,1349,760,964,827,1372,852,1400,825,1308,524,278,844,1037,242,778,954,
189,1836,755,1633,293,1548,8,1417,1963,473,543,74,1160,15,1371,1934,1367,173,433,957,145,195,121,
98,898,1247,719,50,1571,690,154,1457,1148,444,36,485,117,1863,1867,1554,39], sumB = 1006},
EncryptedBit {sumA = [1527,118,1004,1614,1737,1850,1406,1845,478,957,841,294,18,993,766,1698,940,
188,1511,1727,409,1484,1093,845,1070,293,1380,1096,883,1786,129,1153,1322,747,1865,125,1635,878,
1841,1078,1453,719,154,445,96,737,1429,664,1640,186,141,1954,647,996,1254,920,136,346,1808,1288,271,
970,1726,501,563,191,1560,1650,85,685,1648,1319,9,702,526,929,476,1134,321,879], sumB = 1521},
EncryptedBit {sumA = [977,1129,1172,1651,985,620,959,755,1640,1857,1794,439,370,1512,956,577,4,433,
1005,1187,867,1706,1265,181,1940,984,843,231,1954,1450,296,1466,1115,1540,557,1332,592,1758,922,158,
1275,1661,34,466,1369,1650,256,131,1693,253,519,1438,441,1771,195,1599,317,1923,713,1111,1249,258,74,
1641,758,8,1780,849,437,45,64,878,881,150,349,123,1916,465,1322,1151], sumB = 1115},
EncryptedBit {sumA = [318,1734,1729,425,1011,585,1219,975,1913,600,1235,1693,465,169,609,1235,890,
1921,270,1659,527,1080,209,1232,1433,1574,1627,315,319,24,608,909,555,1358,259,621,18,1671,242,56,
925,1843,1585,1032,62,1249,42,497,1805,568,1457,1261,1508,1027,1024,1507,1178,1775,419,662,1781,1489,
1734,164,1000,391,507,10,1381,1955,387,95,1028,1405,1195,763,1803,742,966,267], sumB = 1250},
EncryptedBit {sumA = [981,770,1411,877,324,1374,1762,1821,1189,102,344,26,90,948,1445,861,834,1069,
1760,1591,680,1478,1673,1618,1839,663,1938,1245,330,1865,1736,1098,720,139,1880,858,1841,509,665,1236,
1868,1474,921,986,1731,153,1793,1778,900,478,1150,1851,816,1830,178,1503,377,945,539,1435,729,1113,927,
985,1146,1892,517,1128,1296,291,1369,1225,949,356,152,1629,1852,1109,1785,799], sumB = 1925},
EncryptedBit {sumA = [1549,30,1774,464,1535,19,398,1753,1350,1206,1673,1248,484,669,626,255,112,906,
1907,673,1453,674,1580,1144,1784,577,1767,1413,368,1865,1821,1747,401,954,1266,1110,519,242,1723,750,
444,1658,466,1576,1337,977,1507,1319,1744,145,214,81,57,500,1188,1481,475,394,570,91,1762,1720,1104,431,
973,1310,1222,632,567,1333,690,716,1557,1404,1121,1764,990,1541,1174,615], sumB = 1420},
EncryptedBit {sumA = [1537,477,1833,97,1089,491,561,47,151,1082,51,786,294,1236,1065,1295,409,92,1972,33,
829,1947,293,1363,767,526,1054,363,262,1387,1241,779,1028,470,1562,1287,403,1115,1244,529,710,1503,175,
142,1178,191,277,1127,1696,412,837,722,630,743,784,39,1217,1475,1898,661,922,802,558,863,1135,1958,851,
1107,1304,1598,1017,1524,41,260,714,1899,580,344,1768,57], sumB = 670}]


For a encryption schema with security of 80 bits and p = 1973, we have:

the privateKey size is 80 * (Int size)

the publicKey size is 1388862 * (Int size)

the encrypted bit size is 81 * (Int size)

the message size is 6561 * (Int size)

the decrypted msg is
[0,0,1,0,1,0,0,1]

With more security parameters

Using n = 128 and p = 1717

For a encryption schema with security of 128 bits and p = 17167, we have:

the privateKey size is 128 * (Int size)

the publicKey size is 5965806 * (Int size)

the encrypted bit size is 129 * (Int size)

the message size is 16641 * (Int size)

the decrypted msg is
[0,0,1,0,1,0,0,1]

How the algorithm works

Phi beta PDF

First we need to define the probability density function (PDF) phi_β:

• phi_β is normal distribution with mean = 0 and standard deviation = β/√(2*π)
• The discretization of a sample is done by multiplying it by p, rounding and applying mod p
• We will define χ using β = 1/((√n) log^2 n)

Ecryption schema

m is defined by p and n: m = (1+ε)(n+1)*log(p)

• Private key: choose uniformly s from (Zp)^n
• Public key:
  • Choose uniformly m vectors a_1, ..., a_m from (Zp)^n
  • Choose m errors e_i from Zp according to χ
  • Define b_i = <a_i , s> + e_i, where s is the private key
  • The public key is (a_i, b_i)_m
• Encrypt a bit:
  • Choose randomly a subset S of {1,...,m}
  • The encryption is the pair (sum(a_i), sum(b_i)) if the bit is 0, else the result is (sum(a_i), floor(p/2) + sum(b_i)), where i is an element of S in both cases
• Decrypt a bit:
  • Calculate r = b - <a,s> where (a,b) is the encrypted bit
  • if r is closer to 0 than to floor(p/2) mod p, then the bit is 0, else the bit is 1

Correctness proof

Since the errors sampled from χ are from a normal PDF with mean 0 and very small standard deviation, with m big enough, sum e_i is close to 0. The 0 encrypted bit is:

(a,b) = (sum(a_i), sum(b_i)) then
r = b - <a,s>
  = sum(b_i) - < sum(a_i), s >
  = sum(b_i) - sum( <a_i, s> )
  = sum(<a_i , s> + e_i) - sum( <a_i, s> )
  = sum(<a_i , s>) + sum(e_i) - sum( <a_i, s> )
  = sum(e_i)

Since sum(e_i) is close to 0, the bit must be 0.

When the encrypted bit is 1 we have the same, except r = sum(e_i) + floor(p/2), with the same argument, r is close to floor(p/2), then the bit must be 1.