{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9661aac1",
   "metadata": {},
   "source": [
    "Notebook created: 2025-03-07 11:06:19  \n",
    "Generated from: docs/algorithms/ntru.rst  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "474928e0",
   "metadata": {},
   "source": [
    "\n",
    "<a id='ntru-primal-attacks'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a17752c",
   "metadata": {},
   "source": [
    "# NTRU Primal Attacks\n",
    "\n",
    "We construct an (easy) example NTRU instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1e17007",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "from estimator import *\n",
    "params = NTRU.Parameters(n=200, q=7981, Xs=ND.UniformMod(3), Xe=ND.UniformMod(3))\n",
    "params"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bc046a8",
   "metadata": {},
   "source": [
    "The simplest (and quickest to estimate) model is solving via uSVP and assuming the Geometric Series Assumption (GSA) [[Schnorr03]](../references.ipynb#schnorr03). The success condition was formulated in [[USENIX:ADPS16]](../references.ipynb#usenix-adps16) and studied/verified in [[AC:AGVW17]](../references.ipynb#ac-agvw17), [[C:DDGR20]](../references.ipynb#c-ddgr20), [[PKC:PosVir21]](../references.ipynb#pkc-posvir21). The treatment of small secrets is from [[ACISP:BaiGal14]](../references.ipynb#acisp-baigal14). Here, the NTRU instance is treated as a homoegeneous LWE instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72edc335",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_usvp(params, red_shape_model=\"gsa\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1fd7c40",
   "metadata": {},
   "source": [
    "We get a similar result if we use the `GSA` simulator. We do not get the identical result because we optimize β and d separately:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63339310",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_usvp(params, red_shape_model=Simulator.GSA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54cfedf7",
   "metadata": {},
   "source": [
    "To get a more precise answer we may use the CN11 simulator by Chen and Nguyen [[AC:CheNgu11]](../references.ipynb#ac-chengu11) (as [implemented in FPyLLL](https://github.com/fplll/fpylll/blob/master/src/fpylll/tools/bkz_simulator.py)):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a092d7c6",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_usvp(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "178ea01a",
   "metadata": {},
   "source": [
    "We can then improve on this result by first preprocessing the basis with block size β followed by a single SVP call in dimension η [[RSA:LiuNgu13]](../references.ipynb#rsa-liungu13). We call this the BDD approach since this is essentially the same strategy as preprocessing a basis and then running a CVP solver:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0b49108",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_bdd(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2aa748e7",
   "metadata": {},
   "source": [
    "We can improve these results further by exploiting the sparse secret in the hybrid attack [[C:HowgraveGraham07]](../references.ipynb#c-howgravegraham07) guessing ζ positions of the secret:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "255d6d75",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_hybrid(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "767dac39",
   "metadata": {},
   "source": [
    "In addition to the primal secret key recovery attack, this module supports the dense sublattice attack as formulated in [[EC:KirFou17]](../references.ipynb#ec-kirfou17), and refined/verified in [[AC:DucWoe21]](../references.ipynb#ac-ducwoe21). The baseline dense sublattice attack uses a ‘z-shape’ variant of the Geometric Series Assumption, called the ZGSA:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2dd2f806",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "params.possibly_overstretched\n",
    "NTRU.primal_dsd(params, red_shape_model=Simulator.ZGSA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18f3ef33",
   "metadata": {},
   "source": [
    "Of course we can also use the CN11 simulator for this attack as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c482503c",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "NTRU.primal_dsd(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ea7268",
   "metadata": {},
   "source": [
    "**Note:** Currently, dense sublattice attack estimation is only supported if the distributions of `f` and `g` are equal. `NTRU.primal_dsd()` will return a `NotImplementedError` if this is not the case."
   ]
  }
 ],
 "metadata": {
  "date": 1741345579.0376966,
  "filename": "ntru.rst",
  "kernelspec": {
   "display_name": "SageMath",
   "language": "sage",
   "name": "sagemath"
  },
  "title": "NTRU Primal Attacks"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}