International Association
for Cryptologic Research

A zero-knowledge proof is a cryptographic protocol where a prover can convince a verifier that a statement is true, without revealing any further information except for the truth of the statement. More precisely, if $x$ is a statement from an NP language verified by an efficient machine $M$, then a zero-knowledge proof aims to prove to the verifier that there exists a witness $w$ such that $M(x,w)=1$, without revealing any further information about $w$. The proof is a proof of knowledge, if the prover additionally convinces the verifier that it knows the witness $w$, rather than just of its existence.

This article is a survey of recent developments in building practical systems for zero-knowledge proofs of knowledge using vector oblivious linear evaluation (VOLE), a tool from secure two-party computation.

A large number of works prove lower bounds on space-time trade-offs in preprocessing attacks, i.e., trade-offs between the size of the advice and the time needed to break a scheme given such advice. We contend that the question of how much {\em time} is needed to produce this advice is equally important, and often highly non-trivial. However, this question has received significantly less attention. In this paper, we present lower bounds on the complexity of preprocessing attacks that depend on both offline and online time. As in the case of space-time trade-offs, we focus in particular on settings with ideal primitives, where both the offline and online time-complexities are approximated by the number of queries to the given primitive. We give generic results that highlight the benefits of salting to generically increase the offline costs of preprocessing attacks. The majority of our paper presents several results focusing on {\em salted} hash functions. In particular, we provide a fairly involved analysis of the pre-image-and collision-resistance security of the (two-block) Merkle-Damgård construction in our model.

Secure computation has become a necessity in the modern world. Its applications are widespread: from allowing medical researchers to compute statistics over private patient data without violating HIPAA to helping large companies like Meta and Google avoid GDPR fines. A ubiquitous and popular choice for secure computation is Multi-party Computation (MPC). Most MPC protocols work over finite fields or rings, which means that encoding techniques are required to map rational-valued data into the algebraic structure being used. Leveraging an encoding technique introduced in "$\mathsf{PIE}$ : $p$-adic Encoding for High-Precision Arithmetic in Homomorphic Encryption", we present $\mathsf{Mercury}$ - a family of protocols for addition, multiplication, subtraction, and division of rational numbers. Notably, the output of our division protocol is exact (i.e., it does not use iterative methods). Our protocols offer significant improvements in both round complexity and communication complexity when compared with prior art, and are secure for a dishonest minority of semi-honest parties. We emphasize that the encoding technique our protocols are based on is composable, so it can be paired with any MPC protocol over a prime-order field.

A standard paradigm for building key exchange protocols with full forward secrecy (and explicit authentication) is to add key confirmation messages to an underlying protocol having only weak forward secrecy (and implicit authentication). Somewhat surprisingly, we show through an impossibility result that this simple trick must nevertheless incur a linear tightness loss in the number of parties for many natural protocols. This includes Krawczyk's HMQV protocol (CRYPTO 2005) and the protocol of Cohn-Gordon et al. (CRYPTO 2019).

Cohn-Gordon et al. gave a very efficient underlying protocol with weak forward secrecy having a linear security loss, and showed that this is optimal for certain reductions. However, they also claimed that full forward secrecy could be achieved by adding key confirmation messages, and without any additional loss. Our impossibility result disproves this claim, showing that their approach, in fact, has an overall quadratic loss.

Motivated by this predicament we seek to restore the original linear loss claim of Cohn-Gordon et al. by using a different proof strategy. Specifically, we start by lowering the goal for the underlying protocol with weak forward secrecy, to a selective security notion where the adversary must commit to a long-term key it cannot reveal. This allows a tight reduction rather than a linear loss reduction. Next, we show that the protocol can be upgraded to full forward secrecy using key confirmation messages with a linear tightness loss, even when starting from the weaker selective security notion. Thus, our approach yields an overall tightness loss for the fully forward-secret protocol that is only linear, as originally claimed. Finally, we confirm that the underlying protocol of Cohn-Gordon et al. can indeed be proven selectively secure, tightly.

Digital and paper-based authentication are the two predominant mechanisms that have been deployed in the real world to authenticate end-users. When verification of a digital credential is performed in person (e.g. the authentication that was often required to access facilities at the peak of the COVID global pandemic), the two mechanisms are often deployed together: the verifier checks government-issued ID to match the picture on the ID to the individual holding it, and then checks the digital credential to see that the personal details on it match those on the ID, and to discover additional attributes of the holder. This pattern is extremely common and very likely to remain in place for the foreseeable future. However, it poses an interesting problem: if the digital credential is privacy-preserving (e.g. based on BBS+ on CL signatures), but the holder is still forced to show an ID card or a passport to verify that the presented credential was indeed issued to the holder, what is the point of deploying privacy-preserving digital credential? In this paper we address this problem by redefining what an ID card should show, and force a minimal but mandatory involvement of the card in the digital interaction. Our approach permits verifiers to successfully authenticate holders and to determine that they are the rightful owners of the digital credential. At the same time, optimal privacy guarantees are preserved. We design our scheme, formally define and analyse its security in the Universal Composability (UC) framework, and implement the card component, showing the running time to be below 200ms irrespective of the number of certified attributes.

The $k$-nearest neighbors classifier is a simple machine learning algorithm with applications in image recognition, finance, medical diagnosis and so on. It involves a measurement which is compared against a database of preclassified vectors, so that the result depends on the $k$ vectors in the database that are closest to the measurement. In the client-server model, this classification process can be outsourced to an external party that offers machine learning as a service, where the measurement is sent in the form of a query. However, this raises privacy concerns if sensitive information is contained in the query.

We design a secure and non-interactive version of the $k$-nearest neighbors classifier, based on fully homomorphic encryption, which does not leak any information about the query to the server. Our algorithm is instantiated with the TFHE homomorphic encryption scheme, and the selection of the top-$k$ elements is done with a novel strategy based on a type of data-oblivious algorithm---sorting networks. Compared to prior work from PoPETs 2021, the asymptotic complexity is improved from $O(d^2)$ to $O(d \log^2 {k})$, where $d$ is the number of entries in the $k$-NN model. Experimental results show that the proposed protocol can be up to 16 times faster (not accounting for difference in CPU) than previous approaches for a moderately sized database.

Recently, Biryukov et al. presented a new technique for key recovery in differential cryptanalysis, called meet-in-the-filter (MiF). In this work, we develop theoretical and practical aspects of the technique, which helps understanding and simplifies application. In particular, we show bounds on MiF complexity and conditions when the MiF-enhanced attack may reach them. We present a method based on trail counting which allows to estimate filtering strength of involved rounds and perform consequent complexity analysis with pen and paper, compared to the computer-aided approach of the original work. Furthermore, we show how MiF can be combined with plaintext structures for linear key schedules, allowing to increase the number of attacked rounds or to reduce the data complexity.

We illustrate our methods on block cipher families CHAM and KATAN and show best-to-date single-key differential attacks for these ciphers.

Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates.

As a core building block of hash-based signatures, the efficiency of one-time signature (OTS) largely dominates that of hash-based signatures. The WOTS$^{+}$ signature scheme (Africacrypt 2013) is the current state-of-the-art OTS adopted by the signature schemes standardized by NIST---XMSS, LMS and SPHINCS$^+$.

A natural question is whether there is (and how much) room left for improving one-time signatures (and thus standard hash-based signatures). In this paper, we show that WOTS$^{+}$ one-time signature, when adopting the constant-sum encoding scheme (Bos and Chaum, Crypto 1992), is size-optimal not only under Winternitz's OTS framework, but also among all tree-based OTS designs. Moreover, we point out a flaw in the DAG-based OTS design previously shown to be size-optimal at Asiacrypt 1996, which makes the constant-sum WOTS$^{+}$ the most size-efficient OTS to the best of our knowledge. Finally, we evaluate the performance of constant-sum WOTS$^{+}$ integrated into the SPHINCS$^+$ (CCS 2019) and XMSS (PQC 2011) signature schemes which exhibit certain degrees of improvement in both signing time and signature size.

Topology-Hiding Computation (THC) enables parties to securely compute a function on an incomplete network without revealing the network topology. It is known that secure computation on a complete network can be based on oblivious transfer (OT), even if a majority of the participating parties are corrupt. In contrast, THC in the dishonest majority setting is only known from assumptions that imply (additively) homomorphic encryption, such as Quadratic Residuosity, Decisional Diffie-Hellman, or Learning With Errors.

In this work we move towards closing the gap between MPC and THC by presenting a protocol for THC on general graphs secure against all-but-one semi-honest corruptions from constant-round constant-overhead secure two-party computation. Our protocol is therefore the first to achieve THC on arbitrary networks without relying on assumptions with rich algebraic structure. As a technical tool, we introduce the notion of locally simulatable MPC, which we believe to be of independent interest.

Updatable encryption is a useful primitive that enables key rotation for storing data on an untrusted storage provider without the leaking anything about the plaintext or the key. In this work, we make two contributions. Firstly, we extend updatable encryption to the public-key setting, providing its security model and three different efficient constructions. Using a public-key updatable encryption scheme, a user can receive messages directly in the cloud from multiple senders without revealing their secret key. Secondly, we add signatures on ciphertexts to guarantee plaintext integrity and authenticity. We call our new primitive \emph{Public-Key Signable Updatable Encryption} ($\mathsf{PSigUE}$). Our approach ensures that only legitimate ciphertexts are accepted by the server, and the adversary cannot compromise the message integrity in the database. We bypass the conflict between public integrity verification and the malleability that comes from the update functionality.

We provide three pairing-based constructions of public-key signable updatable encryption. The first scheme, $\mathsf{PSigUE}_1$, is built using a dual-mode zero-knowledge proof of knowledge system under an assumption closely related to the $k$-linear assumption. The second scheme, $\mathsf{PSigUE}_2$, provides unlinkability in addition to public authenticity. In the third scheme, $\mathsf{PSigUE}_\mathsf{T}$, we achieve the tight security with respect of number of epochs. The construction of $\mathsf{PSigUE}_\mathsf{T}$ is inspired by tag-based tightly-secure PKE schemes.

Salary: 35,308 to 40,745 GBP

The Surrey Centre for Cyber Security (SCCS) at the University of Surrey is seeking to recruit a full-time Research Fellow in Data Resilience, Security and Privacy. The post is available with the opportunity for hybrid working – some time on campus and some from home. We welcome applicants who wish to pursue the role through flexible working patterns.

The successful candidate will be expected to conduct research within the context of the Defence Data Research Centre https://ddrc.uk/, funded by DSTL, in which SCCS is a partner, alongside the Universities of Exeter and Liverpool, and the Digital Catapult. The Centre is focusing on problems related to the use of data for Artificial Intelligence applications, particularly around the challenges of bringing raw data to the state where it can be used. We consider these problems within a defence context, such as logistics support, object tracking and data wrangling. SCCS is focused on the area of data resilience, security and privacy, considering problems such as the trustworthiness and resilience of data and issues around anonymisation.

The post holder will benefit from the research environment provided by the Surrey Centre for Cyber Security, an Academic Centre of Excellence in Cyber Security Research recognised by the National Cyber Security Centre. The Centre’s broader research agenda is in the areas of trusted computing, data privacy, privacy preserving security, applied cryptography, and a range of cyber security topics.

Closing date for applications:

Contact: Steve Schneider.

s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13336

We are looking for 1 post-doc researcher to work on the theory and practice of composition of secure hardware devices. The position is funded as part of the UKRI/EPSRC project "SECCOM: Securing composable Hardware Platforms" with funding from MoD/Dstl (UK's Defence Science and Technology Laboratory). Offers for the position will therefore be conditional on passing an identity check with Dstl.

The postdoc will be hosted by Bernardo Magri at the Systems and Software Security group at the CS department of the University of Manchester, located in the Northwest of England (https://www.cs.manchester.ac.uk/research/expertise/systems-and-software-security/).

The ideal candidate should have a PhD degree in Computer Science or related areas, and a proven record of publications in cryptography and/or security venues such as Crypto, Eurocrypt, Asiacrypt, TCC, PKC, CCS, S&P, USENIX, ACNS, ESORICS, etc. Experience with protocol composition frameworks (such as the UC framework) is a plus, but not required.

The position is at grade 7 (salary between £43k-53k/year depending on experience) and it lasts for 2 years. Positions can be filled from September 1st to December 1st, 2023, and will remain open until filled.

To apply, please send an email with the subject "SECCOM application" to bernardo.magri@manchester.ac.uk with:

Cover letter

CV

Short research statement

Names of at least 2 references

Closing date for applications:

Contact: Bernardo Magri

The Linear Equivalence Problem (LEP) asks to find a linear isometry between a given pair of linear codes; in the Hamming weight this is known as a monomial map. LEP has been used in cryptography to design the family of LESS signatures, which includes also some advanced schemes, such as as ring and identity-based signatures. All of these schemes are obtained applying the Fiat-Shamir transformation to a Sigma protocol, in which the prover's responses contain a description of how the monomial map acts on all code coordinates; such a description constitutes the vast majority of the signature size. In this paper, we propose a new formulation of LEP, which we refer to as Information-Set (IS)-LEP. Exploiting IS-LEP, it is enough for the prover to provide the description of the monomial action only on an information set, instead of all the coordinates. Thanks to this new formulation, we are able to drastically reduce signature sizes for all LESS signature schemes, without any relevant computational overhead. We prove that IS-LEP and LEP are completely equivalent (indeed, the same problem), which means that improvement comes with no additional security assumption, either.

Polynomial commitments schemes are a powerful tool that enables one party to commit to a polynomial $p$ of degree $d$, and prove that the committed function evaluates to a certain value $z$ at a specified point $u$, i.e. $p(u) = z$, without revealing any additional information about the polynomial. Recently, polynomial commitments have been extensively used as a cryptographic building block to transform polynomial interactive oracle proofs (PIOPs) into efficient succinct arguments.

In this paper, we propose a lattice-based polynomial commitment that achieves succinct proof size and verification time in the degree $d$ of the polynomial. Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023). Unlike recent constructions of polynomial commitments by Albrecht et al. (CRYPTO 2022), and by Wee and Wu, we do not require any expensive preprocessing steps, which makes our scheme particularly attractive as an ingredient of a PIOP compiler for succinct arguments.

We further instantiate our polynomial commitment, together with the Marlin PIOP (Eurocrypt 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS). Performance-wise, we achieve 26 MB proof size for $2^{20}$ constraints, which is 10X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.

Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{et al.}$ (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). Furthermore, programmable PCG's can be used similarly to generate multiparty correlated randomness to be used in silent secure N-party protocols. Previous works constructed very efficient (non-programmable) PCG's for correlations such as random oblivious transfers. However, the situation is less satisfying for the case of random oblivious linear evaluation (OLE), which generalises oblivious transfers over large fields, and are a core resource for secure computation of arithmetic circuits. The state-of-the-art work of Boyle $\textit{et al.}$ (Crypto 2020) constructed programmable PCG's for OLE, but their work suffers from two important downsides: (1) it only generates OLE's over large fields, and (2) it relies on relatively new "splittable" ring-LPN assumption, which lacks strong security foundations.

In this work, we construct new programmable PCG's for the OLE correlation, that overcome both limitations. To this end, we introduce the quasi-abelian syndrome decoding problem (QA-SD), a family of assumptions which generalises the well-established quasi-cyclic syndrome decoding assumption. Building upon QA-SD, we construct new programmable PCG's for OLE's over any field $\mathbb{F}_q$ with $q>2$. Our analysis also sheds light on the security of the ring-LPN assumption used in Boyle $\textit{et al.}$ (Crypto 2020). Using our new PCG's, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over $\mathbb{F}_q$ for any $q>2$.

Inspired by the advancements in (fully) homomorphic encryption during the last decades and its practical applications, we conduct a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications.

To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems where a set of objects with specific weights and values is involved. Finally, we give recommendations on how to run our algorithms in order to obtain better results in terms of precision.

WhatsApp is an end-to-end encrypted (E2EE) messaging service used by billions of people. In late 2021, WhatsApp rolled out a new protocol for backing up chat histories. The E2EE WhatsApp backup protocol (WBP) allows users to recover their chat history from passwords, leaving WhatsApp oblivious of the actual encryption keys. The WBP builds upon the OPAQUE framework for password-based key exchange, which is currently undergoing standardization. While considerable efforts have gone into the design and auditing of the WBP, the complexity of the protocol’s design and shortcomings in the existing security analyses of its building blocks make it hard to understand the actual security guarantees that the WBP provides. In this work, we provide the first formal security analysis of the WBP. Our analysis in the universal composability (UC) framework confirms that the WBP provides strong protection of users’ chat history and passwords. It also shows that a corrupted server can under certain conditions make more password guesses than what previous analysis suggests.

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO.

In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in $k$ for $k$-fold composition. In comparison, for standard differential privacy, we can enjoy roughly $\sqrt{k}$ loss for $k$-fold composition by applying the well-known advanced composition theorem. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO.

In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Rényi-NPDO, zero-concentrated NPDO, Gassian-NPDO, and $g$-NPDO notions. We also prove composition theorems for these generalized notions of NPDO.

We report on a new class of ECDSA signature vulnerability observed in the wild on the Bitcoin blockchain that results from a signature nonce generated by concatenating half of the bits of the message hash together with half of the bits of the secret signing key. We give a lattice-based attack for efficiently recovering the secret key from a single signature of this form. We then search the entire Bitcoin blockchain for such signatures, and identify and track the activities of an apparently custom ECDSA/Bitcoin implementation that has been used to empty hundreds of compromised Bitcoin addresses for many years.

The sum of two $n$-bit pseudorandom permutations is known to behave like a pseudorandom function with $n$ bits of security. A recent line of research has investigated the security of two public $n$-bit permutations and its degree of indifferentiability. Mandal et al. (INDOCRYPT 2010) proved $2n/3$-bit security, Mennink and Preneel (ACNS 2015) pointed out a non-trivial flaw in their analysis and re-proved $(2n/3-\log_2(n))$-bit security. Bhattacharya and Nandi (EUROCRYPT 2018) eventually improved the result to $n$-bit security. Recently, Gunsing at CRYPTO 2022 already observed that a proof technique used in this line of research only holds for sequential indifferentiability. We revisit the line of research in detail, and observe that the strongest bound of $n$-bit security has two other serious issues in the reasoning, the first one is actually the same non-trivial flaw that was present in the work of Mandal et al., while the second one discards biases in the randomness influenced by the distinguisher. More concretely, we introduce two attacks that show limited potential of different approaches. We (i) show that the latter issue that discards biases only holds up to $2^{3n/4}$ queries, and (ii) perform a differentiability attack against their simulator in $2^{5n/6}$ queries. On the upside, we revive the result of Mennink and Preneel and show $(2n/3-\log_2(n))$-bit regular indifferentiability security of the sum of public permutations.