This is a repository implementing a few lattice algorithms implemented in Python and Sage.
The files containing the algorithm source code can be found in the Lattice Algorithms folder.
Implementation of the Congruential Public Key Cryptosystem as described in Section 7.1 of An Introdution To Mathematical Cryptography, Second Edition by Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman.
Function to generate public-key private-key pair.
Returns -> (PubKey, PrivKey); where PubKey = (q, h) and PrivKey = (g, h)
Function to encrypt the message using the supplied public key.
pubkey: The public-key tuple
msg: The message to be encrypted (integer representation)
Returns -> The encryption of msg under pubkey (integer representation)
Function to decrypt the ciphertext using the supplied keys.
pubkey: The public-key tuple
privkey: The private-key tuple
ciphertext: The ciphertext to be decrypted (integer representation)
Returns -> The decryption of the ciphertext under pubkey and privkey (integer representation)
Implementation of Merkle-Hellman Knapsack Cryptosystem.
Function to generate the public-key from a private-key.
privkey: The private-key tuple
Returns -> PubKey
Function to encrypt the message using the supplied public key.
pubkey: The public-key tuple
msg: The message to be encrypted (integer representation)
Returns -> The encryption of msg under pubkey (integer representation)
Function to decrypt the ciphertext using the supplied keys.
pubkey: The public-key tuple
privkey: The private-key tuple
ciphertext: The ciphertext to be decrypted (integer representation)
Returns -> The decryption of the ciphertext under pubkey and privkey (integer representation)
Implementation of Gram-Schmidt Orthogonalisation.
Function to perform Gram-Schmidt Orthogonalisation.
basis_vectors: The list of basis vectors upon which to perform Gram-Schmidt Orthogonalisation
Returns -> Gram-Schmidt Orthogonalised vectors derived from basis_vectors
Implementation of Babai's Closest Vertex Algorithm to solve apprCVP in a lattice.
Function to solve apprCVP using Babai's Closest Vertex Algorithm.
basis_vectors: The list of basis vectors for the lattice
w: The vector whose apprCVP in the lattice has to be solved
Returns -> A vector of the solution of apprCVP of w in the lattice obtained by the algorithm
Implementation of Babai's Closest Plane Algorithm to solve apprCVP in a lattice.
Function to solve apprCVP using Babai's Closest Plane Algorithm.
basis_vectors: The list of basis vectors for the lattice
t: The vector whose apprCVP in the lattice has to be solved
Returns -> A vector of the solution of apprCVP of w in the lattice obtained by the algorithm
Implementation of the Goldreich–Goldwasser–Halevi (GGH) Cryptosystem.
Function to encrypt the message using the supplied public key.
pubkey: The public-key list
msg: The message to be encrypted (integer representation)
delta: The absolute value of the 0-symmetric strict bounds of the co-ordinates of the perturbation vector
Returns -> The encryption of msg under pubkey (integer representation)
Function to decrypt the ciphertext using the supplied keys.
pubkey: The public-key list
privkey: The private-key list
ciphertext: The ciphertext to be decrypted (integer representation)
Returns -> The decryption of the ciphertext under pubkey and privkey (integer representation)
Implementation of the Goldreich-Goldwasser-Halevi (GGH) Digital Signature Scheme.
Function to sign a document under the GGH Digital Signature Scheme.
pubkey: The public-key list
privkey: The private-key list
document: The document vector
Returns -> The signature vector of the document under pubkey and privkey
Function to verify signature on a document.
pubkey: The public-key list
document: The document vector whose signature is to be verified
signature: The signature vector
tolerance: The amount of tolerance accepted for the norm of the difference vector
Returns -> True if the signature verifies, False otherwise
Implementation of the NTRUEncrypt Public Key Cryptosystem.
Function to generate public-key private-key pair.
N: Check comments in source code
p: Check comments in source code
q: Check comments in source code
d: Check comments in source code
Returns -> (PubKey, Privkey)
Function to encrypt message using NTRUEncrypt.
N: Check comments in source code
p: Check comments in source code
q: Check comments in source code
d: Check comments in source code
pubkey: The public-key
msg: The message to be encrypted (represented as the centre-lift of a polynomial in Rp to R; check comments in source code)
Returns -> The ecnryption of the message under pubkey (represented as a polynomial in Rq; check comments in source code)
Function to decrypt the ciphertext using the supplied keys.
N: Check comments in source code
p: Check comments in source code
q: Check comments in source code
d: Check comments in source code
pubkey: The public-key
privkey: The private-key
ciphertext: The ciphertext to be decrypted (represented as a polynomial in Rq; check comments in source code)
Returns -> The decryption of the ciphertext under pubkey and privkey (represented as the centre-lift of a polynomial in Rp to R; check comments in source code)
Implementaion of the Gaussian Reduction Algorithm for Lattice Reductions in 2 Dimenions.
Function to return Gaussian Basis Reduction on the given two basis vectors.
v1: The first basis vector
v2: The second basis vector
Returns -> A 2-tuple of the Gaussian Reduced Basis vectors
Implementation of the Lenstra–Lenstra–Lovász Algorithm for Lattice Reductions.
Function to return the LLL reduced basis vectors from the given basis_vectors.
basis_vectors: The list of basis vectors upon which to perform LLL
Returns -> LLL reduced basis vectors derived from given basis_vectors