Cryptography Reference
In-Depth Information
The fact that one can take a rank weight
r
close to
d
enables one to greatly
decrease the size of the parameters.
Parameters of the repaired Chen protocol with parameters
q
=2
,n
=
20
,m
=20
,k
=11
,r
=6
Public matrix H :
(
n
−
k
)
×
k
×
m
= 1980bits
×
m
= 180 bits
Secret key s :
n
×
m
= 400 bits
Average number of bits exchanged in one round:
2 hash + one word of
GF(
q
m
)
Public key i :
(
n
−
k
)
∼
800bits.
7.2 Possible Improvements
The protocol described in the previous section follows Stern's SD scheme, the only
difference being that the notion of permutation for Hamming distance, which gives
the indistinguishability is replaced by an equivalent notion for rank distance, the
product
P
∗
xQ
. Following this analogy other protocols like Veron's protocol ([15])
which improves on Stern's protocol can be adapted in this case.
It is also possible to improve the cheating probability to 1
/
2 as in the Cayrel et
al. protocol [3] by increasing the size of
q
. For the protocol we proposed we took
q
= 2, which gives a cheating probability of 2
/
3, increasing
q
to large
q
permits
to reach asymptotically a cheating probability of 1
/
2 but it may also increase the
cost of communication.
7.3 Comparison with Other Protocols
In terms of communication costs our protocol is 20% better than Stern's SD scheme
and faster, however the syndrome decoding problem remains less studied for the
rank distance and there is no underlying problem proven to be NP-hard (although
the problem is considered as hard by the community). The new protocol is less in-
teresting in terms of communication by a factor 20% compared to Shamir's PKP
protocol, however the security of PKP has been even less studied than the syn-
drome decoding problem for the rank distance. Another advantage of the new
protocol is that it benefits from a small public key compared to SD and PKP.
Overall these three protocols are all interesting for different reasons for low-cost
cryptography.
8Con lu on
In this paper we presented two polynomial attacks on the Chen identification pro-
tocol, the first attack takes advantage of the structure of the masking of the se-
cret and the second attack takes advantage of the fact that no hash function is
used in the protocol. Overall our attacks completely break the system when previ-
ous cryptanalysis remained of exponential complexity. We propose a new repaired
protocol but with a hash function: it comes with a rigorous zero-knowledge proof.
