{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e0ce14af",
   "metadata": {},
   "source": [
    "Notebook created: 2026-02-23 15:58:25  \n",
    "Generated from: docs/algorithms/lwe-primal.rst  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9923c6ab",
   "metadata": {},
   "source": [
    "\n",
    "<a id='lwe-primal-attacks'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36f5c5df",
   "metadata": {},
   "source": [
    "# LWE Primal Attacks\n",
    "\n",
    "We construct an (easy) example LWE instance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6abce61b",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "from estimator import *\n",
    "params = LWE.Parameters(n=200, q=7981, Xs=ND.SparseTernary(16), Xe=ND.CenteredBinomial(4))\n",
    "params"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efd03961",
   "metadata": {},
   "source": [
    "The simplest (and quickest to estimate) model is solving via uSVP and assuming the Geometric Series\n",
    "Assumption (GSA) [[Schnorr03]](../references.ipynb#schnorr03). The success condition was formulated in [[USENIX:ADPS16]](../references.ipynb#usenix-adps16) and\n",
    "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\n",
    "from [[ACISP:BaiGal14]](../references.ipynb#acisp-baigal14):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b66395f6",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "LWE.primal_usvp(params, red_shape_model=\"gsa\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19250298",
   "metadata": {},
   "source": [
    "We get a similar result if we use the `GSA` simulator. We do not get the identical result because\n",
    "we optimize β and d separately:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09464a77",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "LWE.primal_usvp(params, red_shape_model=Simulator.GSA)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6428c727",
   "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": "d8461f3e",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "LWE.primal_usvp(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "002e06b0",
   "metadata": {},
   "source": [
    "We can then improve on this result by first preprocessing the basis with block size β followed by a\n",
    "single SVP call in dimension η [[RSA:LiuNgu13]](../references.ipynb#rsa-liungu13). We call this the BDD approach since this is\n",
    "essentially the same strategy as preprocessing a basis and then running a CVP solver:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e2caf24f",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "LWE.primal_bdd(params, red_shape_model=Simulator.CN11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "519b17a9",
   "metadata": {},
   "source": [
    "We can improve these results further by exploiting the sparse secret in the hybrid attack\n",
    "[[C:HowgraveGraham07]](../references.ipynb#c-howgravegraham07) guessing ζ positions of the secret:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d613405",
   "metadata": {
    "hide-output": false
   },
   "outputs": [],
   "source": [
    "LWE.primal_hybrid(params, red_shape_model=Simulator.CN11)"
   ]
  }
 ],
 "metadata": {
  "date": 1771862305.2351098,
  "filename": "lwe-primal.rst",
  "kernelspec": {
   "display_name": "SageMath",
   "language": "sage",
   "name": "sagemath"
  },
  "title": "LWE Primal Attacks"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}