PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient and Implementation-Hardened RBLWE on Commodity Cortex-M Microcontrollers

Muhammad Asim Javaid, Muhammad Adeel Pasha, Muhammad Ali Siddiqi

arXiv:2610.07820v1cs.CRcs.AR

TL;DR

Resource-constrained IoT devices need post-quantum implementations that meet practical budgets while resisting implementation attacks, but prior work separates architecture-aware acceleration from implementation-security scrutiny. This paper accelerates and hardens RBLWE on a commodity Cortex-M33. It reports same-core speedups for key generation, encryption, and decryption, alongside staged protection evaluation that also identifies a residual fault gap.

  • Problem

    Prior work separates architecture-aware acceleration from implementation-security scrutiny for RBLWE, despite the latency, memory, energy, and physical-attack constraints of embedded IoT deployments.

    Source: §I · p. 1

  • Method

    The paper combines Cortex-M33 SIMD-style polynomial arithmetic, packed message processing, and buffered TRNG access with staged constant-time, fault, CCA2-oriented, and shared-decryption protections.

    Source: §I · p. 1

  • Results

    4.06×, 3.35×, and 3.01× same-core speedups are reported for key generation, encryption, and decryption, respectively, with binary inspection, timing tests, TVLA, and 2,678 fault trials evaluating protections.

    Source: A. Per-Mechanism Acceleration Gains · p. 7, §VII · p. 10

  • Takeaways & Limitations

    The results demonstrate a measurable transition from an accelerated CPA core to a hardened MCU implementation, with speed and protection costs reported across stages.

    Source: §VII · p. 10

    The fault conclusions are limited to the tested single-point logical model, and skipping the final store or loop control can silently corrupt valid output.

    Source: F. Resistance to Fault-Injection Attacks · p. 9

Abstract

from arXiv · show

Efficient post-quantum cryptography on resource-constrained Internet-of-Things (IoT) devices requires implementations that exploit the target processor architecture while resisting practical implementation attacks. This paper presents an ISA-accelerated and implementation-hardened realization of Ring Binary Learning with Errors (RBLWE) encryption on a commodity ARM Cortex-M33 microcontroller. Packing four 8-bit polynomial coefficients into the byte lanes of a 32-bit register and processing them with SIMD-style instructions, together with a packed message codec, accelerates encryption and decryption, while a buffered hardware-TRNG entropy source drawn from the on-die Secure Element drives the key-generation gain. Together these give same-core cold-start speedups of $4.06\times$, $3.35\times$, and $3.01\times$ for key generation, encryption, and decryption over a scalar baseline, and $3.52\times$/$3.18\times$ lower encryption/decryption cycle counts than a reference Cortex-M0 implementation. On top of this accelerated core, we add four staged countermeasures: constant-time execution, fault hardening against zeroing, random-corruption, and instruction-skip faults, a Fujisaki-Okamoto (FO)-style CCA2 transform, and first-order shared (masked) CPA decryption, reporting each layer's cost individually. Binary-level inspection confirms these countermeasures survive compilation and identifies a compiler-induced masking flaw resolved with a hand-written assembly replacement. Dudect-style timing tests, debugger-assisted fault-injection campaigns, and component-level TVLA then provide implementation-level evidence for the staged protections. The results demonstrate a practical acceleration-security tradeoff for RBLWE on off-the-shelf microcontrollers and reusable architecture-aware techniques for lightweight post-quantum implementations.

I. INTRODUCTION

The paper addresses the gap between architecture-aware RBLWE acceleration and implementation-security evaluation on resource-constrained devices. It combines Cortex-M33 acceleration with staged protections and evaluates their implementation-level behavior.

I. INTRODUCTION

  • RBLWE suits constrained IoT nodes because binary secrets and errors reduce sampling and arithmetic complexity relative to general Ring-LWE.The paper notes that exposed embedded deployments also require low latency, memory, and energy use while resisting physical attacks.Source: §I · p. 1
  • Prior hardware work accelerates arithmetic without side-channel or fault evaluation, while prior lightweight software lacks 32-bit SIMD and on-die security-peripheral acceleration.The paper identifies missing power-leakage assessment and binary-level verification in those software works.Source: §I · p. 1

C1. ISA- and Hardware-Assisted RBLWE Acceleration:

  • The proposed Cortex-M33 implementation packs four polynomial coefficients per 32-bit word, uses byte-lane SIMD and packed message processing, and batches Secure Element TRNG output.The paper attributes most encryption and decryption speedup to SIMD arithmetic and most key-generation gain to fewer TRNG invocations.Source: §I · p. 1, C1. ISA- and Hardware-Assisted RBLWE… · pp. 1–2
  • The accelerated CPA-secure core is extended in stages with constant-time execution, fault hardening, an FO-style CCA2 transform, and first-order shared CPA decryption.The cycle and memory cost of each protection layer is reported separately.Source: §I · p. 1, C1. ISA- and Hardware-Assisted RBLWE… · p. 2
  • Byte-lane SIMD arithmetic, packed encoding/decoding, and a buffered Secure-Engine TRNG together yield same-core speedups of 4.06×, 3.35×, and 3.01×.ELF inspection found GCC recombined masked shares inside a noinline gadget, resolved with a hand-written assembly replacement. Dudect-style timing tests, component-level TVLA, and 2,678 debugger-assisted fault trials evaluated the staged protections.Source: C1. ISA- and Hardware-Assisted RBLWE… · pp. 1–2

A. Ring-LWE Computational Model

The paper formulates RBLWE over a polynomial quotient ring and describes its binary key and encryption sampling. Its adopted scheme includes coefficient-dependent decoding to address noise bias.

A. Ring-LWE Computational Model

  • Ring-LWE operates over a polynomial quotient ring, where coefficients are reduced modulo q and multiplication is negacyclic because x^n = -1.RBLWE restricts secret and error polynomial coefficients to binary values.Source: A. Ring-LWE Computational Model · p. 2

B. RBLWE Dataflow and Bias-Aware Decoding

  • The adopted Buchmann et al. RBLWE scheme uses coefficient-dependent decoding because binary sampling introduces coefficient-dependent noise bias.Binary sampling reduces sampler and arithmetic complexity relative to wider error distributions.Source: B. RBLWE Dataflow and Bias-Aware… · p. 2

1) Key generation:

  • Key generation selects public a from Rq and independently samples two binary polynomials with Bernoulli(1/2) coefficients.The resulting public key is (a, p), and the secret key is r2.Source: 1) Key generation · p. 2

2) Encryption:

  • Encryption independently samples three fresh binary polynomials for a binary message, then outputs ciphertext c = (c1, c2).The message bits map to the encoded polynomial's coefficients.Source: 2) Encryption · p. 2

3) Decryption and residual noise:

Decryption produces the encoded message plus residual noise. Because the expected noise depends on coefficient index, the decoder applies an index-dependent offset before its MSB decision.

3) Decryption and residual noise:

4) Bias-aware decoding:

  • Binary variables have positive skew, and negacyclic multiplication makes the expected residual noise coefficient-dependent.The number of positive and negative wrapped terms depends on coefficient index i.Source: 4) Bias-aware decoding · p. 3
  • The decoder computes zi = (wi − Li) mod q and recovers m-hat_i = 1 ⊕ MSBlog2 q(zi); subtracting Li compensates for index-dependent noise bias before the branch-free Most Significant Bit (MSB) decision.It defines bµi = ⌈µi⌉ = i − n/2 + 2 and Li = bµi + q/4.Source: 4) Bias-aware decoding · p. 3

III. ARCHITECTURE-AWARE IMPLEMENTATION

The implementation targets a Cortex-M33 and exploits byte-lane operations for RBLWE polynomial arithmetic, alongside packed message processing. The paper also notes a deployment and security-claim boundary tied to decryption-failure rate.

A. Target Resources and Data Representation

  • On the EFM32PG28 Cortex-M33, the evaluated baseline uses (n, q) = (256, 256) with contiguous byte coefficients, placing four coefficients in each 32-bit register.Independent byte-lane wraparound makes per-lane arithmetic equivalent to reduction modulo 256.Source: A. Target Resources and Data… · p. 3
  • The multiplication algorithm processes equal-length coefficient ranges four at a time with UADD8 and USUB8, using scalar operations only for the zero-to-three-coefficient tails.For q = 128, it applies a final seven-bit mask.Source: A. Target Resources and Data… · p. 3
  • A packed message codec stores groups of eight encoded coefficients and decodes coefficients using an index-adjusted offset.The algorithm labels these procedures PACKEDENCODE and PACKEDDECODE.Source: A. Target Resources and Data… · p. 3
  • The reported decryption-failure rate precludes a deployment recommendation and the CCA2-security claim developed in Section IV-B.The source limits this caveat to the implementation under comparison.Source: A. Target Resources and Data… · p. 3

B. Acceleration Mechanisms

The accelerated baseline combines four-lane byte-SIMD polynomial arithmetic, packed message processing, and buffered Secure Element randomness. The following security section defines the adversary model and introduces countermeasures.

B. Acceleration Mechanisms

  • Four-lane polynomial arithmetic and packed message processing accelerate the baseline, with the codec handling eight message bits per byte without SIMD arithmetic.The polynomial kernel processes four coefficients at a time, using scalar handling only for the remaining zero-to-three coefficients.Source: B. Acceleration Mechanisms · p. 3
  • Fig. 3 maps KeyGen, Encrypt, and Decrypt to the shared TRNG-backed Sampler Bank and the four-lane engine used for polynomial arithmetic and message encoding.The baseline dataflow is shown on the EFM32PG28.Source: Figure 3 · p. 4
  • Buffered Secure Element TRNG output supplies binary samplers; cold-start measurements count every required refill, while prefetched mode moves refills off the timed path.These changes affect execution mapping rather than the RBLWE equations or Bernoulli distributions.Source: B. Acceleration Mechanisms · p. 4

IV. SECURITY COUNTERMEASURES

  • The security-countermeasure section begins by defining the deployment adversary model before presenting protections.Source: §IV · p. 4

1) Adversary Capabilities:

The paper specifies physical and chosen-ciphertext adversary capabilities, then adds constant-time execution, fault hardening, and a CCA2-oriented wrapper. The wrapper re-encrypts for verification and rejects mismatches without exposing a validity flag.

1) Adversary Capabilities:

  • The adversary may choose plaintexts, submit malformed ciphertexts, observe outputs and execution behavior, collect timing and power traces, and inject one targeted fault per execution.Faults include instruction skips, state zeroing, and value substitution; underlying RBLWE, hash, and key-derivation primitives are assumed secure.Source: 1) Adversary Capabilities · p. 4

B. Countermeasure Design

  • The countermeasure set adds constant-time execution, fault hardening, a CCA2-oriented transform, and first-order shared CPA decryption.These protections are tested in the work, building on fault-resilient Binary Ring-LWE.Source: B. Countermeasure Design · p. 4

1) Constant-Time Execution:

  • Replacing skip-zero branching with a full-width mask makes each multiplier coefficient follow the same loop structure, accumulating zero or its negacyclic shift.The packed source words are masked and accumulated with byte-lane addition or subtraction according to whether the shift wraps.Source: 1) Constant-Time Execution · p. 4

2) Fault-Injection Hardening:

  • Key-generation failures erase both key objects, and decryption releases candidate data only when independent forward and reverse comparisons pass without internal error.The final output loop and store remain a non-redundant point that can still be exploited.Source: 2) Fault-Injection Hardening · p. 4

3) CCA2-Oriented Protection:

  • The CCA2-oriented layer encrypts a fresh binary vector, masks the message in c3, and authenticates the complete ciphertext in c4.Its SHA-256-based derivations are domain-separated; the wrapper follows a deterministic re-encryption approach,.Source: 3) CCA2-Oriented Protection · pp. 4–5
  • Decryption rebuilds ciphertext components and returns the candidate message only when all three match; otherwise it returns R(z, H(C)) without exposing a validity flag.Internal processing failures, such as a failed Secure Element hash call, are reported as errors.Source: 3) CCA2-Oriented Protection · p. 5, Figure 4 · p. 5
  • The wrapper uses its own byte layout and is evaluated empirically rather than supported by a formal CCA2 proof.It is not interchangeable with standardized schemes such as ML-KEM despite following a similar re-encryption pattern.Source: 3) CCA2-Oriented Protection · p. 5

4) First-Order Shared CPA Decryption:

First-order shared CPA decryption keeps the secret polynomial and decryption computation split into two shares, then decodes without recombining them. Masking ends at message-share recombination, leaving subsequent CCA2 processing unmasked.

4) First-Order Shared CPA Decryption:

  • Each binary coefficient of r2 is represented by two arithmetic shares, refreshed before decryption with a fresh polynomial δ that shifts the shares oppositely while preserving their sum.The first share is random and the second completes the required binary value.Source: 4) First-Order Shared CPA Decryption · p. 5
  • The firmware computes c1r2,0 and c1r2,1 separately, adding c2 to the second share without reconstructing r2 or the decryption polynomial w.Because the shares are general elements of Zq, these operations use the general multiplier rather than the faster binary multiplier.Source: 4) First-Order Shared CPA Decryption · p. 5
  • The decoder converts each coefficient pair into Boolean shares using masked log2 q-bit ripple-carry addition and an ISW-style masked-AND gadget.It applies the public decoding offset without combining the shares.Source: 4) First-Order Shared CPA Decryption · p. 5
  • Output bit shares are packed into two n/8-byte buffers and combined only after all n coefficients have been decoded.Source: 4) First-Order Shared CPA Decryption · p. 5
  • The decoder and key-share refresh consume 6n random bytes per decryption, or 1,536 bytes for Set 1; the Set 1 source path also holds four 256-byte polynomial temporaries and a 256-byte refresh buffer.The random-pool failure path clears output and returns an error.Source: 4) First-Order Shared CPA Decryption · p. 5
  • The implemented protection is first-order shared CPA decryption, not a fully masked CCA2-PKE operation.CCA2 hashing, re-encryption, comparison, and output selection remain unmasked after message-share recombination.Source: 4) First-Order Shared CPA Decryption · pp. 5–6

V. EXPERIMENTAL SETUP AND METHODOLOGY

The evaluation uses cumulative configurations and audits the hardened binary for countermeasure behavior. Cycle measurements distinguish prefetched-entropy latency from cold-start latency, while memory figures use linker allocations.

A. Evaluated Configurations

  • Seven cumulative configurations progress from scalar arithmetic and codec with direct TRNG calls to packed, branch-free, CCA2/fault-protected, and first-order shared CPA builds.End-to-end measurements start without prefetched randomness, and CCA2 processing remains unmasked.Source: A. Evaluated Configurations · p. 6

B. Toolchain Constraints and Binary-Level Verification

  • The evaluated firmware uses GCC 12.2.1 for Thumb Cortex-M33 code, compiled as C17 with -Os and -fno-lto; changing the compiler configuration requires repeating the binary audit.Compiler identity, options, and source revision are part of the evaluated configuration.Source: B. Toolchain Constraints and… · p. 6
  • The Set 1 hardened binary audit confirmed mask-based multiplication, fixed control flow in masked decoding, full-length ciphertext comparison, and branch-free implicit-rejection selection.Remaining loop branches depended only on fixed public iteration counts.Source: B. Toolchain Constraints and… · p. 6

C. Performance and Memory Measurement

  • DWT cycle measurements distinguish latency with prefetched entropy from cold-start latency that includes synchronous TRNG refill and other operation costs.Cold-start results are conservative measurements, not formal worst-case bounds; prefetching moves refill work and energy outside the timed window.Source: C. Performance and Memory Measurement · p. 6
  • Flash is linked .text+data, static RAM is allocated .data plus ordinary .bss, and reported stack and heap are linker allocations rather than runtime high-water marks.Source: C. Performance and Memory Measurement · p. 6

D. Fixed-versus-Random Timing Tests

The evaluation combines acceleration measurements with timing, power-trace, and logical-fault procedures, while binary inspection identifies and corrects a compiler-induced masking flaw.

D. Fixed-versus-Random Timing Tests

  • Four dudect-style tests use 100,000 DWT measurements each, balanced fixed-versus-random classes, and Welch’s t-test with a |t| < 4.5 no-detection criterion.Random generation, pool refill, validation, and UART transmission remain outside the timed call.Source: D. Fixed-versus-Random Timing Tests · p. 6, Figure 6 · p. 7

E. Power-Trace Leakage Assessment

  • Component-level TVLA compares unshared and first-order shared multiplication using aligned current traces and a |t| = 4.5 threshold.Input preparation, UART synchronization, and random-pool refill occur outside the triggered capture.Source: E. Power-Trace Leakage Assessment · p. 6, Figure 7 · p. 7

F. Debugger-Assisted Fault Campaigns

  • The logical-fault campaigns apply one intervention per execution, testing state zeroing, seeded value substitutions, and emulated Thumb instruction skips at security-relevant locations.The procedure records API status, output class, candidate-bit release, crash or timeout behavior, and whether the injection point was reached.Source: F. Debugger-Assisted Fault Campaigns · p. 7

A. Per-Mechanism Acceleration Gains

  • 4.06×, 3.35×, and 3.01× are the same-core cold-start speedups for KeyGen, encryption, and decryption; Cortex-M0 comparisons show 3.52–3.75× encryption and 3.18–3.62× decryption cycle-count speedups across parameter sets.SIMD arithmetic supplies the main arithmetic gain, while batched TRNG access drives most of the KeyGen gain; all measurements use an empty TRNG pool.Source: A. Per-Mechanism Acceleration Gains · p. 7

B. Binary-Level Verification Finding

  • Binary inspection found GCC temporarily recombined Boolean shares in the C masked-AND gadget; standalone Thumb assembly removed that flaw without introducing secret-dependent branches or memory accesses.The replacement keeps the four ISW cross-products in separate registers.Source: B. Binary-Level Verification Finding · p. 7

C. Performance Impact of Staged Security Countermeasures

The staged protections have operation-dependent performance costs, while timing, TVLA, and logical-fault tests provide evidence of protection and expose a limited output-integrity weakness under instruction skips.

C. Performance Impact of Staged Security Countermeasures

  • Branch-free execution raises KeyGen cycles; CCA2 adds recovery, re-encryption, verification, and implicit rejection to decryption, while sharing leaves encryption essentially unchanged but dominates KeyGen and decryption costs.The stated masking costs include general multiplication on arithmetic shares, key refresh, and masked decoding.Source: C. Performance Impact of Staged… · p. 7
  • 29.6% to 4.0%: the Set 1 KeyGen reduction from prefetching falls between the branchy CPA baseline and final shared configuration.Final-configuration encryption and decryption improve by 0.9% and 6.8%, respectively; the benefit follows the share of randomness in the timed path.Source: C. Performance Impact of Staged… · p. 7, Table III · p. 8, Table II · p. 8

D. Resistance to Timing Attacks

  • All four timing statistics remained below |t| = 4.5 without sustained growth, so no class-dependent timing was detected in this (256, 256) experiment.This is empirical evidence, not a universal proof of constant-time execution.Source: D. Resistance to Timing Attacks · pp. 7–8

E. Power-Trace Leakage

  • Unmasked multiplication crossed the |t| = 4.5 threshold, while shared multiplication and other protected operations remained below it; no statistically significant leakage was detected under the applied conditions.Masked CCA2 operations sit closer to the threshold because their traces also include unmasked hashing, re-encryption, and comparison logic.Source: E. Power-Trace Leakage · p. 8, Table IV · p. 8

F. Resistance to Fault-Injection Attacks

  • 2,612 value-substitution trials safely rejected, but six selector-store and loop-control skips silently corrupted valid output; no authentication bypass or weak key was observed after hardening.The zeroing records did not independently log each target’s pre-injection value, so already-zero targets cannot be distinguished retrospectively from effective zeroing faults.Source: F. Resistance to Fault-Injection Attacks · pp. 8–9, Table V · p. 9

G. Comparison with Prior Embedded Lattice Implementations

The comparison uses normalized efficiency and documented security-feature evidence because the implementations lack a common benchmark boundary. The discussion and conclusion describe a staged move from accelerated RBLWE to a hardened Cortex-M33 implementation, while delimiting the evidence and residual fault risk.

G. Comparison with Prior Embedded Lattice Implementations

  • Table VI compares the branch-free CCA2/fault-protected unmasked configuration with prior embedded Binary Ring-LWE implementations, excluding masking without equivalent reports and substantially different schemes.The comparison does not include shared-key generation or first-order shared CPA decryption.Source: G. Comparison with Prior Embedded… · p. 9, Table VI · p. 10
  • Fig. 8 scores encryption and decryption efficiency by normalized cycle counts, and four security axes by an ordinal evidence rubric.The rubric assigns 1 to experimentally or formally supported features, 0.5 to unvalidated claims, and 0 to features not demonstrated; zero does not establish absence.Source: G. Comparison with Prior Embedded… · p. 9, Figure 8 · p. 9
  • Set 1 leads encryption efficiency, while Ebrahimi and Bayat-Sarmadi lead decryption because their Cortex-M0 result carries no masking overhead.Fig. 8 profiles are descriptive rather than directly rank-equivalent because platforms, moduli, and protection boundaries differ.Source: Figure 8 · p. 9, G. Comparison with Prior Embedded… · p. 9

H. Discussion

  • Security and DFR estimates apply only to the original uniformly sampled binary parameters and bias-aware decoder, not automatically to the custom PKE wrapper.Sharing covers CPA decryption, not oracle and re-encryption logic; fault results cover the tested single-point logical model.Source: H. Discussion · p. 9

VII. CONCLUSION

  • Binary-level checks confirmed countermeasures survived compilation and caught a compiler-induced masking flaw fixed in hand-written assembly; tests found a residual instruction-skip risk at output selection.The reported evidence includes Dudect timing tests, component-level TVLA, and 2,678 fault trials; the unduplicated output-selection step could be hardened by duplicating the store or checking loop completion.Source: §VII · p. 10
Loading 2610.07820v1…