Welcome to the fourth issue of Ciphertext Compression, meant to be a quick digest of what happened on ePrint last week. If you are wondering why I am doing this, I am wondering that too, see the this post for what I was thinking.
Range considered. new ePrints posted between Sun, 24 Oct 2021 12:02AM GMT and Sun, 31 Oct 2021 12:02AM GMT!
Breaking the $IKEp182 Challenge — In analogy to the RSA challenge, Microsoft created the SIKE Cryptographic Challenge asking for solutions to specific instances of the Computational Supersingular Diffie-Hellman1 problem at varying hardness. This paper chronicles how the authors solved the terribly named
Secure Featurization and Applications to Secure Phishing Detection — While machine learning (ML) models are generally black box, we can gain some explainability by controlling the inputs. For instance, if I preprocess the input so it only contains relevant data, I can be sure that the ML model is not training on irrelevant data (it might still pickup irrelevant patterns but that’s a topic for a different day.) This preprocessing is the art of featurization where you want to represent raw data in a form that is optimal for an ML model. Now, if you want to do an ML task like phishing detection you want to hide the entire ML process from the client, not just the model evaluation like prior work, because knowing the featurization step can allow an adversary to evade the system (for instance, if the featurization took an email and returned just the distinct words an attacker can craft their emails to have the same words as benign emails.) This paper formalizes and designs secure protocols for secure featurization.3
Franchised Quantum Money — Recall that the no-cloning theorem implies that an adversary cannot make copies of a quantum state that encodes information they do not know and incorrect attempts to read information off the state would destroy it. In the early days of quantum information, more than a decade before BB84, Wiesner observed that this lends itself to a private-key money scheme where a trusted bank with a secret key $k$ can, for each serial number $n$ that it wants to generate a bank note for, generate a random number $x \gets \PRF_k(n)$ and use it to generate a quantum state $\lvert \psi_x \rangle$ and give $(n, \lvert \psi_x \rangle)$ to the requestor. Further, the bank can verify a note $(n, \lvert \psi_x \rangle)$ by checking that it encodes $x \gets \PRF_k(n)$. However, notice that this scheme not only requires a trusted bank to generate notes, but to also verify notes, and publicly-verifiable quantum money (from standard cryptographic assumptions) has been an open-problem for at least 2 decades. This paper makes progress towards this goal by presenting a weaker form of publicly-verifiable quantum money, one where users can request a unique-to-them verification key and use it to verify bank notes, from one-way functions.
Public-Key Quantum Money with a Classical Bank — This paper, using heavy-weight cryptographic primitives like quantum fully-homomorphic encryption (which we nowadays just abbreviate as LWE) and post-quantum indistinguishability obfuscation for classical circuits, shows how to build a publicly-verifiable quantum money scheme with a classical mint (the quantum bank note is generated via a 2-party protocol between the quantum user and the classical mint with classical communication.)
With a Little Help from My Friends: Constructing Practical Anonymous Credentials — When I say Anonymous Credentials you probably think Privacy Pass, but there is an entire zoo of them nowadays. This paper constructs a multi-show (contrast with PrivacyPass’s one-show) anonymous credentials that splits the computation between a low-power core device (think smart card) and a helper device (think smartphone) to achieve fast showing.
Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography — Comparing two numbers in constant-time is easy,4 comparing two arrays of numbers in constant-time is less easy but we have libraries for it,5 but comparing two compressed FO ciphertexts in constant-time is not easy. This paper looks at the FO transformation in Kyber and Saber, shows an attack against a recent proposal for side-channel resistance and proposes remediations.
Thanks for sticking till the end. 💜
Obvious Disclaimer. Views are mine and not serious. All mistakes are mine. If you’d like to point them out, shoot me an email. Maybe I can embed secret messages here and no one will notice. 489EBF2F32A98B8312F6ACEF6862CB23
On the challenge page, Microsoft calls the problem “Supersingular Computational Diffie-Hellman” and abbreviates it as “SSCDH”. 🤮 So, anyway, the title is variants of this abbreviation with the “C” versions corresponding to CSIDH, there seems to be a paper on ePrint using these abbreviations so good enough for me. ↩︎
I kept reading it as
If the “security by obscurity” nature of this is bothering you too, unfortunately, in most abuse situations, this seems necessary—Jon Callas calls this the “oracle” problem where if you reveal a detection oracle, the adversary can keep making small perturbations till it evades detection. ↩︎
fwiw, it is not super easy, like using
===in JS, but if you care and are in a reasonable language, you can likely implement it correctly. ↩︎
before anyone yells at me for giving a rust example for a constant-time library, consider the following. I used to be a “the C is literally the first letter in crypto” person and I understand that the Rust compiler / LLVM backend thinks it is the shit and may fuck around with your hand-crafted side-channel resistant code and the subtle crate is only “best effort”, but do you really want to give up the productivity of Rust? There is also a lot of recent activity in getting LLVM (and the Rust compiler by extension) to understand side-channel resistance and once that stuff lands, the downsides are mostly gone. ↩︎