Skip to content

Latest commit

 

History

History
60 lines (47 loc) · 4.16 KB

README.md

File metadata and controls

60 lines (47 loc) · 4.16 KB
Raw

HAWK signature scheme

This repository contains:

  • a reference to a C implementation of HAWK,
  • multiple sage files used in the cryptanalysis and used for generating all the tables in the C implementation,
  • data files that were used to generate all the figures in the paper.

[DPPvW21] HAWK: Module LIP makes Lattice Signatures Fast, Compact and Simple by Léo Ducas, Eamonn W. Postlethwaite, Ludo Pulles, Wessel van Woerden

Contributers

  • Léo Ducas,
  • Eamonn W. Postlethwaite,
  • Ludo Pulles,
  • Wessel van Woerden.

Requirements

  • C/C++ compiler, preferably gcc,
  • SageMath.

Description of files

Short description of the files.

In C-implementation:

  • branch main (pointed to) contains solely HAWK and a benchmark file located in tests/speed.c.
  • branch develop contains all the test files that were run to acquire standard deviations of coefficients of either public or signature. These are mostly located in avx2-optimized/tests. Here you will also find config_fg.c and config_FG.c which were used to determine the number of bits needed to represent all the coefficients in every layer of tower solve.
  • branch NTT-18433 contains an implementation of signing which uses the smaller prime q = 18433 for signing with the NTT (avx2-optimized stays the same). The advantage of using this smaller prime instead of 65537 is that the memory usage is almost halved for signing.
  • branch rANS was an experimental branch for using asymmetric numeral systems as an encoding instead of Golomb--Rice.

In code:

  • BKZ_simulator.sage contains the code used to simualate BKZ reduction, adapted from the leaky-LWE-estimator
  • _attack_Zn.sage contains the functions that generate and apply lattice reduction to forms, _attack_Zn.py is created via sage --preparse _attack_Zn.sage and renaming. This preparsing must take place if _attack_Zn.sage is altered
  • attack_Zn.sage contains the high level functions for running experiments in parallel
  • bkz_strat.json contains the strategies used by fpylll for BKZ reduction
  • convert_sigma_to_stddev.py converts a Gaussian parameter sigma to standard deviation, as these vary below smoothing
  • coprimality.sage contains the functions that estimate whether a sampled f, g can be completed using TowerSolve
  • exp_varying_n.sage runs experiments where the dimension n varies
  • exp_varying_sigma.sage runs experiments where the Gaussian parameter sigma varies
  • find_params.sage contains the functions used to find the three parameter sets in the paper, and to compare security in FALCON's security methodology
  • generate_C_tables.sage contains the functions that determine tables for sampling from discrete Gaussians with sufficiently small Rényi divergence
  • hawk.sage contains a slow but simple implementation of hawk for didactic purposes
  • load_strategies.sage loads the BKZ strategies
  • pred_varying_n.sage runs the BKZ_simualtor on instances in dimension n
  • proba_utils.py contains functions that generate and examine discrete distributions used in find_params.sage

In data:

  • XXX_varying_sigma_80trials.txt contain the average block sizes required to solve XXX dimensional instances with the given Gaussian parameters sigma
  • XXX_varying_stddev_80trials.txt as above but with sigma converted to standard deviation via conver_sigma_to_stddev.sage
  • estimates_tower_solve.txt estimates the number of completable samples and the proportion of these that are completed by TowerSolve for various powers of 2 using coprimality.sage
  • estimates_tower_solve_hawk.txt as above but further stipulating HAWK KGen conditions
  • experimental_tower_solve_1.5.txt data on how many sampled (f, g) with sigma = 1.5 are completable, and how many of these are completable by TowerSolve (to compare to estimates_tower_solve.txt)
  • experimental_tower_solve_1.5_hawk.txt as above but further stipulating HAWK KGen conditions
  • pred_varying_n.txt data from pred_varying_n.sage
  • varying_n_40trials.txt experimental data on the block size required to solve instances for varying dimensions
  • varying_structured_n_40trials.txt as above but with structured lattices for dimensions we can experiment on