1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
|
#ifndef BKZ_PARAM_H
#define BKZ_PARAM_H
/* (C) 2014-2016 Martin Albrecht.
This file is part of fplll. fplll is free software: you can
redistribute it and/or modify it under the terms of the GNU Lesser
General Public License as published by the Free Software
Foundation, either version 2.1 of the License, or (at your option)
any later version.
fplll is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with fplll. If not, see
<http://www.gnu.org/licenses/>.
*/
#include "defs.h"
#include "pruner.h"
#include <string>
#include <vector>
FPLLL_BEGIN_NAMESPACE
/**
A strategy covers pruning parameters and preprocessing block_sizes
*/
class Strategy
{
public:
size_t block_size; //< block size
vector<PruningParams> pruning_parameters; //< Pruning parameters
vector<size_t> preprocessing_block_sizes; //< For each block size we run one tour
/** Construct an empty strategy
@note Use this instead of the default constructor. The default
constructor does not add default pruning parameters.
*/
static Strategy EmptyStrategy(size_t block_size)
{
Strategy strat;
strat.block_size = block_size;
strat.pruning_parameters.emplace_back(PruningParams());
return strat;
};
/** Select the best pruning parameters for the input `radius`. The
parameter `gh` is used to establish the ratio between `radius`
and the Gaussian heuristic, which is used for sizes.
@param radius radius of the currently shortest vector
@param gh Gaussian heuristic prediction for radius
*/
const PruningParams &get_pruning(double radius, double gh) const;
};
class BKZParam
{
public:
/**
@brief Create BKZ parameters
@param block_size
block size for the reduction
@param strategies
vector of strategies used for pruning and preprocessing
@param delta
LLL parameter delta
@param flags
various flags that can be arbitrarily combined (using |):
- BKZ_VERBOSE print additional information during reduction
- BKZ_NO_LLL do not run LLL before block reduction (use at your own risk)
- BKZ_MAX_LOOPS terminate after max_loops iterations
- BKZ_MAX_TIME terminate after max_time time
- BKZ_BOUNDED_LLL only run LLL in current block during SVP preprocessing (use at your
own
risk)
- BKZ_AUTO_ABORT heuristically terminate the reduction if progress stalls
- BKZ_DUMP_GSO after every iteration write the shape of the current basis to a file
- BKZ_GH_BND use the Gaussian heuristic to reduce the enumeration bound of possible
- BKZ_SD_VARIANT run SD-BKZ
- BKZ_SLD_RED run slide reduction
@param max_loops
maximum number of loops (or zero to disable this)
@param max_time
maximum number of time (or zero to disable this)
@param auto_abort_scale
auto abort when next tour does not improve slope over `scale`* previous tour
@param auto_abort_max_no_dec
auto abort when next tour does not improve slope `no_dec` times
@param gh_factor
set enumeration bound to Gaussian heuristic times `gh_factor`
@param min_success_probability
minimum success probability in an SVP reduction (when using pruning)
@param rerandomization_density
the heavier rerandomization, the better our guarantees and costs
*/
BKZParam(int block_size, vector<Strategy> &strategies, double delta = LLL_DEF_DELTA,
int flags = BKZ_DEFAULT, int max_loops = 0, double max_time = 0,
double auto_abort_scale = BKZ_DEF_AUTO_ABORT_SCALE,
int auto_abort_max_no_dec = BKZ_DEF_AUTO_ABORT_MAX_NO_DEC,
double gh_factor = BKZ_DEF_AUTO_ABORT_MAX_NO_DEC,
double min_success_probability = BKZ_DEF_MIN_SUCCESS_PROBABILITY,
int rerandomization_density = BKZ_DEF_RERANDOMIZATION_DENSITY)
: block_size(block_size), strategies(strategies), delta(delta), flags(flags),
max_loops(max_loops), max_time(max_time), auto_abort_scale(auto_abort_scale),
auto_abort_max_no_dec(auto_abort_max_no_dec), gh_factor(gh_factor),
dump_gso_filename("gso.json"), min_success_probability(min_success_probability),
rerandomization_density(rerandomization_density)
{
// we create dummy strategies
if (strategies.empty())
{
strategies = vector<Strategy>();
for (long b = 0; b <= block_size; ++b)
{
strategies.emplace_back(Strategy::EmptyStrategy(b));
}
}
};
/** Block size used for enumeration **/
int block_size;
/** Strategies (pruning coefficients, preprocessing) */
vector<Strategy> &strategies;
/** LLL parameter delta **/
double delta;
/** See BKZFlags **/
int flags;
/** Maximum number of loops to execute **/
int max_loops;
/** Maximum time to spend **/
double max_time;
/** If BKZ_AUTOABORT is set, We abort if `new_slope < auto_abort_scale * old_slope`
is true for `auto_abort_max_no_dec` loops.
*/
double auto_abort_scale;
int auto_abort_max_no_dec;
/** If BKZ_GH_BND is set, the enumeration bound will be set to gh_factor times
the Gaussian Heuristic
*/
double gh_factor;
/** If BKZ_DUMP_GSO is set, the norms of the GSO matrix are written to this
file after each complete round.
*/
string dump_gso_filename;
/** minimum success probability when using extreme pruning */
double min_success_probability;
/** density of rerandomization operation when using extreme pruning **/
int rerandomization_density;
};
/**
Load BKZ pruning and preprocessing strategies from a json file.
@note All parameters except pruning and preprocessing are silently ignored.
*/
vector<Strategy> load_strategies_json(const std::string &filename);
/**
Return default directory to search for strategies (if any)
*/
const std::string &default_strategy_path();
/**
Return default strategy (if any)
*/
const std::string &default_strategy();
/**
Attempt to expand strategy path to full path
*/
const std::string strategy_full_path(const string &strategy_path);
FPLLL_END_NAMESPACE
#endif /* BKZ_PARAM_H */
|
