Social Foundations of Cryptography

I’m rather excited to report that EPSRC decided to fund our grant titled “Social Foundations of Cryptography”. Our project tries to do two things.

First, we want to ground cryptographic security notions in rigorous social science findings rather than “simply” our intuitions that we write down in the introductions of our papers. In Burdens of Proof, Jean-François Blanchette characterises what we – as cryptographers – do as follows:

New cryptographic objects are generated through more or less straightforward combinations of elements of the cryptographic toolbox, such as threshold, proxy, or fairness properties. Like so many modular Lego pieces, cryptographic primitives and design patterns are assembled in new schemes and protocols exhibiting security properties with no obvious real-world equivalents. This creative process is one of the core professional activities of cryptographers, rewarded through conference presentations, journal publications, and commercial patents. Yet the cryptographic paper genre seems to require that these products of mathematical creativity be justified in some “real-world” setting, motivated either by their potential application, their evidential value, or the new threats they identify. These justificatory scenarios are remarkable in their assumptions that the properties of cryptographic objects, as designed and discussed by cryptographers, will translate transparently into the complex social settings they describe.

Our approach is to flip this approach around: make cryptographic security notions contingent on ethnographic findings. This is, of course, a tall order when it comes to, say, PRP security of a block cipher (I enjoy Phil Rogaway’s discussion of cryptographic definitions, Phil is also on our advisory board), but it is perhaps a bit more obvious when we talk about ideal functionalities in simulation-based proofs of complex cryptographic protocols. For these ideal functionalities it is not at all immediately clear they are indeed “ideal”. Still, this remains quite a daunting project and I’m rather nervous about it.

Second, we picked the settings of large-scale urban protests, i.e. ask about security notions and needs of protesters confronting agents of the state. We think these settings (we plan on doing field work in different sites internationally) are rich yet specific. That is, notions of security depend on context and grounding cryptographic notions in such contexts can unlock insights. Post-compromise security needs for a business traveller (having their phone confiscated at an airport) and for protesters (who face arrest) may be quite different.

Another key, distinguishing, feature of these settings is that security notions are quite collective rather than individual, according to our pilot study. In this study we interviewed protesters involved in the Anti Extradition Bill protests in Hong Kong (2019/2020). This work then motivated us to then take a deeper look at Telegram. However, this pilot study has the big caveat that its inquiry was somewhat limited, by necessity.

Our study was an interview study, meaning participants self-selected to discuss their security needs with us. Yet, a key challenge in engaging those who depend on security technology is that they are not trained information security professionals. They do not know and, indeed, should not need to know, for example, that confidentiality requires integrity, that existing onboarding practices can be phrased in the language of information security, which different security notions cannot be achieved simultaneously and what guarantees, say, cryptography, can give if asked. Therefore, to know exactly what is taken for granted, or put otherwise, expected or desired, in social interactions, social and technical protocols and, indeed, cryptography is of critical import.

This is where ethnography comes in, as it is uniquely placed to “unearth what the group (under study) takes for granted”. In a nutshell, it’s a social science method involving prolonged field work, i.e. staying with the group under study, to observe not only what they say but also what their social reality and practice is.

On the cryptographic side, our project consists of Ben Dowling (Sheffield) and me. On the ethnography side, it’s Andrea Medrado (Westminster) and Rikke Jensen (RHUL). But we’re hiring! We will have one postdoc position in ethnography at RHUL (perhaps not so relevant to the audience of this blog, see Rikke’s blog post) and one postdoc position in cryptography. This position is only scheduled to start in a year, but if you’re interested please let us know, we have some flexibility about when to put it on the market.

I’ve hired for postdoc positions before, but I think I’ve never been this nervous about that process as here. If working on the protest setting and putting what you’ll do at the mercy of ethnographic findings is for you, please reach out!

Our project website is here: https://social-foundations-of-cryptography.gitlab.io/

A Surfeit of SIS with Hints Assumptions

After a “lattice-assumptions winter”™ (there, I coined it now!) because “knapsack”, the last few years have seen the introduction of a bunch of newfangled SIS-like assumptions along the lines of:

Given s.t. , with short, it is hard to find a short s.t. .

That is, in some shape or form, these assumptions posit that some variant of SIS or ISIS remains hard even if you hand out some short preimages of some specially selected targets. There’s quite some variety here: BASIS instead hands out a trapdoor for a bigger related matrix, one-more-ISIS allows the adversary to pick the targets but has tight norm constraints etc.

I’ve started to track these new assumptions in the SIS with Hints Zoo, with the hope of encouraging cryptanalysis, reductions and/or re-use of existing assumptions. That page has been up for a little while. I’m blogging about it now, because it now has a few “non-trivial” entries, that you might have missed and that illustrate well that cryptanalysis and reductions are fruitful endeavours here:

Knowledge k-R-ISIS is false

Knowledge (I’m good with words like that!) of this break has been circulating a while, but since the paper breaking it is finally out, it is time to amplify the message: The knowledge version of the k-R-ISIS assumption from https://eprint.iacr.org/2022/941 is (at least morally) false. It thus gets a “BROKEN” tag.

Twin k-R-ISIS is no easier than k-R-ISIS

In Appendix A of https://eprint.iacr.org/2023/1469 we show that if you can solve Twin k-R-ISIS you can also solve k-R-ISIS (under parameters etc). It thus gets an “EQUIVALENT” tag.

-PRISIS is hard

under the M-SIS assumption and for degree , as was shown in https://eprint.iacr.org/2023/846. That is useful is established in https://eprint.iacr.org/2023/1469. It thus gets a “STANDARD” tag.

If your (favourite) assumption is missing or is misrepresented, please get in touch: PRs welcome, too.

Post-quantum oblivious PRFs from shallow PRFs and TFHE

We – Alex Davidson, Amit Deo, Daniel Gardham and me – have updated our pre-print Crypto Dark Matter on the Torus: Oblivious PRFs from shallow PRFs and TFHE. It has been around for a while, but I am now somewhat confident that we won’t squeeze more performance out of it for the time being, so this feels like the right time to blog about.

What is an OPRF and why should I care? Oblivious pseudorandom functions allow two parties to compute a pseudorandom function (PRF) together: a server supplying a key and a user supplying a private input . The server does not learn or and the user does not learn . If the user can be convinced that is correct (i.e. that evaluation is performed under the correct key) then the function is “verifiable oblivious” (VOPRF), otherwise it is only “oblivious” (OPRF). Both may be used in many cryptographic applications. Example applications include anonymous credentials (e.g. Cloudflare’s PrivacyPass), password-based key exchanges (e.g. OPAQUE) and Private Set Intersection (PSI) enabling e.g. privacy-preserving contact look-up on chat platforms.

Sounds good, seems solved! Despite the wide use of (V)OPRFs, most constructions are based on classical assumptions, such as Diffie-Hellman (DH), RSA or even pairing-based assumptions. Indeed, DH-based OPRFs are currently being standardised by the IETF. Their vulnerability to quantum adversaries makes it desirable to find post-quantum solutions, however, known candidates are much less efficient.

Oblivious PRF and FHE, I see where this is going … Indeed, given fully homomorphic encryption (FHE), there is a natural (P)OPRF candidate. The client FHE encrypts input and sends it with tag . The server then evaluates the PRF homomorphically or “blindly” using a key derived from and its own secret key. Finally, the client decrypts the resulting ciphertext to obtain the PRF output. The first challenge with this approach is performance, PRFs tend to have sufficiently deep circuits that FHE schemes struggle to evaluate them efficiently. Even special purpose PRFs such as the LowMC construction require depth ten or more, making them somewhat impractical. More generally, in a binary circuit model we expect to require depth to obtain a PRF resisting attacks with complexity .

Yet, if we expand our circuit model to arithmetic circuits with both mod and mod gates for both primes, shallow proposals exist. The main proposal even has a kewl name: “Crypto Dark Matter PRF”. In particular, the (weak) PRF candidate is

where arithmetic operations are over the integers and is the secret key. That’s it! The same work also contains a proposal to “upgrade” this weak PRF, defined for uniformly random inputs , to a full PRF, taking any . Furthermore, the works already provide oblivious PRF candidates based on this PRF and MPC, but with non-optimal round complexity. Thus, a natural question to ask is if we can construct a round-optimal (or, 2 message) POPRF based on this PRF candidate using the FHE-based paradigm mentioned above.

So what did you actually do? We construct a novel POPRF from lattice assumptions and the “Crypto Dark Matter” PRF candidate in the random oracle model. At a conceptual level, our scheme exploits the alignment of this family of PRF candidates, relying on mixed modulus computations, and programmable bootstrapping in the torus fully homomorphic encryption scheme (TFHE). This allows us to construct an OPRF candidate using only one level of bootstrapping (the most expensive operation in a FHE computation). We also explore a cut-and-choose based strategy for adding verifiability to our OPRF.

Performance. For the core online OPRF functionality, we require amortised 10.0KB communication per evaluation and a one-time per-client setup communication of 2.5MB. I’d say his makes our OPRF practical size-wise. Client computation costs are also somewhat manageable but server computation costs are quite unattractive unless you’re willing to invest in some FHE co-processor. We have some early benchmarks (using tfhe-rs) running the server code in ~150ms on 64 cores. Let me stress that this does not account for “circuit privacy” which should add a factor of 5x to 10x (or the zk systems we need, but we assume those won’t add that much overhead in computation, we do include their sizes in the estimates above). Moreover, our relatively small sizes are the effect of aggressive packing, unpacked the key material should weight about ~2GB in RAM.

Implementation. We do have a somewhat complete implementation of our scheme, but it is in SageMath and thus extremely slow. I should mention, though, that this implementation, too, does not cover the zero-knowledge proof systems we rely on to achieve malicious security.

A Formal Cryptographic Analysis of Matrix’ Core

Our work – “Device-Oriented Group Messaging: A Formal Cryptographic Analysis of Matrix’ Core” – is now out on ePrint and will be presented at IEEE S&P’24; “us” here being Dan Jones, Benjamin Dowling and myself.

Matrix is an open standard for interoperable, federated, real-time communication over the Internet. It consists of a number of specifications which, together, define a federated secure group messaging protocol enabling clients, with accounts on different Matrix servers, to exchange messages.

Last year, together with Sophía Celi, we reported several severe security issues in its cryptographic core, invalidating the cryptographic security guarantees of confidentiality and authentication in the protocol and its flagship client Element.

What we originally set out to do was to formally analyse Matrix, i.e. not “just” find some vulnerabilities that leave open the question whether there are lurking more, but to get some more rigorous assurances that whole classes of attacks will fail:

UK Crypto Day (June 2023 Edition)

Together with Nick Spooner and Sarah Meikeljohn, I’m co-organising the next UK Crypto Day.¹

Date	23 June
Venue	King’s College London
Registration	Here
Programme	https://uk-crypto-day.github.io/2023/06/23/

We got some nice speakers/talks lined up:

Jonathan Bootle: The Sumcheck Protocol, Applications, and Formal Verification

The sumcheck protocol plays a central role in many constructions of efficient zero-knowledge arguments. In this talk, I will describe the sumcheck protocol, explain why it is so useful, and discuss recent work on a machine-checkable security proof.

Bio. Jonathan Bootle is a researcher in the Foundational Cryptography Group at IBM Research – Zurich. His research focuses on constructing efficient zero-knowledge proofs, especially those based on lattice assumptions or error-correcting codes.

Bernardo Magri: YOSO – You Only Speak Once

Imagine a setting where whenever a party in a protocol sends a message, its IP address becomes known, and it gets immediately killed by the adversary in a DoS attack. This implies that in any given protocol a party can only send a single message at a random point in time. Can we do secure multiparty computation in this setting? In this talk we introduce the YOSO MPC model that is based around the notion of roles, which are randomly assigned stateless parties that can send a single message for the entire duration of the protocol. We will show how one we can leverage the infrastructure of public blockchains to securely YOSO-compute any function with private inputs.

Bio. Bernardo Magri is a Senior Lecturer at the CS department at University of Machester. His research interests are on the theoretical and practical aspects of cryptography and distributed ledgers.

Sunoo Park: Email Attribution and Election Audits

My talk will focus on two recent works. The first concerns preventing the exploitation of stolen email data. Email is used widely for personal, industry, and government communication; as such, it is a valuable target for attack. Such attacks are compounded by email’s strong attributability: today, any attacker who gains access to your email can easily prove to others that the stolen messages are authentic. We define and construct non-attributable email using a new cryptographic signature primitive.

The second paper concerns a new model of post-election audits, loosely inspired by multi-prover interactive proofs. Post-election audits perform statistical hypothesis testing to confirm election outcomes. However, existing approaches are costly and laborious for close elections—often the most important cases to audit. We instead propose automated consistency checks, augmented by manual checks of only a small number of ballots. Our protocols scan each ballot twice, shuffling the ballots between scans: a “two-scan” approach inspired by two-prover proof systems.

Bio: Sunoo Park is a Postdoctoral Fellow at Columbia University and Visiting Fellow at Columbia Law School. Her research interests range across cryptography, security, and technology law. She received her Ph.D. in computer science at MIT, her J.D. at Harvard Law School, and her B.A. in computer science at the University of Cambridge.

Michele Ciampi: On the round-complexity of secure multi-party computation

In multi-party computation (MPC), multiple entities, each having some inputs want to jointly compute a function of these inputs with the guarantee that nothing aside from the output of the function will be leaked. In this talk, we are going to investigate how many messages the parties of an MPC need to exchange to securely realise any functionality with simulation-based security in the case where there is no setup and the majority of the parties can be corrupted. We will then consider a relaxation of the standard simulation-based paradigm, and discuss whether this lead to more efficient MPC protocols which still realize non-trivial functionalities which meaningful security.

Bio. Michele Ciampi is a Chancellor’s Fellow at the School of Informatics at the University of Edinburgh. His work focuses on theoretical aspects of cryptography, including multi-party computation protocols, zero-knowledge proofs, and blockchain.

François Dupressoir: Revisiting machine-checked AKE security — Reports from a possibly active trench

Machine-checked cryptographic proofs, as supported by tools such as EasyCrypt, CryptHOL or SSProve, aim at increasing trust in cryptographic algorithms by producing machine-checkable evidence that their security follows from relatively (sometimes) standard hardness assumptions. With only a few exceptions, their application has unfortunately been limited to small, typically non-interactive, constructions. A significant exception is a Eurocrypt 2015 paper applying EasyCrypt to a family of Authenticated Key Exchange protocols, whose massive proof has unfortunately been lost to time (and some obnoxious IT practices). This talk will report on an ongoing (or perhaps, hopefully, not) attempt at understanding better the interplay between EasyCrypt, interactive protocols, and a few competing pen-and-paper definition and proof methodologies. By doing so, I hope to provoke discussions around the goal and value of security proof and their machine-checked variants, and about what “traditional” cryptographers might expect or want from proof tools.

Bio. François Dupressoir is a Senior Lecturer at the University of Bristol, where he heads the Cryptography Research Group. His research revolves around bringing formal methods and formal reasoning techniques to cryptographic security of algorithms, protocols and their implementations.

Yixin Shen: Finding Many Collisions via Reusable Quantum Walks — Application to Lattice Sieving

Given a random function with domain and codomain , with , a collision of is a pair of distinct inputs with the same image. Collision finding is a ubiquitous problem in cryptanalysis, and it has been well-studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be , and matching algorithms are known for any value of . The situation becomes different when one is looking for multiple collision pairs. Here, for collisions, a query lower bound of was shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values of , when many collisions exist.

In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the Shortest Vector Problem (SVP), with a complexity of instead of the previous .

Bio. Yixin Shen is a research fellow at Royal Holloway, University of London. Her work focuses on quantum algorithms and their application in lattice-based cryptanalysis. She completed her PhD at Université Paris Cité in 2021. After that, she worked as a postdoctoral researcher at Royal Holloway. In 2022, she obtained a five-year EPSRC Quantum Technology Career Development Fellowship.

Footnotes:

¹

Formerly, known as London-ish Crypto Day, but that produced a name clash with Liz’ London Crypto Day.

SandboxAQ Internships

You may or may not be aware that at SandboxAQ we have an internship residency programme. Residencies would typically be remote but can be on-site, they can take place year round and last between three to twelve months, full-time or part-time. To take part, you’d need to be a PhD student or postdoc somewhere.

In the interest of advertising our programme, here are two example ideas I’d be interested in.

Add SIS and (overstretched-)NTRU to the Lattice Estimator

The name “lattice estimator” at present is more aspirational than factual. In particular, we cover algorithms for solving LWE but not algorithms for solving SIS or (overstretched) NTRU. Well, we implicitly cover SIS because solving SIS implies solving LWE (and we cost that: the “dual attack”), we don’t have a nice interface to ask “how hard would this SIS instance be”. Adding this would be a nice contribution to the community, given how widely that estimator is used.

OPRFs from Lattices

Our first work on building OPRFs from lattices costs about 2MB of bandwidth if you ignore the zero-knowledge proofs and something like 128GB (yes, GB) if you count them. Since then, proving lattice statements has become a lot cheaper, so a natural project is to reconsider our construction: use newer/smaller proofs, tune the parameters, prove it in a nicer game-based model or in UC. To give you a taste of what is possible: This work building a non-interactive key-exchange (NIKE) has to solve essentially the same problem (noise drowning + ZK proofs) and achieves smaller parameters.

If you are interested, or have some other ideas, ping me and apply for a PQC resident position.

The k-R-ISIS (of Knowledge) Assumption

Our paper – together with Valerio Cini, Russell W. F. Lai, Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan – titled Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable will be presented at CRYPTO’22. A pre-print is available and here’s the abstract:

A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings.

In this work, we make progress on this question. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. Our construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones. At the heart of our SNARK is a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps, which is a candidate solution for the open problem of constructing VC schemes with openings to beyond linear functions. However, the security of our constructions is based on a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption.

In this post, I want to give you a sense of our new family of assumptions, the k-M-ISIS family of assumptions, and its variants. Meanwhile, Russell has written a post focusing on building the SNARK and Aravind has written about the nice things that we can do with our lattice-based SNARKs.

10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security for the Everyday

At Royal Holloway we are again taking applications for ten fully-funded PhD positions in Information Security. See the CDT website and the ISG website for what kind of research we do. Also, check out our past and current CDT students and our research seminar schedule to get an idea of how broad and diverse the areas of information security are in which the ISG works.

More narrowly, to give you some idea of cryptographic research (and thus supervision capacity) in the Cryptography Group at Royal Holloway: currently, we are nine permanent members of staff: Simon Blackburn (Maths), Saqib A. Kakvi, Keith Martin, Sean Murphy, Siaw-Lynn Ng, Rachel Player, Liz Quaglia and me. In addition, there are three postdocs working on cryptography and roughly 14 PhD students. Focus areas of cryptographic research currently are: lattice-based cryptography and applications, post-quantum cryptography, symmetric cryptography, statistics, access control, information-theoretic security and protocols.

To give you a better sense of what is possible, here are some example projects. These are in no way prescriptive and serve to give some ideas:

1. I am, as always, interested in exploring lattice-based and post-quantum cryptography; algorithms for solving the hard underlying protocols, efficient implementations, lifting pre-quantum constructions to the post-quantum era.
2. Together with my colleague Rikke Jensen, we want to explore security needs and practices in large-scale protests using ethnographic methods. We’ve done an interview-based (i.e. not ethnography-based) pilot with protesters in Hong Kong and think grounding cryptographic security notions in the needs, erm, on the ground, will prove rather fruitful.
3. My colleague Rachel Player is looking at privacy-preserving outsourced computation, with a focus on (fully) homomorphic encryption.
4. My (new) colleague Guido Schmitz uses formal methods to study cryptographic protocols.

Note that most of these positions are reserved for UK residents, which does, however, not mean nationality (see CDT website for details) and we can award three of our scholarships without any such constraint, i.e. international applicants. The studentship includes tuition fees and maintenance (£21,285 for each academic year).

To apply, go here. Feel free to get in touch if you have questions about whether this is right for you. Official announcement follows.

Collective Information Security in Large-Scale Urban Protests: the Case of Hong Kong

Our work – with Jorge Blasco, Rikke Bjerg Jensen and Lenka Mareková – on the use of digital communication technologies in large-scale protests in Hong Kong was accepted at USENIX ’21. A pre-print is available on arXiv. Here’s the abstract:

The Anti-Extradition Law Amendment Bill protests in Hong Kong present a rich context for exploring information security practices among protesters due to their large-scale urban setting and highly digitalised nature. We conducted in-depth, semi-structured interviews with 11 participants of these protests. Research findings reveal how protesters favoured Telegram and relied on its security for internal communication and organisation of on-the-ground collective action; were organised in small private groups and large public groups to enable collective action; adopted tactics and technologies that enable pseudonymity; and developed a variety of strategies to detect compromises and to achieve forms of forward secrecy and post-compromise security when group members were (presumed) arrested. We further show how group administrators had assumed the roles of leaders in these ‘leaderless’ protests and were critical to collective protest efforts.

Our work can be seen in the tradition of “Can Johnny Build a Protocol? Co-ordinating developer and user intentions for privacy-enhanced secure messaging protocols” which documented the divergence of what higher-risk users – such as those in conflict with the authorities of a nation state – need and want and what secure messaging developers design for. This divergence is noteworthy because “human-rights activists” are a common point of reference in discussions around secure messaging.

However, our focus is not activists but participants in large-scale protests, i.e. our focus is more closely tied to specific needs in moments of heightened conflict, confrontation and mass mobilisation. In particular, we interviewed people who were in some shape or form involved in the Anti-ELAB protests in Hong Kong in 2019/2020. Several of our participants described themselves as “frontliners” which roughly means they were present in areas where direct confrontations with law enforcement took place.

As the title suggests our data speaks to how security needs and practices in this population are collective in nature: how decisions about security are made, what security features are deemed important, how people learn to understand security technologies. As an example take post-compromise security and forward secrecy:

Round-optimal Verifiable Oblivious Pseudorandom Functions from Ideal Lattices

PKC’21 is nearly upon us which – in this day and age – means a new YouTube playlist of talks. Eamonn and Fernando wrote a nice paper on on the success probability of solving unique SVP via BKZ which Fernando is describing here:

Alex is presenting our – with Amit and Nigel – work on round-optimal Verifiable Oblivious PseudoRandom Functions (VOPRF) from ideal lattices here:

Since Alex is doing an amazing job at walking you through our paper I won’t attempt this here. Rather, let me point out a – in my book – cute trick in one of our appendices that may have applications elsewhere.