PQC and Keccak on Karu

Here at Manse Processors, we have been working on Post-Quantum Cryptography since 2015!

Well, I was actually in Belfast doing my final post-doc then, and thanks to Prof. Máire & Co I can now claim “10+ years of PQC experience”. Anyway, let me first explain why the RISC-V PQC Task Group is working on Keccak support.

PQC Standards vs Keccak

It turns out that cryptographic hash functions (the actual subject matter of my 2009 PhD) are incredibly important for PQC. From a practical viewpoint, the two main PQC algorithms are:

• FIPS 203 “Module-Lattice-Based Key-Encapsulation Mechanism Standard” (ML-KEM) is the recommended PQC key establishment method.
• FIPS 204 “Module-Lattice-Based Digital Signature Standard” (ML-DSA) is the recommended PQC authentication and integrity protection method.

Basic quantitative analysis of ML-KEM and ML-DSA reveals that often more than 50% of their execution time is actually spent computing the KECCAK-p[1600, 24] permutation, the core of the SHAKE extensible-output function (XOF). SHAKE is specified as a part of the SHA-3 standard FIPS 202.

Intuitively, you wouldn’t necessarily expect this — symmetric cryptography “support” functions consume a negligible percentage of cycles in traditional asymmetric RSA and Elliptic Curve cryptography. For the most part, ML-KEM and ML-DSA are not using SHAKE to hash (“absorb”) input data, but to expand (“squeeze”) random bits for various purposes.

Naturally, the hash-based signature algorithms SLH-DSA (FIPS 205) and LMS & XMSS (SP 800-208) consist almost exclusively of hash computation, so any Keccak speed-up is proportionally reflected on the performance of the SHAKE parameter sets of these algorithms.

Keccak is Hard to Vectorize

Nicolas Brunie (SiFive) wrote a blog post about RVV Implementation of Keccak / SHA-3 with a subtitle “Leveraging RISC-V Vector to slow down SHA-3 software implementation”. Why?

The Keccak permutation has a very efficient mixing transformation; the downside is that the particular access pattern of words makes efficient vectorization difficult. Since all 25 state words fit into the register file simultaneously, fast scalar execution is generally faster.

The linear mixing step Theta (θ) is just xors and the Rho (ρ) step is just rotations; that’s why the availability of scalar rori makes a lot of difference for scalar Keccak speed. The word permutation PI (π) is just scalar register re-indexing, while the only nonlinear step Chi (χ) is a logical and operation with other input inverted; the bitmanip instruction andn. The cost of a full 24-round permutation ends up being at 3000+ instructions; in practice, the compilers emit 4000+ instructions if rori and andn are available (bitmanip extension), and 6000+ if they are not (regular RV64GC).

One can, of course, parallelize VLEN/64 independent Keccak permutations with the vector unit. ML-KEM and ML-DSA can utilize such parallelism for some operations. The speedup is significantly reduced because vector instructions are generally not issued at the same rate as scalar instructions.

Keccak in Pure Hardware: Very, very fast

The structure is very fast in pure hardware, allowing 1 or 2 rounds per cycle even at very high operating frequencies. This is because the logical depth of each round is small; each round has only a handful of gates between input and output. Note that steps Rho (ρ) and PI (π) are just wiring; no gates.

While fast, the permutation is not very small; the cycle-per-round implementation in Karu is roughly 30 kGE, the size of a very small microcontroller core. However, for application processors, the exceptional, typically 100-fold, difference in hardware and software speed makes it sensible to do the entire permutation with a single instruction.

Hence, the draft Zvknhk Vector Keccak extension specifies a single instruction, Vector-Immediate Multi-Round Keccak, with the mnemonic vkeccak.vi.

While the permutation itself is easily 24 cycles, that is not the latency of the permutation due to the way vector register files are organized. A typical implementation will spend several times as much time getting data to and from the VRF as on the permutation itself. However, even if the permutation takes 100 cycles, it’s still orders of magnitude faster than executing thousands of instructions.

vkeccak: Zvknhk Specification and Tooling

The instruction is now defined by the published RISC-V PQC specification, with its source maintained in the official RISC-V PQC repository. That specification is normative. The repository’s Zvknhk support tree also keeps the non-normative implementations and tests together:

• Spike support provides the instruction semantics for the RISC-V ISA simulator.
• QEMU support implements the same semantics for TCG.
• OpenSSL support connects the instruction to SHA-3, SHAKE, and the Keccak-based PQC algorithms.
• The instruction test suite covers the 24-round and 12-round forms.

The implemented instruction performs Keccak in place in a fixed 2048-bit element group designated by vd. Its encoding can be written as:

vkeccak.vi v0, 0
.insn r 0x77, 0x2, 0x53, x0, x18, x0

The raw .insn form uses x-register names to encode the numeric instruction fields: the first x0 designates v0, while the final x0 encodes imm5=0. Use x1 in the final field for the 12-round form.

The immediate is now a selector rather than a literal round count. imm5=0 selects the 24-round Keccak-p[1600,24] permutation used by SHA-3 and SHAKE. imm5=1 selects Keccak-p[1600,12], using round constants RC[12..23], for functions such as KangarooTwelve and TurboSHAKE. All other immediate values are reserved.

The fixed group contains 32 64-bit elements and is independent of vl and LMUL. The 25-word Keccak state occupies elements 0 through 24; elements 25 through 31 are preserved. At Karu’s VLEN=256, the group spans eight registers, so vd can be v0, v8, v16, or v24:

 V0: [00 01 02 03]   V1: [04 05 06 07]   V2: [08 09 10 11]   V3: [12 13 14 15]
 V4: [16 17 18 19]   V5: [20 21 22 23]   V6: [24 -- -- --]   V7: [-- -- -- --]

 V8: [00 01 02 03]   V9: [04 05 06 07]  V10: [08 09 10 11]  V11: [12 13 14 15]
V12: [16 17 18 19]  V13: [20 21 22 23]  V14: [24 -- -- --]  V15: [-- -- -- --]

V16: [00 01 02 03]  V17: [04 05 06 07]  V18: [08 09 10 11]  V19: [12 13 14 15]
V20: [16 17 18 19]  V21: [20 21 22 23]  V22: [24 -- -- --]  V23: [-- -- -- --]

V24: [00 01 02 03]  V25: [04 05 06 07]  V26: [08 09 10 11]  V27: [12 13 14 15]
V28: [16 17 18 19]  V29: [20 21 22 23]  V30: [24 -- -- --]  V31: [-- -- -- --]

Resolved Details in the Current Draft

• VLEN=128 is supported by an instruction-specific 16-register fixed group. At larger VLENs, the group uses ceil(2048/VLEN) aligned registers.
• v0 is a valid destination when it satisfies the group-alignment rule. The instruction itself must be unmasked (vm=1).
• SEW values other than 64, immediate values other than 0 or 1, misaligned groups, and vm=0 are reserved encodings. The official Spike and QEMU models reject them as illegal instructions.
• A nonzero vstart explicitly raises an illegal-instruction exception.
• The operation is independent of vl, including vl=0, and leaves all bits outside the fixed group unchanged.

This is a breaking change from the experimental encoding used for the original June measurements. That version treated the immediate as a literal round count and used a different fixed encoding field. Current Karu64 and KaruDeb sources use the official Zvknhk form; binaries built for the earlier encoding must be rebuilt.

Benchmarking PQC Code

Our ML-KEM and ML-DSA implementations in KaruDeb have been derived from the original “ANSI C” Kyber and Dilithium code, with some modifications and options. They have now been ported to the official Zvknhk encoding; the cycle measurements below retain the original June comparison.

• There is a central macro flag for the Keccak permutation that is implemented alternatively with the Keccak instruction (VK_KECCAK == 1) or with a reasonably fast scalar code (VK_KECCAK == 0).

• The RISC-V Autovectorizer in recent versions of LLVM works really for some targets, but unfortunately it doesn’t know that our vector unit is relatively slow compared to the scalar ALU. The C code was compiled with the clang cross-compiler version 23.0.0git, which I built on June 1, 2026 (commit c07f4eef0945cf8e3b1d7480cbfcfa19f79d885f). There was no special target tuning; simply -O3 flag is used, and architecture flags specify which extensions are allowed.

• Certain parts have hand-written vector intrinsics optimizations controlled by flags MLDSA_RVV == 1 and MLKEM_RVV == 1. This is especially relevant for the shuffles in the Number Theoretic Transforms (vrgather shuffle instruction) and for rejection sampling in the A matrix generation (vcompress). The code is currently limited to our VLEN = 256 size, and may not be the final word in ML-KEM and ML-DSA optimization, but it still beats LLVM & GCC autovectorization in most cases.

• In these implementations, different parameter sets share the same execution paths, eliminating the need to re-instantiate multiple full versions of the algorithms for different security levels. This may make implementations slightly slower due to compiler optimizations (fewer opportunities to embed constants in instruction immediates, etc.), but it was originally done for code size and to simplify the build flow.

• The cycle counts are read with the standard RISC-V rdcycles instruction. Especially in a multi-user or multi-core Linux system, this register may be filtered/managed. The KaruDeb has a little utility for that: perf_run.c opens Linux perf events and then execs the actual benchmark binary (and its parameters) from the command line.

Results

Here we are giving some raw cycle numbers; you can see that Karu is not as fast as most other processors (its CPI — the average cycles/instruction number when running general benchmarks such as CoreMark — is pretty high). That wasn’t our goal with this single-issue in-order CPU that doesn’t even have proper caches; we wanted to achieve feature completeness while still fitting a full application vector processor in an FPGA. In absolute terms, these numbers tell nothing about “RISC-V” — if I built a processor like this with x86 or ARM ISA, it would have an equally bad CPI.

Hence, “speed” is computed as before-cycles / after-cycles on the same target, so 1.00x means the same speed, and values above 1.00x mean the second build is faster. Averages are arithmetic means over the nine top-level operations for each algorithm.

For validating the instruction semantics independently of Karu’s cycle counts, use the official Zvknhk test suite with the repository’s Spike support. The ML-KEM and ML-DSA figures below are Karu performance measurements rather than ISA conformance results.

For reproducing the instruction-count measurements, KaruDeb retains separate test-matrix scripts for ML-KEM and ML-DSA.

Impact of Scalar Bitmanip Alone (+15%)

(Simply enabling the Zbb flag in the compiler. This is almost entirely thanks to RORI and ANDN making Keccak faster.)

ML-KEM: RV64GC vs RV64GC+Zbb

ML-DSA: RV64GC vs RV64GC+Zbb

Impact of Keccak without Intrinsics (+40%)

(Autovectorization in use, no intrinsics. No modification to source code except addition of Keccak instruction.)

ML-KEM: RV64GCV+Zbb vs RV64GCV+Keccak

ML-DSA: RV64GCV+Zbb vs RV64GCV+Keccak

Impact of Intrinsics alone (+25%)

(No Keccak instruction. Impact of my optimizations with vector intrinsics over autovectorization.)

ML-KEM: RV64GCV+Zbb vs RV64GCV+Zbb+Intrin

ML-DSA: RV64GCV+Zbb vs RV64GCV+Zbb+Intrin

With Vector Intrinsics: Impact of Keccak (+52%)

(This is the headline number. With vector intrinsics the relative share of Keccak cycles increases, so the impact of the Keccak instruction is larger.)

ML-KEM: RV64GCV+Zbb+Intrin vs RV64GCV+Intrin+Keccak

ML-DSA: RV64GCV+Zbb+Intrin vs RV64GCV+Intrin+Keccak