Cryptography Reference
In-Depth Information
The minimal value is reached, up to a constant factor, when = ( p ) such that
K 3
2 K 1 K 2 ε ( p, ( p ))
( p ) = log 2
.
Interestingly ( p ) is increasing with p and so is the complexity
( p, ( p )).
We thus want to choose p as small as possible. On the other hand, we have
|W 1 ||W 2 |
T
= k +
p
and
|W 2 |
must be a positive integer which limits the decrease
of p .Wemusthave
k +
p
k +
p
,
K 2
K 1 ε ( p, )
|W 1 |≤
with equality for the optimal p . Finally the optimal pair ( p, ) is the unique one
such that we have simultaneously
=log 2 K 3
2 K 2
min 2 r , w
k +
p
.
K 3
2 K 1 K 2
=log 2
r−
w−p
An Estimate of the Improvement. Let p is the optimal value obtained
above with an unlimited number of instances. In that case (we take K 0 =0,
K 1 = K 2 =1, K 3 =2)
k + 1
p
and =log 2 k +
.
1 =log 2
p
Keeping the first order variations we have
2 1 . From Proposition 3 we have
T
( p, 1 )
0 . 721 w − p
r − 1
T ( p, ) = 1
log
2 − c ( p )where c ( p )
N
≈T ( p, ) 2 −c ( p )
2 .Thus
where N ≈T ( p, )
T
( p, 1 )
Proposition 4. For a given p , we have
log
T ( p, ) = 2
T
( p, 1 )
3 + 4
1
2ln2
w − p
r − 1 w−p− 1
2
9 c ( p ) where c ( p )
.
log
Coming back to the single instance case, and assuming that
T
( p, 1 ) varies very
slowly with p , we may assume that WF ISD ( n,r,w )
( p, 1 ). This means that
when an attacker has access to an unlimited number of instances and needs to
decode one of them only, the decoding exponent is multiplied by a quantity,
slightly larger than 2 / 3, close to the one given in the above proposition.
≈T
w − p
r − 1 w−p− 1
2
2
3 +0 . 321
WF ( )
ISD ( n,r,w )=WF ISD ( n,r,w ) β where β ≈
(11)
where p and 1 are the optimal parameters of the algorithm when N =1.
 
Search WWH ::




Custom Search