This post’s ID is 3903250242484811137.
I have several subdermal implants. I have one that lets me tap-to-pay with my left hand, two that store assorted data in their flash (one of them takes you to my website if you tap it), and two permanent magnets. I like bodymodding and subdermal implants and that sort of thing. I consider it almost a hobby of mine.
The company I bought most of these implants from is called Dangerous Things, and they sell a JavaCard implant called the flexSecure. It can run arbitrary user code on it in addition to storing plain data. It has 164KiB of available EEPROM and a minimum of 4KiB of RAM available to user applets. Since it’s a JavaCard, it’s a 16-bit processor on which we can only run JVM bytecode.
I want to buy one, program it to compute (but not verify) quantum-resistant digital signatures, and have it implanted under my skin. This post is the first in a series documenting the course of this project, and will consist of a sketch of what exactly the software side is going to look like. If you’d like, you can think of my previous post on a closely related topic as part 0 of the series.
’Cause you always work on Thursday nights
and I need something else to analyze
I’m making a fortune, painting you a portrait
of the artistPortrait of the Artist as a Young Fag, Car Seat Headrest (2010), second track off the album 3
I have a few criteria for this:
We can construct a quick low-effort table of NIST-standardized or current-candidate-for-standardization (as of this writing) primitives according to if these criteria are met:
| Primitive | Key Fits In EEPROM | Signature Under 1KiB | RAM Under 3.5KiB | Streaming Messages In | Fault Injections Easily Mitigated |
|---|---|---|---|---|---|
| Y | N | N | Y (external ) | ? | |
| Y | N | N | Y | ? | |
| Y | N | ? | N | ? | |
| HashSLH-DSA | Y | N | ? | Y | ? |
| SQISign | Y | Y | ? | Y | ? |
| Y | N | N | Y | ? | |
| SDitH | Y | N | ? | Y | ? |
| Y | Y | ? | Y | N (as of round 2 submission) | |
| QR-UOV | Y | Y | ? | Y | Y (at time of writing) |
| SNOVA | Y | Y | ? | Y | ? |
| N | Y | Y | Y | ? | |
| FAEST | Y | N | ? | Y | ? |
Thank you to the MQOM team, by the way, for giving memory usage benchmarks in the proposal! For ML-DSA, I simply relied on the fact that it is already beginning to be implemented in HSMs and TPMs (don’t, ah, ask how I know about the TPMs) and I couldn’t find a single such device with less than 32KiB of RAM (and it is the most RAM-intensive primitive the devices would generally be implementing).
This immediately eliminates 6 of 12 algorithms based solely on information I was able to glean from the standards and round 2 submissions with a minute or so given to each. It leaves:
We have to get heuristic now. Let’s consider performance.
I will immediately, unfortunately, have to eliminate SQISign, because its performance is easily the worst among any of these primitives on server hardware. I will next note that HashSLH-DSA relies on an extremely large number of hash invocations, and SHAKE relies on a permutation (Keccak-) that is going to be very slow on 16-bit hardware. I will thus also eliminate HashSLH-DSA.
And then there were four. Let’s just vomit up the number of milliseconds it takes to sign on the fastest parameter sets on the NIST reference hardware for each primitive (assuming a cycle frequency of 3GHz, because the SDitH team gave milliseconds where everyone else gave megacycles [or both, thank you FAEST team!]):
| Primitive | Signature Latency (ms) |
|---|---|
| SDitH | 2.96 |
| QR-UOV | 0.0216 |
| SNOVA | 0.0875 |
| FAEST | 0.507 |
QR-UOV is the clear winner, but I will note that this is on a 64-bit platform with 512-bit (or, for FAEST, 256-bit) SIMD instructions, not a 16-bit platform with no SIMD capability at all. This gives an artificial boost to the multivariate schemes, which can leverage SIMD effectively for linear algebra over Galois fields.
Given all of this, I’m choosing to implement QR-UOV. Note that I’d already researched it extensively for this purpose for “part 0” of this series, so I already know generally how I’m going to do fast(ish) Galois field arithmetic. By my estimation based on the round 2 spec, with as much precomputation as possible, QR-UOV signing should have a peak memory consumption of around 3.3KiB, which fits what we need. My only real issue at this stage is that QR-UOV as written is slightly underspecified, leaving out a necessary result for the rank of a particular matrix, which makes it difficult to determine how a random solution should be properly and efficiently sampled:
This hopefully will be fixed in the round 3 submission due in two weeks. If not, I shall ask about it on the NIST PQC forum mailing list and brave the small (but never zero) chance of being snarked at by DJ Bernstein. For what it’s worth, the reference implementation appears to just directly compute the rank and then do something similar to the MAYO team’s algorithm for this:
So perhaps there isn’t a clean result for the rank of the matrix.