ntru-group-algebra 0.1.0

Research code for NTRU-style encryption over finite group algebra.

NTRU Group Algebra

Research code for an NTRU-style encryption experiment over finite group algebra. Classical NTRU uses

Z[x]/(x^N - 1) ~= Z[C_N].

This package replaces the cyclic group C_N with a finite group G and works in Z[G], with reductions modulo p and q. For noncommutative groups it fixes a left-sided convention:

h = f^{-1} g mod q
e = p h r + m mod q
f e = p g r + f m mod q

After center lifting, multiplying by f^{-1} modulo p recovers m when coefficients have not wrapped modulo q.

Status

This is research software, not production cryptography. The package is now pure Python and does not depend on SageMath. It includes direct finite-group arithmetic for cyclic, dihedral, and symmetric groups.

Optional FFT acceleration is used when compatible packages are installed:

• fft-dihedral>=0.2.0 accelerates dihedral multiplication and inversion over compatible prime fields.
• fft-symmetric>=0.2.0 accelerates symmetric-group multiplication and inversion over prime fields with characteristic p > n.

Composite NTRU-style moduli such as q = 2048 still use the pure-Python fallback path.

For dihedral groups, the fallback path also includes a faster inverse routine: when FFTs are unavailable over a small prime field such as F_3, inversion is reduced to a cyclic-polynomial inverse instead of a dense 2n x 2n linear solve.

Install

From a checkout:

python -m pip install -e .

With optional FFT backends:

python -m pip install -e ".[fft]"

Run Experiments

From a checkout:

python NTRU_group_algebra.py
python NTRU_group_algebra.py --profile larger --seed 20260506 --skip-cyclic-check
python NTRU_group_algebra.py --profile fft --seed 20260506 --skip-cyclic-check

After editable install:

ntru-group-algebra --profile larger --seed 20260506 --skip-cyclic-check
python -m ntru_group_algebra.cli --group symmetric --n 5 --p 7 --q 4099 --d 15 --trials 5

Test

PYTHONPATH=src python -m unittest discover -s tests

Near-Term Research Directions

• Separate parameter sets from experiment dictionaries.
• Extend acceleration to Z/2^k Z or add Hensel lifting for NTRU-like q.
• Decide whether a Rust crate should own fast arithmetic kernels while Python remains the research interface.