Performance anomaly observed in hybrid KEM operations with oqs-provider

[ChanKamyung]

Environment Setup:

• OpenSSL 3.4.3
• liboqs 0.15.0
• oqs-provider 0.11.0-rc1
• CPU: Intel Core i7-1165G7 CPU
• Operating System: Ubuntu 24.04.3 LTS (Virtual Machine)

Test Results:

$ openssl speed mlkem768
Doing mlkem768 keygen ops for 10s: 722163 mlkem768 KEM keygen ops in 9.83s
Doing mlkem768 encaps ops for 10s: 805409 mlkem768 KEM encaps ops in 9.81s
Doing mlkem768 decaps ops for 10s: 653917 mlkem768 KEM decaps ops in 9.86s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
                   mlkem768 0.000014s 0.000012s 0.000015s   73465.2   82100.8   66320.2

$ openssl speed X25519
Doing X25519 keygen ops for 10s: 204817 X25519 KEM keygen ops in 9.84s
Doing X25519 encaps ops for 10s: 89317 X25519 KEM encaps ops in 9.87s
Doing X25519 decaps ops for 10s: 180618 X25519 KEM decaps ops in 9.85s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
                     X25519 0.000048s 0.000111s 0.000055s   20814.7    9049.3   18336.9

$ openssl speed X25519MLKEM768
Doing X25519MLKEM768 keygen ops for 10s: 149695 X25519MLKEM768 KEM keygen ops in 9.80s
Doing X25519MLKEM768 encaps ops for 10s: 87746 X25519MLKEM768 KEM encaps ops in 9.88s
Doing X25519MLKEM768 decaps ops for 10s: 85120 X25519MLKEM768 KEM decaps ops in 9.92s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
             X25519MLKEM768 0.000065s 0.000113s 0.000117s   15275.0    8881.2    8580.6

Performance Analysis:

1. Key Generation: X25519MLKEM768 keygen time (0.000065s) ≈ X25519 keygen (0.000048s) + mlkem768 keygen (0.000014s) = 0.000062s ✓

2. Encapsulation: X25519MLKEM768 encaps time (0.000113s) ≈ X25519 encaps (0.000111s) + mlkem768 encaps (0.000012s) = 0.000123s ✓

3. Decapsulation: X25519MLKEM768 decaps time (0.000117s) ≈ 1.67 × (X25519 decaps (0.000055s) + mlkem768 decaps (0.000015s)) = 1.67 × 0.000070s = 0.0001169s ✗

Expected vs Actual Decapsulation Performance:

• Expected: ~0.000070s (sum of individual operations)
• Actual: 0.000117s (~1.67× slower than expected)

Contrasting Results with OpenSSL 3.6.0:
When testing the same algorithms using OpenSSL 3.6.0 (which includes native post-quantum algorithm support), the hybrid KEM performance aligns with expectations - all three operations show execution times approximately equal to the sum of their individual components.

$ openssl speed -seconds 3 ML-KEM-768
Doing ML-KEM-768 keygen ops for 3s: 48683 ML-KEM-768 KEM keygen ops in 2.85s
Doing ML-KEM-768 encaps ops for 3s: 85463 ML-KEM-768 KEM encaps ops in 2.95s
Doing ML-KEM-768 decaps ops for 3s: 52684 ML-KEM-768 KEM decaps ops in 2.96s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
                   ML-KEM-768 0.000059s 0.000035s 0.000056s   17081.8   28970.5   17798.6

$ openssl speed -seconds 3 X25519
Doing X25519 keygen ops for 3s: 60690 X25519 KEM keygen ops in 2.94s
Doing X25519 encaps ops for 3s: 26533 X25519 KEM encaps ops in 2.96s
Doing X25519 decaps ops for 3s: 53032 X25519 KEM decaps ops in 2.98s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
                     X25519 0.000048s 0.000112s 0.000056s   20642.9    8963.9   17796.0

$ openssl speed -seconds 3 X25519MLKEM768
Doing X25519MLKEM768 keygen ops for 3s: 26448 X25519MLKEM768 KEM keygen ops in 2.92s
Doing X25519MLKEM768 encaps ops for 3s: 21533 X25519MLKEM768 KEM encaps ops in 2.94s
Doing X25519MLKEM768 decaps ops for 3s: 26301 X25519MLKEM768 KEM decaps ops in 2.86s
                               keygen    encaps    decaps keygens/s  encaps/s  decaps/s
             X25519MLKEM768 0.000110s 0.000137s 0.000109s   9057.5    7324.1    9196.2

Question:
The observed discrepancy in decapsulation performance with oqs-provider seems counterintuitive. While some overhead for hybrid operations is expected, the decapsulation time being nearly double the sum of individual operations warrants investigation.

Could this be related to:

1. Implementation inefficiencies in the hybrid decapsulation code path?
2. Additional context setup or key parsing overhead specific to oqs-provider?
3. Known optimizations or configuration options that might improve performance?

Any insights or guidance would be greatly appreciated.

[baentsch]

Thanks for the report and analysis, @ChanKamyung . This indeed seems to point towards some inefficiency in the hybrid decaps path. If you'd be willing to help find a place where to look, can you reproduce this for P-hybrids, not just X25519? What happens in the case of other PQ algs, particularly for sig algs? What in the case of older OpenSSL versions?

[ChanKamyung]

Thank you for your reply!

Following your suggestion, I conducted a more comprehensive test, and the results are indeed more concerning. The performance anomalies are not limited to X25519MLKEM768; they manifest differently but are widespread across various classical/PQ hybrid combinations.

🔍 Key Findings Summary:

1. P-Curve Hybrids (e.g., SecP256r1MLKEM768, p384_bikel3): Exhibit a severely abnormal key generation time, often 10-100x slower than a reasonable sum of the component algorithms. Decapsulation also shows significant overhead.
2. X-Curve Hybrids (e.g., X25519MLKEM768, x448_bikel3): Key generation time is roughly additive (as expected), but decapsulation time remains about 1.6-2x the sum of the components, confirming the initial observation.
3. Hybrid Signatures (e.g., p256_falcon512): Also show abnormally high key generation time for the composite algorithm.
4. Cross-Version Consistency: The same issues were reproduced with OpenSSL 3.3.5, indicating it's not a regression in 3.4.3.

📊 Detailed Test Results & Analysis

1. P-Curve Hybrid KEM: Severely Abnormal Key Generation

The data for SecP256r1MLKEM768 is particularly striking. Its key generation is ~340x slower than the sum of its parts.

# Component: ECP-256 (P-256)
                    ECP-256 0.000017s 0.000117s 0.000092s   59529.6    8559.7   10847.3
# Component: mlkem768
                   mlkem768 0.000015s 0.000013s 0.000016s   65427.1   79064.6   64461.9
# Expected ~sum:           ~0.000032s               ~0.000108s
# Hybrid Result:
          SecP256r1MLKEM768 0.005709s 0.000135s 0.000183s     175.2    7392.9    5460.7
# Keygen is 0.005709s vs expected ~0.000032s -> **~178x slower**.

The same pattern holds for p384_bikel3:

# Component: ECP-384
                    ECP-384 0.000211s 0.000843s 0.000572s    4735.1    1186.8    1747.3
# Component: bikel3
                     bikel3 0.000797s 0.000098s 0.001740s    1254.1   10168.8     574.7
# Expected ~sum:           ~0.001008s               ~0.002312s
# Hybrid Result:
                p384_bikel3 0.006956s 0.000895s 0.002373s     143.8    1116.9     421.4
# Keygen is 0.006956s vs expected ~0.001008s -> **~7x slower**.

2. X-Curve Hybrid KEM: "Normal" Keygen, But Slow Decaps

For X25519MLKEM768, keygen time is additive (~0.000072s ≈ 0.000048s + 0.000015s), but decapsulation remains problematic.

                     X25519 0.000048s 0.000113s 0.000054s   20699.7    8876.0   18640.4
                   mlkem768 0.000015s 0.000013s 0.000016s   65427.1   81105.1   62552.7
# Expected Decaps sum:      ~0.000070s (0.000054 + 0.000016)
             X25519MLKEM768 0.000072s 0.000123s 0.000120s   13859.4    8137.4    8361.7
# Decaps is 0.000120s vs expected ~0.000070s -> **~1.7x slower**.

The pattern is similar for x448_bikel3 (keygen is additive, decaps is slower).

3. Hybrid Signatures: Also Affected

While I'm not sure of the exact command to test a standalone p256 signature, the hybrid p256_falcon512 shows an improbably high key generation time, suggesting a similar underlying issue.

                  falcon512 0.010459s 0.000343s 0.000059s      95.6    2916.8   16877.4
# Hybrid Result:
             p256_falcon512 0.016836s 0.000373s 0.000159s      59.4    2684.6    6291.6
# The keygen time for the hybrid (0.0168s) is much larger than falcon512 alone (0.0105s).
# A classical ECDSA-P256 keygen typically takes < 1ms, so the composite keygen seems abnormally slow.

4. Results are Consistent in OpenSSL 3.3.5

All the issues described above were reproduced with OpenSSL 3.3.5 (full terminal outputs are in the original post). This rules out a recent regression.

✅ Answers to Your Specific Questions

• "Can you reproduce this for P-hybrids, not just X25519?" → Yes, and it's worse. P-hybrids show a critical performance degradation in key generation, which is even more severe than the decapsulation overhead in X-hybrids.
• "What happens in the case of other PQ algs, particularly for sig algs?" → The issue is general. I tested with BIKE-L3 (KEM) and Falcon-512 (signature). Both show the same pattern when combined with a classical algorithm (P-curve or X-curve), affecting key generation and/or decapsulation/verification.
• "What in the case of older OpenSSL versions?" → The issues persist in OpenSSL 3.3.5.

🎯 Suggested Next Steps

The data strongly suggests that the current implementation of composite/hybrid algorithms in oqs-provider has non-additive overheads, which are algorithm-dependent:

1. P-Curve + PQ Composites: Suffer from a major inefficiency in key generation.
2. X-Curve + PQ Composites: Suffer from a significant decapsulation overhead.

The logical places to investigate would be the composite key generation and decapsulation code paths, particularly focusing on how the key contexts for the two components are initialized, managed, and serialized/deserialized.

I hope this detailed analysis is helpful. I am willing to assist further, such as running more targeted tests or reviewing specific code sections.