HQC updates

[Gaborit]

Dear all,


We have made some updates and improvements to the HQC scheme. The
main important points are the following:

 - We improved the DFR analysis of our protocol: as a consequence, we
managed to decrease the size of the public key by 3%

- We introduced an alternative and more efficient encoding and decoding
algorithm based on concatenating Reed-Muller and Reed-Solomon codes.
This new decoding variant does not change the protocol nor its security
and enables us to decrease the size of the public key (less 17% for 128
bits security). We provide a new set of parameters denoted by HQC-RMRS
for this decoding variation.

- Our implementations are now implemented in a constant-time way
whenever relevant and they should not   leak any sensitive information
with respect to timing attacks.

- Our implementations no longer rely on third party librairies for
finite field arithmetic

- We welcome Jean-Marc Robert (Univ. of Toulon, France) and Pascal Véron
(Univ. of Toulon, France) in our team


For 128 bits of security, we obtain the following sizes (in bytes), and
performances (in kilocycles) for HQC and HQC-RMRS :

                HQC       HQC-RMRS

Public Key    3,024          2,607

Ciphertext    6,017          5,191

Keygen          142            126

Encaps          231            213

Decaps          372            325



The new implementations, documentation and KATs are directly available at:

-Site: https://pqc-hqc.org

-Specs:https://pqc-hqc.org/doc/hqc-specification_2020-04-21.pdf

-Package :https://pqc-hqc.org/doc/hqc-submission_2020-04-21.zip


Best,

the HQC team

[D. J. Bernstein]

Gaborit writes:
> For 128 bits of security, we obtain the following sizes (in bytes), and
> performances (in kilocycles) for HQC and HQC-RMRS :
>                 HQC       HQC-RMRS
> Public Key    3,024          2,607
> Ciphertext    6,017          5,191
> Keygen          142            126
> Encaps          231            213
> Decaps          372            325

Given the nature of HQC and these numbers for constant-time software,
I'd guess that HQC uses fewer bit operations than most, perhaps all,
lattice submissions, and correspondingly less energy for computation in
an ASIC. It would be interesting to see bit-operation counts for HQC.

The general point here is that lattice submissions benefit from fast
multipliers in CPUs, but these multipliers inherently use many bit
operations. Most other CPU instructions are performing computations that
use far fewer bit operations, with the CPU costs dominated by overhead
that disappears in an ASIC. Variable-index array access is a notable
exception, and can be arbitrarily expensive (far more expensive than a
multiplier), but shouldn't appear in constant-time code.

---Dan

[D. J. Bernstein]

I've now looked a bit at the new HQC software (in the version submitted
to SUPERCOP), and I dispute the constant-time claims for this software.
For example, in crypto_kem/hqc128/avx,

* crypto_kem_dec(ss,ct,sk) calls hqc_pke_decrypt(m,u,v,sk),
* which finishes by calling code_decode(m,tmp2) to obtain the secret
message m,
* which finishes by calling bch_code_decode(m,tmp),
* which converts vector=tmp into syndromes_256 and then calls
compute_elp(sigma,(uint16_t *)syndromes_256),
* which feeds various syndromes to gf_mul,
* which uses exp and log tables for multiplication,

so the computation uses secret indices, violating the constant-time
rules (and perhaps leaking secret keys to cache-timing attacks).

As a double-check, running crypto_kem_dec(ss,ct,sk) under valgrind with
sk returned by an uninitialized malloc() complains about the same code
path (and about many other code paths that I haven't investigated). This
type of test can produce false positives (as in rejection sampling), but
I don't see anything protecting the code path described above.

---Dan

[Gaborit]

dear Dan,

Thank you for pointing this, you are right, we missed this part of the
code when moving to a constant time implementation of HQC.

We will make a thorough review of the code, solve this, and send a
modified version to SUPERCOP as soon as it is done.


best,

philippe for the HQC team

[Gaborit]

Dear all,

 Following Dan's remark on the constant time implementation of HQC,
 we went into more details on the function we missed, everything
 has been modified accordingly.

 For HQC the performance impact is very low for keygen, encaps and
 decaps for all parameter sets (at most 5%). For the HQC-RMRS, the
 impact is similarly low on keygen and encaps, and moderate for decaps
 (20% for 128 bits, and less for higher security levels).

 We thank again Dan for his remark.

 The new implementation is available on our site: https://pqc-hqc.org

- modified implementation:
http://pqc-hqc.org/doc/hqc-optimized-implementation_2020-05-29.zip

- specifications with new performances:
http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf

- whole package:
http://pqc-hqc.org/doc/hqc-submission_2020-05-29.zip

best,

philippe for the HQC team


Le 24/05/2020 à 04:56, D. J. Bernstein a écrit :