Welcome to the fifth issue of Ciphertext Compression (now abbreviated as “CC”), 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 this post.

Range considered. new ePrints posted between Sun, 31 Oct 2021 12:02AM UTC and Sun, 07 Nov 2021 12:02AM UTC!


Server-Aided Continuous Group Key Agreement — Recall that the Signal protocol creates pair-wise E2EE connections between devices and that traditional group messaging, at a high-level, is just a collection of pair-wise channels with some group management slapped on top. Sure we can do clever things within these constraints to avoid the scalability problem from just encrypting each message to all the participants (termed client-side fan-out) like sender keys (cf. WhatsApp) and asynchronous ratcheting trees (cf. MLS) but at the end of this day—this paper points out—this model is an oversimplification that does not take advantage of the structure provided by having an untrusted server in the middle, and combines that observation with cryptographic magic to create a lower-bandwidth group messaging system.

Formal Analysis

An In-Depth Symbolic Security Analysis of the ACME Standard — I love ACME, I recently had to setup a webserver and getting HTTPS to work took less than 5 minutes with Caddy (which uses ACME under the hood.) While previous symbolic analyses of ACME focused exclusively on the cryptography, this paper includes the lower-level details like message formats and state.


Foundations of Transaction Fee Mechanism Design — Returning to the theme of dirty secrets of traditional blockchain systems—transaction fees—did you know that miners historically could include whichever transactions they liked in the block they are mining!? Transaction fees are a way for users to bribe miners to include their transactions, and typically miners include the transactions that pay the most fees in their next block. This transaction fees setting can be modelled as an auction where users want their transaction to get a spot in the next block. But this auction is different from the ones we study in game theory, the entity running the auction, the miner, cannot be trusted and may even collude with users to enhance their outcome (think injecting bids). This paper looks at a “dream” transaction fee mechanism (defined in prior work), and proves that it is impossible.

Themis: Fast, Strong Order-Fairness in Byzantine Consensus — As mentioned above, in traditional blockchain systems, there is no relationship between the order that transactions arrive in and the order that they are pushed onto the chain; for instance, a transaction with higher transaction fees can be pushed earlier. Indeed, as prior work like the Flash Boys 2.0 paper pointed out, this behavior is being exploited to front-run transactions on decentralized exchanges (think exchanges mediated by smart contracts on Ethereum). The long term solution to this problem is fair ordering1 which informally translates to including transactions in the order that most nodes see them. While prior schemes for fair ordering needed $O(n^2)$ time (in the optimistic case) for a committee of $n$ nodes, this paper proposes a protocol that needs $O(n)$ time (in the optimistic case).

Searching Encrypted Databases

Efficient Searchable Symmetric Encryption for Join Queries — Recall that an equi join is a join on equality; i.e., a SQL query like SELECT songs.* FROM playlist, songs WHERE playlist.song_id = songs.song_id. Prior work on doing join queries on encrypted databases required pre-computing the joins (i.e., compute the join and then encrypt it), this paper remedies the situation by proposing a scheme that does not require one to precompute joins. The resultant scheme still needs pre-computation dependant on the number of attributes you want to join on, and its leakage is now also dependant on the entropy of the attributes you want to join on (if you choose to join on high-entropy attributes like song_id above, you’re fine, but if you wanted to join on low-entropy attributes like genre, you might leak information.)


3-Party Distributed ORAM from Oblivious Set Membership — Encryption is awesome but we sometimes find ourselves in environments where we need more, like when we are forced to use untrusted memory, encryption hides the data but using just it leaks the access patterns which in turn may leak the sensitive data. The easy solution is to read the entire memory each time you need something (but this is bonkers!) Oblivious RAM (ORAM) protocols provide better performance by inducing only a polylogarithmic overhead (they turn your one query into a bunch of queries and the new queries look random to the server). However, notice that ORAMs don’t map nicely to the MPC world where we don’t have a trusted client talking to untrusted memory but a bunch of participants (some of whom are potentially corrupted) who want to talk to untrusted memory. Here, we need a different primitive, Distributed Oblivious RAM (DORAM), which affords exactly this—a bunch of MPC participants talking to untrusted memory. This paper presents a scheme that reduces the communication needed in a DORAM protocol from the current best of $O(\log^3(N))$ to $O(\log(N))$.

Closing Words

Thanks for sticking till the end. 💜

You can subscribe to this hooey via Buttondown (using email or rss) and find it on Twitter.

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

  1. If you noticed that this malicious re-ordering is only possible because the attackers can see the pending transactions in cleartext (leading to front-running) and just hiding the transaction data would alleviate the issue, you are mostly right. However, as the paper points out, schemes to hide the transaction data might still leak metadata which may be used for front-running. So, I agree with the paper’s suggestion that combining fair ordering schemes with transaction data hiding schemes leads to the best chance of people sleeping better at night. ↩︎