#include <libsnark/common/data_structures/merkle_tree.hpp>#include <libsnark/gadgetlib1/gadgets/basic_gadgets.hpp>#include <libsnark/gadgetlib1/gadgets/hashes/hash_io.hpp>#include <libsnark/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc>
Go to the source code of this file.
Classes | |
| struct | libsnark::knapsack_dimension< FieldT > |
| class | libsnark::knapsack_CRH_with_field_out_gadget< FieldT > |
| class | libsnark::knapsack_CRH_with_bit_out_gadget< FieldT > |
Namespaces | |
| libsnark | |
Functions | |
| template<typename FieldT > | |
| void | libsnark::test_knapsack_CRH_with_bit_out_gadget () |
Detailed Description
Declaration of interfaces for the knapsack gadget.
The gadget checks the correct execution of a knapsack (modular subset-sum) over the field specified in the template parameter. With suitable choices of parameters such knapsacks are collision-resistant hashes (CRHs). See [Ajt96] and [GGH96].
Given two positive integers m (the input length) and d (the dimension), and a matrix M over the field F and of dimension dxm, the hash H_M maps {0,1}^m to F^d by sending x to M*x. Security of the function (very roughly) depends on d*log(|F|).
Below, we give two different gadgets:
- knapsack_CRH_with_field_out_gadget, which verifies H_M
- knapsack_CRH_with_bit_out_gadget, which verifies H_M when its output is "expanded" to bits. In both cases, a method ("sample_randomness") allows to sample M.
The parameter d (the dimension) is fixed at compile time in the struct knapsack_dimension below. The parameter m (the input length) can be chosen at run time (in either gadget).
References:
[Ajt96]: "Generating hard instances of lattice problems", Miklos Ajtai, STOC 1996
[GGH96]: "Collision-free hashing from lattice problems", Oded Goldreich, Shafi Goldwasser, Shai Halevi, ECCC TR95-042
- Copyright
- MIT license (see LICENSE file)
Definition in file knapsack_gadget.hpp.
