CC #8: Haters Gonna Corrupt, Corrupt, Corrupt

Hey 👋! Welcome to the 8th issue of authenticated twaddle, err ciphertext compression.

Range considered. new ePrints posted between Sun, 2 Jan 2022 12:01AM UTC and Sun, 9 Jan 2022 12:01AM UTC!

As expected, this was another slow week on ePrint with only 20 new papers.

Post-Quantum Crypto

Efficient Lattice-Based Blind Signatures via Gaussian One-Time Signatures — In CC #7 we saw blind signatures and that the original schemes did not support concurrent execution. Another drawback of the original schemes is that they rely on pre-quantum assumptions like RSA and discrete log. You might say, why not just built one from lattices? If prior experience is any guide, you can build anything from lattices. In this case, however, that seems harder than usual, with recent work showing that all the initial lattice-based blind signature schemes were either broken or had gaps in their proofs. Later work has crossed the barrier and built provably secure lattice-based blind signature schemes, but they were not efficient. This paper proposes a lattice-based blind signature scheme that is provably secure and efficient: if you want to sign ~1 million documents, the signatures are ~100KB, the public keys are ~1MB, and signing needs ~10MB of communication.

Blockchains

Formalizing Delayed Adaptive Corruptions and the Security of Flooding Networks — It’s been a while since we discussed the dirty secrets of traditional blockchains, so let’s dive back into it. Say you mined the next bitcoin block, your next task is to convince everyone to use your block (and mine on top of it.) Of course if 51% of the hashpower hated you, they can just ignore you and continue mining till one of them finds a block and build on top of that, and in the long-term their fork will win out. But, if you take a step back and look at the network structure, the bitcoin network is not a fully connected graph, it is clustered (like the internet.) So, it suffices for just your neighbors on the graph to hate you to stop your message from reaching the wider network. In other words, an adversary that can do arbitrary adaptive corruptions might be able to silence you over a clustered network graph with fewer than 1/2 corruptions. Indeed, prior work has shown communication lower bounds in this model. This paper takes a different approach by weakening the adversary, it can still do arbitrary adaptive corruptions but now with a time delay, and proves security based on the delay parameter.

Fancy Credentials

Security Analysis of Coconut, an Attribute-Based Credential Scheme with Threshold Issuance — Recall that Anonymous credentials allow a user to prove identity in a privacy-preserving manner. The user first asks a trusted Issuer (think Identity Provider) to issue them the “anonymous credentials” which can then be spent in an unlinkable manner. OG schemes like PrivacyPass could only support simple notions of identity (“this user is not a bot”), could only be used once (you need to stockpile credentials for many uses), and could only be redeemed with the Issuer (you need a centralized architecture). Later work supported more complicated notions of identity (many public and private attributes) and could be used many times, and the current state-of-the-art scheme Coconut overcame the final hurdle as well with threshold issuance where you work with a bunch of authorities (with some fraction being honest) to generate and redeem credentials. However, the Coconut paper didn’t include a formal proof of security, this paper fills that gap (and, along the ride, improves the scheme.)

Fancy Signatures

Lattice-based Signatures with Tight Adaptive Corruptions and More — Recall that the traditional security notion for signatures is Existential Unforgeability under Chosen Message Attack (EUF-CMA), where the adversary is given a signing oracle and a public key (to verify signatures) with the task of producing a valid signature on a new message.¹ But notice that this definition does not immediately capture the setting where you have many users and just want to forge a signature from one of them. For that, we need the multi-user analog of this definition, multi-user EUF-CMA (MU-EUF-CMA), where the adversary is given $N$ signing oracle and $N$ public keys corresponding to $N$ users, with the task of producing a valid signature on a new message, from any of the $N$ users. You might have already noticed that EUF-CMA implies MU-EUF-CMA because you can just guess the user for which the adversary will output a forgery and your success probability will be $1/N$ the EUF-CMA success probability. And, you are right. In other words, as long as you are willing to accept a linear in $N$ loss in security (your lower bounds for multi-user will be the single-user ones divided by $N$), you get multi-user security for free. However, for large $N$, this can be problematic. This is partly why cryptographers obsess so much over tight reductions, they don’t want to think about the $N$, they want the higher security for some fixed small price irrespective of $N$. However, in this case, prior work has shown that a tight reduction may be impossible generically, implying that we may need to specifically construct such schemes. This paper proposes a new LWE-based signature scheme that has tight MU-EUF-CMA security.

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.

Feel like this can be made better? Please let me know via 📝 this Google Form.

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. 4A5DEA7BB2CB8D5D0A2B868615F1E978