Reduced-round Keccak for PQ schemes

423 views
Skip to first unread message

Gilles Van Assche

unread,
Jul 8, 2022, 12:30:58 PM7/8/22
to pqc-...@list.nist.gov
Dear all,

First of all, we would like to congratulate the different teams whose
algorithms are selected for standardization or for the 4th round!

Owing to the discussion initiated by John Mattsson in the thread "90s"
version parameter sets, there is a need to optimize and simplify the use
of symmetric primitives in the post-quantum schemes. We have understood
that the calls to SHA-3/SHAKE/Keccak, e.g., to generate pseudo-random
values, but also for other purposes, take a significant part of the
total execution time in some of these schemes.

As its designer, we believe that Keccak is a future-proof and efficient
primitive, among others when protections against side-channel attacks
are required, but we also believe that its full 24 rounds are overkill.
There has been sustained cryptanalysis on Keccak over the years and an
amazing number of publications on this subject by the crypto community
since its submission, and this gives a rather clear view of its safety
margin [1]. Therefore, we would suggest to consider replacing
Keccak-f[1600] with Keccak-p[1600, 12 rounds] in the definition of the
standardized post-quantum schemes. Note that the Keccak-p[1600, 12
rounds] permutation is well defined in FIPS 202.

We think this would not change the safety margin of the post-quantum
schemes in a significant way, yet give them a great speed-up and
therefore yield a better performance-security trade-off for everyone.

Kind regards,
Gilles, Guido, Joan and Michaël

[1] https://keccak.team/third_party.html (note: some recent papers still
have to be added)

John Mattsson

unread,
Jul 10, 2022, 1:51:31 AM7/10/22
to Gilles Van Assche, pqc-...@list.nist.gov

Hi,

 

I think that is an interesting suggestion. My understanding is that Keccak-p[1600, 12] is twice as fast as Keccak-f[1600]. For the XOF maybe even Keccak-p[1600, 12] is overkill:

 

"The choice of SHAKE-128 as instantiation of the XOF is actually important for performance; also we do not need any of the traditional security properties of hash functions from SHAKE-128, but rather that the output “looks uniformly random."”

 

XOF, H, G, PRF, KDF could potentially use different amount of rounds. Could also consider using parallel hashing if any of the field are big enouhg to justify that.

 

I think ARM and RISC-V should be applauded for adding Keccak accelaration. My understanding is that the Keccak acceleration in these instuction set are quite general and would be equally good at accelerating Keccak-p[1600, 12 rounds].

 

I think the most relevant benchmark for PQC should be such a modern platform with ability to accelerate any Keccak variant. The PQC algorithms will likely be with us for many decades. I don't think it is a good idea to optimize for what is on the market today.

 

Cheers,

John

Reply all
Reply to author
Forward
0 new messages