Hey 👋! It’s been a while since the last issue—I guess that fixes my resolution for this year to be more consistent with this folly. 🙇 Oh, happy new year to y’all! 🥳
Range considered. new ePrints posted between Sun, 26 Dec 2021 12:01AM UTC and Sun, 2 Jan 2022 12:01AM UTC!
As expected, this was a slow week on ePrint with only 24 new papers.
E2EE Messaging
Hecate: Abuse Reporting in Secure Messengers with Sealed Sender — Recall that plain E2EE is just an aspect of creating safe experiences for users. We typically also want other features like abuse reporting (you should be able to report abusive messages in a binding manner to a third-party moderation service), abuse source tracing (if you report an abusive message that has been forwarded to you, the third-party moderation service should be able to determine its true origin), and metadata privacy (the resulting system should compose nicely on top of metadata-private E2EE messaging.) Building on top of prior work that has achieved subsets of this functionality, this paper cohesively achieves all of them at once, while keeping the individual security guarantees and being faster.
Lightweight Crypto
Categorization of Faulty Nonce Misuse Resistant Message Authentication — It looks like wide (>256-bit) permutations are the future of symmetric crypto, we rarely encrypt small blobs, and modern desktop and mobile platforms have SIMD instructions, so we get better performance for free. But, at the same time, we are building lightweight devices that handle sensitive data like bluetooth at-home covid tests (h/t foone). So, we should also look at the other extreme of the spectrum, narrow (<128-bit) permutations. An immediate issue with <128-bit permutations is that, by the birthday bound, they only provide 64-bit collision resistance. This is especially problematic if we want to use them to build MACs. This paper enumerates MAC constructions based on 2 permutations calls (given a hash of the message, a nonce, and two keys; think Wegman-Carter), identifies that 10 of them have the potential for beyond-birthday security, 9 provably achieve beyond-birthday security, and 4 achieve it even in the presence of bounded nonce reuse.
Lattice Crypto
Where Star Wars Meets Star Trek: SABER and Dilithium on the Same Polynomial Multiplier — I was today years old when I learned that Dilithium is a Star Trek thing. 😬 Anyho, skipping past that, one reason symmetric crypto is converging on the idea of building one permutation and having every primitive be built on top of that permutation is that it admits hardware acceleration with fewer, higher utilization components. This is in contrast to the current situation where we need separate hardware for AES and SHA2. This paper starts by examining the NIST PQC Round 3 finalists and notices that SABER and Dilithium exhibit synergy,1 both can use Keccak and further can be made to use the same acceleration for polynomial multiplication (the two most expensive parts of accelerating these schemes per prior work.) Then it then defines these schemes (over shared polynomial multiplication), shows that they remain secure, and implements them on FPGAs to understand its performance and resistance to side-channels.
Fancy Signatures
Compact Cut-and-Choose: Boosting the Security of Blind Signature Schemes, Compactly — Blind signature schemes allow a user to generate signatures on messages without revealing the message to the signer. The user first “blinds” the message to generate a “blinded message”, requests a signature on it to get a “blinded signature”, and finally “unblinds” it to get a signature on the true message. This flow, among other things, can be used to add service-level unlinkability to architectures where you have distinct identity and service providers, you can request blind signatures from the identity provider and use the unblinded signature to authenticate with the service provider. However, it was recently shown that a bunch of current blind signature schemes are not secure in the presence of concurrent execution. Later work has proposed “boosting” existing schemes to achieve secure concurrent execution. This paper improves the state-of-the-art in “boosting” by significantly reducing the communication overhead.
(Editor’s Note (from the future): See, also, 2022/007 which independently and concurrently improved “boosting” using similar ideas.)
Fancy Symmetric Crypto
Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over $\FF^n_p$ — The algebraic computation model inside modern zero-knowledge proof systems is in stark2 contrast to desktop computers, the cost is no longer bit operations (like xor) but algebraic operations (like multiply) over some prime field. This is why zk folks use otherwise obscure hash functions like the “Pedersen hash” or “Poseidon”, it is not just to seem cooler than the rest of us, they want primitives that are cheaper in this algebraic model. This paper tries to take a step back and study the landscape of permutations that can be used to build primitives that are fast in this algebraic model, and as a consequence produces an algebraic hash function, termed “Neptune”, that is faster in this algebraic model than the current state-of-the-art Poseidon.
Closing Words
Thanks for sticking till the end. 💜
I switched up the formatting a little bit (made the font a bit larger 📏, the headings tad thinner 👷, replaced feather icons with emoji 😍, and more), if you have thoughts on that, or on anything really 📝, feel free to share them (anonymously) via this Google Form.
You can subscribe to this hooey via Buttondown (using email or rss) and find it on Twitter.
Obvious Disclaimer. Views are mine. All mistakes are mine. If you’d like to point them out, shoot me an email. Maybe I can covertly embed secret messages here. 77352782207717470D8D38095B9BA79E