Welcome to the second 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, 10 Oct 2021 12:01AM GMT and Sun, 17 Oct 2021 12:01AM GMT!
Encryption, with More Features
Multi-Authority ABE, Revisited — Recall that the key idea of identity-based encryption is that you can say encrypt emails to an email address like cool@person—without first getting cool@person’s public key. The way it works is that there is a trusted setup phase where a trusted 3rd party generates a main public key and a main secret key, publishes the main public key, and keeps the main secret key hidden. To send an email to cool@person you call a function that takes the text string cool@person and the main public key and generates the public key for cool@person. Later, the real cool@person can ask the trusted 3rd party for the secret key to cool@person, which the trusted 3rd party can generate using the main secret key and the text string cool@person. Notice that this flow implicitly allows the trusted 3rd party to read all encrypted emails! Recent schemes try to address this issue by allowing many trusted 3rd parties which come and go (the “decentralize trust” approach) but they still require a non-trivial trusted setup, this paper removes the trusted setup requirement.
Multi-Party Computation
Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks — Usually, MPC protocols don’t model DDoS attacks on participants, we assume that Alice, Bob, and Charlie all receive all messages and can respond with any message. This paper considers the DDoS attack model where a participant may be attacked which causes them to not be able to receive or send messages, and shows that under certain bounds on the number of participants attacked this way, they can, with some overhead, error-correct and emulate a network without these disruptions. Note that we can always assume that DDoS-ed participants are “corrupted” but the idea is that DDoS-ed is less disruptive to the protocol and we can tolerate more participants being affected by it.
Blockchains
Plumo: An Ultralight Blockchain Client — A dirty secret of traditional blockchains is that they assume that all users run a full node (a node that verifies all transactions) for the security and privacy guarantees to hold. In practice, this is very not true, Coin Dance counts only ~14k bitcoin full nodes active now. Compared to what people typically think of when they think of blockchain computation requirements, running a full node is not too bad, you can run a bitcoin full node on a mid-range VPS with a terabyte of storage, a few gigs of RAM, and a few gigs of bandwidth. But it is still not accessible to everyone, especially end-users on smartphones. If you take a step back and think about it, this is silly, if I want to know the current state, why do I need to download and verify every transaction ever made?! Can’t you just gimme the final state and a proof that you computed it correctly? Indeed, we are moving towards such a world. While previous approaches were specific to proof-of-work blockchains, this paper constructs a system can work generally over Byzantine Fault Tolerance, and in particular, over proof-of-stake.
Signatures, with More Features
BlindOR: An Efficient Lattice-Based Blind Signature Scheme from OR-Proofs — Blind signatures are really cool, they allow one to get a signer to sign messages they cannot see: the user blinds the message, sends the blinded message to the server who signs it, and the user unblinds the response to get the signed message. This flow is really useful and, for instance, is used in PrivacyPass to build unlinkable credentials. However, existing practical constructions have mostly been based on RSA or Diffie-Hellman (PrivacyPass relies on Elliptic Curve Diffie-Hellman), this paper gives a practical construction based on lattices.
Privacy
Orca: Blocklisting in Sender-Anonymous Messaging — Abuse-aware design is quite challenging. Signal’s sealed sender—sending messages without revealing the identity of the sender to Signal—is quite easy to implement if you didn’t care about abuse, open up a public API and let people send messages to anyone. If you did this you will see spam, lots and lots of it. So, to combat this, Signal periodically shares a “delivery token” with all your contacts and, by default, only people with this “delivery token” can send you messages. This stops non-contacts from spamming you. Furthermore, this design allows Signal to implement blocking by updating the delivery key and giving the wrong key to the blocked contact. However, this design does not work for people who want to receive sealed-sender messages from non-contacts (think journalists), in particular it does not support blocking. This paper proposes a system that allows blocking in this setting.
Lattice Crypto
A note on a Claim of Eldar & Hallgren: LLL already solves it — On September 21st, Sean Hallgren gave a quantum colloquium at the Simons Institute on joint work with Lior Eldar on a new quantum algorithm for lattice cryptanalysis. A few days later, a paper surfaced on GitHub (ehh, ePrint is so 2010s, cutting-edge research is on GitHub these days) showing how one can get the same results with traditional lattice cryptanalysis techniques (like LLL). This looks to be the updated version of the initial GitHub draft.
Closing Words
Thanks for sticking till the end. 💜
You can now subscribe to this hooey via Buttondown (using email or rss) and—as the AI apocalypse folks have long been warning us—this jumble of words has become sentient and created a Twitter account (because that is the first thing sentient entities do these days.)
Obvious Disclaimer. Views are mine and not serious. All mistakes are mine. If you’d like to point them out, shoot me an email. If I get more than 10 emails, I’ll create a discord and post the invite link here.