International Association
for Cryptologic Research

In many occasions, the knowledge error $\kappa$ of an interactive proof is not small enough, and thus needs to be reduced. This can be done generically by repeating the interactive proof in parallel. While there have been many works studying the effect of parallel repetition on the soundness error} of interactive proofs and arguments, the effect of parallel repetition on the knowledge error has largely remained unstudied. Only recently it was shown that the $t$-fold parallel repetition of any interactive protocol reduces the knowledge error from $\kappa$ down to $\kappa^t +\nu$ for any non-negligible term $\nu$. This generic result is suboptimal in that it does not give the knowledge error $\kappa^t$ that one would expect for typical protocols, and, worse, the knowledge error remains non-negligible.

In this work we show that indeed the $t$-fold parallel repetition of any $(k_1,\dots,k_{\mu})$-special-sound multi-round public-coin interactive proof optimally reduces the knowledge error from $\kappa$ down to $\kappa^t$. At the core of our results is an alternative, in some sense more fine-grained, measure of quality of a dishonest prover than its success probability, for which we show that it characterizes when knowledge extraction is possible. This new measure then turns out to be very convenient when it comes to analyzing the parallel repetition of such interactive proofs.

While parallel repetition reduces the knowledge error, it is easily seen to increase the completeness error. For this reason, we generalize our result to the case of $s$-out-of-$t$ threshold parallel repetition, where the verifier accepts a claim if $s$-out-of-$t$ of the parallel instances are accepting. An appropriately chosen threshold $s$ allows both the knowledge error and completeness error to be reduced simultaneously.

We introduce a novel framework for quantifying the bit security of security games. Our notion is defined with an operational meaning that a $\lambda$-bit secure game requires a total computational cost of $2^\lambda$ for winning the game with high probability, e.g., 0.99. We define the bit security both for search-type and decision-type games. Since we identify that these two types of games should be structurally different, we treat them differently but define the bit security using the unified framework to guarantee the same operational interpretation. The key novelty of our notion of bit security is to employ two types of adversaries: inner adversary and outer adversary. While the inner adversary plays a ``usual'' security game, the outer adversary invokes the inner adversary many times to amplify the winning probability for the security game. We find from our framework that the bit security for decision games can be characterized by the information measure called the R\'enyi divergence of order $1/2$ of the inner adversary. The conventional ``advantage,'' defined as the probability of winning the game, characterizes our bit security for search-type games. We present several security reductions in our framework for justifying our notion of bit security. Many of our results quantitatively match the results for the bit security notion proposed by Micciancio and Walter in 2018. In this sense, our bit security strengthens the previous notion of bit security by adding an operational meaning. A difference from their work is that, in our framework, the Goldreich-Levin theorem gives an optimal reduction only for ``balanced'' adversaries who output binary values in a balanced manner.

In the shuffle model for differential privacy, users locally randomize their data and then submit the results to a trusted ``shuffler'' who mixes the responses before sending them to a server for analysis. This is a promising model for real-world applications of differential privacy, as a series of recent results have shown that, in some cases, the shuffle model offers a strictly better privacy/utility tradeoff than what is possible in a purely local model. The recent ``privacy blanket'' notion provides a simple method for analyzing differentially private protocols in the shuffle model.

A downside of the shuffle model is its reliance on a trusted shuffling mechanism, and it is natural to try to replace this with a distributed shuffling protocol run by the users themselves. Unfortunately, with only one exception, existing fully secure shuffling protocols require $\Omega(n^2)$ communication. In this work, we put forth a notion of differential obliviousness for shuffling protocols, and prove that this notion provides the necessary guarantees for the privacy blanket, without requiring a trusted shuffler. We also show a differentially oblivious shuffling protocol based on onion routing that can tolerate any constant fraction of corrupted users and requires only $O(n \log n)$ communication.

Anonymous message delivery systems, such as private messaging services and privacy-preserving payment systems, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.

We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding (unlike in prior schemes), and are post-quantum secure.

Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using a bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers' cost is a couple of USD per million messages scanned, and the resulting digests can be decoded by recipients in under 20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.

Let $As = b + e \bmod q$ be an LWE-instance with ternary keys $s,e \in \{0, \pm 1\}^n$. Let $s$ be taken from a search space of size $\mathcal{S}$. A standard Meet-in-the-Middle attack recovers $s$ in time $\mathcal{S}^{0.5}$. Using the representation technique, a recent improvement of May shows that this can be lowered to approximately $\mathcal{S}^{0.25}$ by guessing a sub-linear number of $\Theta(\frac{n}{\log n})$ coordinates from $e$. While guessing such an amount of $e$ can asymptotically be neglected, for concrete instantiations of e.g. NTRU, BLISS or GLP the additional cost of guessing leads to complexities around $\mathcal{S}^{0.3}$.

We introduce a locality sensitive hashing (LSH) technique based on Odlyzko's work that avoids any guessing of $e$'s coordinates. This LSH technique involves a comparably small cost such that we can significantly improve on previous results, pushing complexities towards the asymptotic bound $\mathcal{S}^{0.25}$. Concretely, using LSH we lower the MitM complexity estimates for the currently suggested NTRU and NTRU Prime instantiations by a factor in the range $2^{20}-2^{49}$, and for BLISS and GLP parameters by a factor in the range $2^{18}-2^{41}$.

Vector commitment (VC) schemes allow one to commit concisely to an ordered sequence of values, so that the values at desired positions can later be proved concisely. In addition, a VC can be statelessly updatable, meaning that commitments and proofs can be updated to reflect changes to individual entries, using knowledge of just those changes (and not the entire vector). VCs have found important applications in verifiable outsourced databases, cryptographic accumulators, and cryptocurrencies. However, to date there have been relatively few post-quantum constructions, i.e., ones that are plausibly secure against quantum attacks.

More generally, functional commitment (FC) schemes allow one to concisely and verifiably reveal various functions of committed data, such as linear functions (i.e., inner products, including evaluations of a committed polynomial). Under falsifiable assumptions, all known functional commitments schemes have been limited to ``linearizable'' functions, and there are no known post-quantum FC schemes beyond ordinary VCs.

In this work we give post-quantum constructions of vector and functional commitments based on the standard Short Integer Solution lattice problem (appropriately parameterized): \begin{itemize} \item First, we present new statelessly updatable VCs with significantly shorter proofs than (and efficiency otherwise similar to) the only prior post-quantum, statelessly updatable construction (Papamanthou \etal, EUROCRYPT 13). Our constructions use private-key setup, in which an authority generates public parameters and then goes offline.

\item Second, we construct functional commitments for \emph{arbitrary (bounded) Boolean circuits} and branching programs. Under falsifiable assumptions, this is the first post-quantum FC scheme beyond ordinary VCs, and the first FC scheme of any kind that goes beyond linearizable functions. Our construction works in a new model involving an authority that generates the public parameters and remains online to provide public, reusable ``opening keys'' for desired functions of committed messages. \end{itemize}

EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical attackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post-quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.

The deadline for nominating IACR members for the 2021 IACR Fellows class is November 15th.

The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology.

Information about nominating a Fellow is available here.

Public knowledge about the structure of a cryptographic system is a standard assumption in the literature and algorithms are expected to guarantee security in a setting where only the encryption key is kept secret. Nevertheless, undisclosed proprietary cryptographic algorithms still find widespread use in applications both in the civil and military domains. Even though side-channel-based reverse engineering attacks that recover the hidden components of custom cryptosystems have been demonstrated for a wide range of constructions, the complete and practical reverse engineering of AES-128-like ciphers remains unattempted. In this work, we close this gap and propose the first practical reverse engineering of AES-128-like custom ciphers, i.e., algorithms that deploy undisclosed SubBytes, ShiftRows and MixColumns functions. By performing a side-channel-assisted differential power analysis, we show that the amount of traces required to fully recover the undisclosed components are relatively small, hence the possibility of a side-channel attack remains as a practical threat. The results apply to both 8-bit and 32-bit architectures and were validated on two common microcontroller platforms.

Significantly extending the framework of (Couteau and Hartmann, Crypto 2020), we propose a general methodology to construct NIZKs for showing that an encrypted vector $\vec{\chi}$ belongs to an algebraic set, i.e., is in the zero locus of an ideal $\mathscr{I}$ of a polynomial ring. In the case where $\mathscr{I}$ is principal, i.e., generated by a single polynomial $F$, we first construct a matrix that is a ``quasideterminantal representation'' of $F$ and then a NIZK argument to show that $F (\vec{\chi}) = 0$. This leads to compact NIZKs for general computational structures, such as polynomial-size algebraic branching programs. We extend the framework to the case where $\IDEAL$ is non-principal, obtaining efficient NIZKs for R1CS, arithmetic constraint satisfaction systems, and thus for $\mathsf{NP}$. As an independent result, we explicitly describe the corresponding language of ciphertexts as an algebraic language, with smaller parameters than in previous constructions that were based on the disjunction of algebraic languages. This results in an efficient GL-SPHF for algebraic branching programs.

The security proofs of leakage-resilient MACs based on symmetric building blocks currently rely on idealized assumptions that hardly translate into interpretable guidelines for the cryptographic engineers implementing these schemes. In this paper, we first present a leakage-resilient MAC that is both efficient and secure under standard and easily interpretable black box and physical assumptions. It only requires a collision resistant hash function and a single call per message authentication to a Tweakable Block Cipher ($\mathsf{TBC}$) that is unpredictable with leakage. This construction leverages two design twists: large tweaks for the $\mathsf{TBC}$ and a verification process that checks the inverse $\mathsf{TBC}$ against a constant. It enjoys beyond birthday security bounds. We then discuss the cost of getting rid of these design twists. We show that security can be proven without them as well. Yet, a construction without large tweaks requires stronger (non idealized) assumptions and may incur performance overheads if specialized $\mathsf{TBC}$s with large tweaks can be exploited, and a construction without twisted verification requires even stronger assumptions (still non idealized) and leads to more involved bounds. The combination of these results makes a case for our first pragmatic construction and suggests the design of $\mathsf{TBC}$s with large tweaks and good properties for side-channel countermeasures as an interesting challenge.

Full-Time, Permanent

The Information Security Group (ISG) at Royal Holloway is looking to appoint two excellent permanent members of academic staff to contribute to its research and teaching. The applicant should have a high-quality research profile that fits within the wide range of research undertaken by the ISG. Successful applicants must be able to demonstrate enthusiasm for research as well as teaching and communicating with diverse audiences.

The ISG was founded in 1990 and carries out research and teaching at both undergraduate and postgraduate level, with particularly high numbers of master’s students – we are one of the very few academic departments worldwide devoted solely to Information Security, enabling our staff to focus their teaching in this area. Our MSc in Information Security is one of the oldest programmes in the world, having started in 1992 and has a large alumni network with over 4,000 graduates. We have hosted, and continue to host, a series of Centres for Doctoral Training (CDT) in cyber security, which has enabling us to recruit 10 fully funded and first-rate PhD students every year, contributing to a large and vibrant PhD community.

We are involved in a range of inter/multidisciplinary research activities, spanning technology to psychology and social sciences. Our research strengths have continued to generate significant collaborative opportunities from industry and other leading universities.

We are now recruiting academic members of staff who can complement or strengthen our existing research and teaching in Information Security. We are also interested in candidates with interests in broader multidisciplinary research. The successful candidate must hold a PhD or equivalent, and will have a proven research record. Experience in attracting funding, engaging with industry, or contributing to outreach activities will also be valuable.

Closing date for applications:

Contact: Prof. Chris Mitchell c.mitchell@rhul.ac.uk or Prof. Martin Albrecht martin.albrecht@royalholloway.ac.uk

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0921-369

Decentralized finance (DeFi) refers to interoperable smart contracts running on distributed ledgers offering financial services beyond payments. Recently, there has been an explosion of DeFi applications centered on Ethereum, with close to a hundred billion USD in total assets deposited as of September 2021. These applications provide financial services such as asset management, trading, and lending. The wide adoption of DeFi has raised important concerns, and among them is the key issue of privacy---DeFi applications store account balances in the clear, exposing financial positions to public scrutiny.

In this work, we propose a framework of privacy-preserving and composable DeFi on public-state smart contract platforms. First, we define a cryptographic primitive called a flexible anonymous transaction (FLAX) system with two distinctive features: (1) transactions authenticate additional information known as ``associated data'' and (2) transactions can be applied flexibly via a parameter that is determined at processing time, e.g. during the execution time of smart contracts. Second, we design a privacy-preserving token standard (extending ERC20), which requires read access to the inter-contract call stack and admits composable} usage by other contracts. Third, we demonstrate how the FLAX token standard can realize privacy-preserving variants of the Ethereum DeFi ecosystem of today---we show contract designs for asset pools, decentralized exchanges, and lending, covering the largest DeFi projects to date including Curve, Uniswap, Dai stablecoin, Aave, Compound, and Yearn. Lastly, we provide formal security definitions for FLAX and describe instantiations from existing designs of anonymous payments such as Zerocash, RingCT, Quisquis, and Zether.

The problem of Byzantine Fault Tolerance (BFT) has received a lot of attention in the last 30 years. The seminal work by Fisher, Lynch, and Paterson (FLP) shows that there does not exist a deterministic BFT protocol in complete asynchronous networks against a single failure. In order to address this challenge, researchers have designed randomized BFT protocols in asynchronous networks and deterministic BFT protocols in partial synchronous networks. For both kinds of protocols, a basic assumption is that there is an adversary that controls at most a threshold number of participating nodes and that has a full control of the message delivery order in the network. Due to the popularity of Proof of Stake (PoS) blockchains in recent years, several BFT protocols have been deployed in the large scale of Internet environment. We analyze several popular BFT protocols such as Capser FFG / CBC-FBC for Ethereum 2.0 and GRANDPA for Polkadot. Our analysis shows that the security models for these BFT protocols are slightly different from the models commonly accepted in the academic literature. For example, we show that, if the adversary has a full control of the message delivery order in the underlying network, then none of the BFT protocols for Ethereum blockchain 2.0 and Polkadot blockchain could achieve liveness even in a synchronized network. Though it is not clear whether a practical adversary could {\em actually} control and re-order the underlying message delivery system (at Internet scale) to mount these attacks, it raises an interesting question on security model gaps between academic BFT protocols and deployed BFT protocols in the Internet scale. With these analysis, this paper proposes a Casper CBC-FBC style binary BFT protocol and shows its security in the traditional academic security model with complete asynchronous networks. Finally, we propose a multi-value BFT protocol XP for complete asynchronous networks and show its security in the traditional academic BFT security model.

A new interpretation of linear cryptanalysis is proposed. This 'geometric approach' unifies all common variants of linear cryptanalysis, reveals links between various properties, and suggests additional generalizations. For example, new insights into invariants corresponding to non-real eigenvalues of correlation matrices and a generalization of the link between zero-correlation and integral attacks are obtained. Geometric intuition leads to a fixed-key motivation for the piling-up principle, which is illustrated by explaining and generalizing previous results relating invariants and linear approximations. Rank-one approximations are proposed to analyze cell-oriented ciphers, and used to resolve an open problem posed by Beierle, Canteaut and Leander at FSE 2019. In particular, it is shown how such approximations can be analyzed automatically using Riemannian optimization.

In this work, we study the Time-Lock Encryption (TLE) cryptographic primitive. The concept of TLE involves a party initiating the encryption of a message that one can only decrypt after a certain amount of time has elapsed. Following the Universal Composability (UC) paradigm introduced by Canetti [IEEE FOCS 2001], we formally abstract the concept of TLE into an ideal functionality. In addition, we provide a standalone definition for secure TLE schemes in a game-based style and we devise a hybrid protocol that relies on such a secure TLE scheme. We show that if the underlying TLE scheme satisfies the standalone game-based security definition, then our hybrid protocol UC realises the TLE functionality in the random oracle model. Finally, we present Astrolabous, a TLE construction that satisfies our security definition, leading to the first UC realization of the TLE functionality. Interestingly, it is hard to prove UC secure any of the TLE construction proposed in the literature. The reason behind this difficulty relates to the UC framework itself. Intuitively, to capture semantic security, no information should be leaked regarding the plaintext in the ideal world, thus the ciphertext should not contain any information relating to the message. On the other hand, all ciphertexts will eventually open, resulting in a trivial distinction of the real from the ideal world in the standard model. We overcome this limitation by extending any secure TLE construction adopting the techniques of Nielsen [CRYPTO 2002] in the random oracle model. Specifically, the description of the extended TLE algorithms includes calls to the random oracle, allowing our simulator to equivocate. This extension can be applied to any TLE algorithm that satisfies our standalone game-based security definition, and in particular to Astrolabous.

Existing logic-locking attacks are known to successfully decrypt a functionally correct key of a locked combinational circuit. Extensions of these attacks to real-world Intellectual Properties (IPs, which are sequential circuits) have been demonstrated through the scan-chain by selectively initializing the combinational logic and analyzing the responses. In this paper, we propose SeqL+ to mitigate a broad class of such attacks. The key idea is to lock selective functional-input/scan-output pairs of flip-flops without feedback to cause attackers to decrypt an incorrect key, and to scramble flip-flops with feedback to increase key length without introducing further vulnerabilities. We conduct a formal study of the scan-locking and scan-scrambling problems and demonstrate automating our proposed defense on any given IP. This study reveals the first formulation and complexity analysis of Boolean Satisfiability (SAT)-based attack on scan-scrambling. We formulate the attack as a conjunctive normal form (CNF) using a worst-case O(n^3) reduction in terms of scramble-graph size n, making SAT-based attack applicable and show that scramble equivalence classes are equi-sized and of cardinality 1. In order to defeat SAT-based attack, we propose an iterative swapping-based scan-cell scrambling algorithm that has O(n) implementation time-complexity and O(2^&#8970;(&#945;.n+1)/3&#8971;) SAT-decryption time-complexity in terms of a user-configurable cost constraint &#945; (0 < &#945; &#8804; 1). We empirically validate that SeqL+ hides functionally correct keys from the attacker, thereby increasing the likelihood of the decrypted key being functionally incorrect. When tested on pipelined combinational benchmarks (ISCAS, MCNC), sequential benchmarks (ITC), and a fully-fledged RISC-V CPU, SeqL+ gave 100% resilience to a broad range of state-of-the-art attacks including SAT [1], Double-DIP [2], HackTest [3], SMT [4], FALL [5], Shift-and-Leak [6], Multi-cycle [7], Scan-flushing [8], and Removal [9] attacks.

Blockchain interoperability is essential for the long-envisioned cross-chain decentralized applications. Existing hardware-based approaches demand several Trusted Execution Environments (TEEs) and large storage on the storage-limited TEEs. This paper presents a TEE-based privacy-preserving blockchain interoperability framework, calls as IvyCross, which decreases the requirement of TEE numbers and TEE's storage sizes by enforcing honest behaviors of TEE hosts with economic incentives. Specifically, IvyCross runs privacy-preserving cross-chain smart contracts atop two distributed TEE-powered hosts, and utilizes a sequential game between rational hosts to guarantee the correctness of contracts execution. IvyCross enables arbitrarily complex smart contracts execution across heterogenous blockchains at low costs. We formally prove the security of IvyCross in the Universal Composability framework. We also implement a prototype of IvyCross atop Bitcoin, Ethereum, and FISCO BOCS. The experiments indicate that (i) IvyCross is able to support privacy-preserving and multiple-round smart contracts for cross-chain communication; (ii) IvyCross successfully decreases the off-chain costs on storage and communication of a TEE without using complex cryptographic primitives; and (iii) the on-chain transaction fees in cross-chain communication are relatively low.

The selection of secure parameter sets requires an estimation of the attack cost to break the respective cryptographic scheme instantiated under these parameters. The current NIST standardization process for post-quantum schemes makes this an urgent task, especially considering the announcement to select final candidates by the end of 2021. For code-based schemes, recent estimates seemed to contradict the claimed security of most proposals, leading to a certain doubt about the correctness of those estimates. Furthermore, none of the available estimates include most recent algorithmic improvements on decoding linear codes, which are based on information set decoding (ISD) in combination with nearest neighbor search. In this work we observe that all major ISD improvements are build on nearest neighbor search, explicitly or implicitly. This allows us to derive a framework from which we obtain practical variants of all relevant ISD algorithms including the most recent improvements. We derive formulas for the practical attack costs and make those online available in an easy to use estimator tool written in python and C. Eventually, we provide classical and quantum estimates for the bit security of all parameter sets of current code-based NIST proposals.

A recent work by Shi and Wu (Eurocrypt'21) sugested a new, non-interactive abstraction for anonymous routing, coined Non-Interactive Anonymous Router (\NIAR). They show how to construct a \NIAR scheme with succinct communication from bilinear groups. Unfortunately, the router needs to perform quadratic computation (in the number of senders/receivers) to perform each routing.

In this paper, we show that if one is willing to relax the security notion to $(\epsilon, \delta)$-differential privacy, henceforth also called $(\epsilon, \delta)$-differential anonymity, then, a non-interactive construction exists with subquadratic router computation, also assuming standard hardness assumptions in bilinear groups. Morever, even when $1-1/\poly\log n$ fraction of the senders are corrupt, we can attain strong privacy parameters where $\epsilon = O(1/\poly\log n)$ and $\delta = \negl(n)$.