ntru-circom

This project has not been audited and should not be used in production.

NTRU (post-quantum asymmetric lattice) encryption in Javascript and Circom

Supports large keys and additive homomorphism

Installation

Important

Requires Node.js and Circom installed (if using circuits)

$ git clone https://github.com/numtel/ntru-circom.git
$ cd ntru-circom
$ npm install
$ npm test

# Run medium sized tests and output circom compilation details
$ GO_167=1 VERBOSE=1 npm test -- -f "decryption #2"
$ GO_167=1 VERBOSE=1 npm test -- -f "encryption #2"
$ GO_167=1 VERBOSE=1 npm test -- -f "together #2"

# Run large tests and output circom compilation details
$ GO_LARGE=1 VERBOSE=1 npm test -- -f "decryption #1"
$ GO_LARGE=1 VERBOSE=1 npm test -- -f "encryption #1"
$ GO_LARGE=1 VERBOSE=1 npm test -- -f "together #1"

Recommended parameters

Caution

Default settings are not high security!

Description	N	q	p
Default	167	128	3
128 bit security margin (NTRU-HPS)	509	2048	3
192 bit security margin (NTRU-HPS)	677	2048	3
256 bit security margin (NTRU-HPS)	821	4096	3
256 bit security margin (NTRU-HRSS)	701	8192	3

Source: Wikipedia

Tip

The Choosing Parameters for NTRUEncrypt paper suggests using ~N/3 for df, dg, dr parameters.

Javascript implementation

import NTRU from 'ntru-circom';

// Encrypt plaintext values up to N (default 167) bits long
const inputStr = 'Hello World';

const ntru = new NTRU;

// Generate a new private key
ntru.generatePrivateKeyF();
// Generate a new public key
ntru.generateNewPublicKeyGH();

// Encrypt the string
const encrypted = ntru.encryptStr(inputStr);

// Decryption returns original value
if(ntru.decryptStr(encrypted) !== inputStr) throw new Error;

constructor(options)

• options <Object>
  • N <Number> Coefficient count (Default: 167)
  • p <Number> Small prime field (Never changes, default: 3)
  • q <Number> Main field size (Power of 2, default: 128)
  • df <Number> Count of each non-zero (1,-1) coefficients in F (private key complexity)
  • dg <Number> Count of each non-zero (1,-1) coefficients in G (public key generation salt secret)
  • dr <Number> Count of each non-zero (1,-1) coefficients in randomness during encryption
  • h <Number[N]> Optional, specify a public key for encryptions

loadPrivateKey(fArr)

• fArr <Number[N]> Array of trinary coefficients (0, 1, -1) (Must be invertible mod q and p)

Load a specific private key. Sets f, fp, fq instance properties.

generatePrivateKeyF()

Generate a new private key. Sets f, fp, fq instance properties.

generatePublicKeyGH()

Generate a new public key. Sets g, h instance properties.

generatePublicKeyH()

Generate a new public key using a specific generation secret. Sets h instance property.

encryptStr(inputPlain)

• inputPlain <String> Text to be encrypted using public key h

Returns <Number[N] mod q> ciphertext array of values.

decryptStr(encrypted)

• encrypted <Number[N] mod q> Ciphertext array of values

Returns <String> plaintext

encryptBits(m)

• m <Number[N]> Plaintext array of trinary coefficients (0, 1, 2) up to N length

Returns object:

{
  value: <Number[N] mod q>,
  // Inputs for VerifyEncrypt circuit witness
  input: {
    r, // randomness
    m, // plaintext
    h, // public key
    quotientE, // verify final step
    remainderE, // encrypted ciphertext
  },
  // Parameters for VerifyEncrypt circuit compilation
  params: {q, nq, N},
}

decryptBits(e)

• e <Number[N]> Ciphertext array of coefficients

Returns object:

{
  value: <Number[N] mod p>,
  // Inputs for VerifyDecrypt circuit witness
  input: {
    f, // private key
    fp, // inverse of private key mod p
    e, // encrypted ciphertext
    quotient1, // verify intermediate step
    remainder1, // verify intermediate
    quotient2, // verify final step
    remainder2, // decrypted plaintext
  },
  // Parameters for VerifyDecrypt circuit compilation
  params: {q, nq, p, np, N},
}

verifyKeysInputs()

Generate the inputs and parameters for creating a VerifyInverse proof to prove coherency of a private key or that the public key matches the private key.

Three cases are keys in the return object:

Case	Usage
fp	Use this to verify fp is derived from f, confirming a decryption
fq	Use this as a first step if verifying h is derived from f in order to prove the user knows the private key for an encryption
h	Use this as a second step to verifying the public key

Tip

In addition to verifying private key coherency (case fp), it is recommended to pad the message with data that can be confirmed during decryption.

Library functions

import {
    // general polynomial operations
    degree, // compute degree of polynomial
    trimPolynomial, // trim leading zeros from polynomial
    modInverse, // compute multiplicative inverse mod p
    addPolynomials,
    subtractPolynomials,
    multiplyPolynomials,
    dividePolynomials,
    multiplyPolynomialsByScalar,

    // for inverting polynomials
    extendedEuclidianAlgorithm,
    polyInv,

    // create a random array of given length with set number of 1, -1 values
    generateCustomArray,

    expandArrayToMultiple,
    expandArray,

    // format helpers
    stringToBits,
    bitsToString,
    bigintToBits,
    bitsToBigInt,

    packOutput, // helper for invoking CombineArray template
    unpackInput, // helper for invoking UnpackArray template
} from 'ntru-circom';

Circom Templates

include "ntru-circom/circuits/ntru.circom";

VerifyEncrypt

Verifies that a ciphertext matches a given plaintext, publickey, and randomness.

VerifyDecrypt

Verifies that a plaintext matches a given ciphertext and privatekey.

VerifyInverse

Verify that the private key is coherent (f matches fp or fq) or that the public key is derived from a specific private key (h matches fq and g).

CombineArray/UnpackArray

For importing or exporting data with fewer signals

References

• NTRUEncrypt on Wikipedia
• pointedsphere/NTRU_python
• Choosing Parameters for NTRUEncrypt
• A Chosen-Ciphertext Attack against NTRU

License

MIT