International Association
for Cryptologic Research

The application security and cryptography group at the Lucerne School of Information Technology has the following open research positions:

Senior Research Associate Cryptography and Quantum Information (https://recruitingapp-2678.umantis.com/Vacancies/2466/Description/1)

Senior Research Associate Security Software Engineer (https://recruitingapp-2678.umantis.com/Vacancies/2465/Description/1)

Doctoral Position in Cryptography & Quantum Information (https://recruitingapp-2678.umantis.com/Vacancies/2467/Description/1)
Candidates should have a strong background in IT security and cryptography and/or good software engineering skills; knowledge in quantum information is advantageous. Both junior and more senior candidates are considered. For junior candidates, there exists the possibility to combine the employment with enrollment in a study-programm towards a PhD or a Master of Science in Engineering (MSE).

Closing date for applications:

Contact: Please apply online via the links provided above. For any further Information contact Prof. Dr. Esther Hänggi, esther.haenggi@hslu.ch

More information: https://recruitingapp-2678.umantis.com/Vacancies/2466/Description/1

The Department of Computer Science within the Faculty of Engineering and Physical Sciences has an international reputation for research and teaching. Research in the department is focused on three main areas - Nature Inspired Computing and Engineering (NICE), Distributed and Networked Systems, and Secure Systems, with Surrey hosting UK Academic Centres of Excellence both in Research and in Education, both recognised by GCHQ.

This post offers an exciting opportunity for an appointment in the Secure Systems group. Suitable areas of expertise that complement and extend strengths of the group include (but are not limited to): software security, program analysis, formal verification of software/systems, practical system security, trusted systems, distributed systems, complex systems and networks, as well as the interface between security and machine learning.

Candidates to the post should have a PhD in a relevant subject or equivalent professional experience. An ability to secure research funding and produce high quality outputs and manage research projects and supervise research students is also required. It is expected that the post-holder will also contribute to high quality teaching in cyber security and fundamental topics in computer science at undergraduate and post-graduate level and to supervise undergraduate projects and dissertations.

The University and the Department specifically are committed to building a culturally diverse organisation and strongly encourages applications from female and minority candidates. The Department of Computer Science was awarded a Bronze Athena SWAN award, in recognition of our commitment to equality and diversity.

The University of Surrey is committed to providing an inclusive environment that offers equal opportunities for all. We place great value on diversity and are seeking to increase the diversity within our community. Therefore, we particularly encourage applications from under-represented groups, such as people from Black, Asian and minority ethnic groups and people with disabilities.

Closing date for applications:

Contact: Professor Steve Schneider

s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=045822

Recent works have made exciting progress on the construction of round optimal, *two-round*, Multi-Party Computation (MPC) protocols. However, most proposals so far are still complex and inefficient.

In this work, we improve the simplicity and efficiency of two-round MPC in the setting with dishonest majority and malicious security. Our protocols make use of the Random Oracle (RO) and a generalization of the Oblivious Linear Evaluation (OLE) correlated randomness, called tensor OLE, over a finite field $\mathbb{F}$, and achieve the following:

- MPC for Boolean Circuits: Our two-round, maliciously secure MPC protocols for computing Boolean circuits, has overall (asymptotic) computational cost $O(S\cdot n^3 \cdot \log |\mathbb{F}|)$, where $S$ is the size of the circuit computed, $n$ the number of parties, and $\mathbb{F}$ a field of characteristic two. The protocols also make black-box calls to a Pseudo-Random Function (PRF).

- MPC for Arithmetic Branching Programs (ABPs): Our two-round, information theoretically and maliciously secure protocols for computing ABPs over a general field $\mathbb{F}$ has overall computational cost $O(S^{1.5}\cdot n^3\cdot \log |\mathbb{F}|)$, where $S$ is the size of ABP computed.

Both protocols achieve security levels inverse proportional to the size of the field $|\mathbb{F}|$.

Our construction is built upon the simple two-round MPC protocols of [Lin-Liu-Wee TCC'20], which are only semi-honest secure. Our main technical contribution lies in ensuring malicious security using simple and lightweight checks, which incur only a constant overhead over the complexity of the protocols by Lin, Liu, and Wee. In particular, in the case of computing Boolean circuits, our malicious MPC protocols have the same complexity (up to a constant overhead) as (insecurely) computing Yao's garbled circuits in a distributed fashion.

Finally, as an additional contribution, we show how to efficiently generate tensor OLE correlation in fields of characteristic two using OT.

It can be tricky to trust elliptic curves standardized in a non-transparent way. To rectify this, we propose a systematic methodology for analyzing curves and statistically comparing them to the expected values of a large number of generic curves with the aim of identifying any deviations in the standard curves.

For this purpose, we put together the largest publicly available database of standard curves. To identify unexpected properties of standard generation methods and curves, we simulate over 250 000 curves by mimicking the generation process of four standards. We compute 22 different properties of curves and analyze them with automated methods to pinpoint deviations in standard curves, pointing to possible weaknesses.

Coin mixing services allow users to mix their cryptocurrency coins and thus enable unlinkable payments in a way that prevents tracking of honest users' coins by both the service provider and the users themselves. The easy bootstrapping of new users and backwards compatibility with cryptocurrencies (such as Bitcoin) with limited support for scripts are attractive features of this architecture, which has recently gained considerable attention in both academia and industry.

A recent work of Tairi et al. [IEEE S&P 2021] formalizes the notion of a coin mixing service and proposes A$^{2}$L, a new cryptographic protocol that simultaneously achieves high efficiency and interoperability. In this work, we identify a gap in their formal model and substantiate the issue by showing two concrete counterexamples: we show how to construct two encryption schemes that satisfy their definitions but lead to a completely insecure system.

To amend this situation, we investigate secure constructions of coin mixing services. First, we develop the notion of blind conditional signatures (BCS), which acts as the cryptographic core for coin mixing services. We propose game-based security definitions for BCS and propose A$^{2}$L$^{+}$, a modified version of the protocol by Tairi et al. that satisfies our security definitions. Our analysis is in an idealized model (akin to the algebraic group model) and assumes the hardness of the one-more discrete logarithm problem. Finally, we propose A$^{2}$L$^\text{UC}$, another construction of BCS that achieves the stronger notion of UC-security (in the standard model), albeit with a significant increase in computation cost. This suggests that constructing a coin mixing service protocol secure under composition requires more complex cryptographic machinery than initially thought.

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.

This paper presents a side-channel analysis (SCA) on key encapsulation mechanisms (KEMs) based on the Fujisaki–Okamoto (FO) transformation and its variants. Many post-quantum KEMs usually perform re-encryption during key decapsulation to achieve CCA security. It has been shown that the side-channel leakage of re-encryption can be exploited for mounting a key-recovery plaintext-checking attack (KR-PCA), even if the CPA secure decryption constructing the KEM is securely implemented. In this paper, we propose an efficient side-channel-assisted KR-PCA on post-quantum KEMs, which achieves a key recovery with significantly fewer attack traces than the existing one. The basic ideas of the proposed attack are to present a new KR-PCA based on a multiple-valued (MV-)PC oracle and to utilize a dedicated multi-classification neural network (NN) to implement an MV-PC oracle. This paper also presents how to realize a sufficiently reliable MV-PC oracle from not completely accurate NN model outputs, and analyzes the tradeoff between the key recovery success rate and the number of attack traces, with its application to NIST PQC selected algorithm Kyber and similar lattice-based Saber, FrodoKEM and NTRU Prime, as well as SIKE, a candidate for the fourth round. Furthermore, the feasibility of the proposed attack is assessed through attack experiments on three typical PRF implementations (i.e., SHAKE, SHA3, and AES software). In consequence, we confirm that the proposed attack reduces the number of attack traces required for a reliable key recovery by up to 87% compared to the existing attacks against Kyber and other lattice-based KEMs under the condition of 99.9999% success rate for key recovery. We also confirm that the proposed attack can reduce the number of attack traces by 85% for SIKE.

Private function evaluation (PFE) is a special type of MPC protocols that, in addition to the input privacy, can preserve the function privacy. In this work, we propose a PFE scheme for RAM. In particular, we first design an efficient 4-server distributed ORAM scheme with amortized communication $O(\log n)$ per access (both reading and writing). We then simulate a RISC RAM machine over the MPC platform, hiding (i) the memory access pattern, (ii) the machine state (including registers, program counter, condition flag, etc.), and (iii) the executed instructions. Our scheme can naturally support a simplified TinyRAM instruction set; if a public RAM program $P$ with given inputs $x$ needs to execute $z$ instruction cycles, our PFE scheme is able to securely evaluate $P(x)$ on private $P$ and $x$ within $5z+1$ online rounds. We prototype and benchmark our system for set intersection, binary search, quicksort, and heapsort algorithms. For instance, to obliviously perform the binary search algorithm on a $2^{10}$ array takes $5.81s$ with function privacy.

This note presents some techniques to slightly reduce the size of EdDSA and ECDSA signatures without lowering their security or breaking compatibility with existing signers, at the cost of an increase in signature verification time; verifying a 64-byte Ed25519 signature truncated to 60 bytes has an average cost of 4.1 million cycles on 64-bit x86 (i.e. about 35 times the cost of verifying a normal, untruncated signature).

In this paper, we formalize the plaintext-awareness notion in the superposition access model in which a quantum adversary may implement the encryption oracle in a quantum device and make superposition queries to the decryption oracle. Due to various possible ways an adversary can access the decryption oracles, we present six security definitions to capture the plaintext-awareness notion with respect to each way of access. We study the relationships between these definitions and present various implications and non-implications. Classically, the strongest plaintext-awareness notion (PA2) accompanied by the indistinguishability under chosen-plaintext attack (IND-CPA) notion yields the indistinguishability under chosen-ciphertext attack (INDCCA) notion. We show that the PA2 notion is not sufficient to show the above relation when targeting the IND-qCCA notion (Boneh-Zhandry definition, Crypto 2013). However, our proposed post-quantum PA2 notion with superposition decryption queries fulfils this implication.

Decision trees are among the most widespread machine learning model used for data classification, in particular due to their interpretability that makes it easy to explain their prediction. In this paper, we propose a novel solution for the private classification of a client request in a non-interactive manner. In contrast to existing solutions to this problem, which are either interactive or require evaluating all the branches of the decision tree, our approach only evaluates a single branch of the tree. Our protocol is based on two primitives that we also introduce in this paper and that maybe of independent interest : Blind Node Selection and Blind Array Access. Those contributions are based on recent advances in homomorphic cryptography, such as the functional bootstrapping mechanism recently proposed for the Fully Homomorphic Encryption over the Torus scheme TFHE. Our private decision tree evaluation algorithm is highly efficient as it requires only one round of communication and d comparisons, with d being the depth of the tree, while other state-of-the-art non-interactive protocols need 2^d comparisons.

Currently deployed public-key cryptosystems will be vulnerable to attacks by full- scale quantum computers. Consequently, quantum resistant cryptosystems are in high demand, and lattice-based cryptosystems, based on a hard problem known as Learning With Errors (LWE), have emerged as strong contenders for standardization. In this work, we train transformers to perform modular arithmetic and combine half-trained models with statistical cryptanalysis techniques to propose SALSA: a machine learning attack on LWE-based cryptographic schemes. SALSA can fully recover secrets for small-to-mid size LWE instances with sparse binary secrets, and may scale to attack real-world LWE-based cryptosystems.

Secure multiparty computation (MPC) models scenarios, where a set of mutually distrusting parties wish to compute some task over their private inputs. Assuming that the majority of the parties are honest and that the parties have access to a broadcast channel, every function can be computed with full security. Conversely, if either an honest majority or a broadcast channel cannot be assumed (as is the case in various real-world settings), then there are functionalities that cannot be computed with full security. Understanding the exact power of each of these assumptions is a valuable goal. In this paper, we study full security for solitary output functionalities (where only a single party receives an output). We focus on three-party functionalities in the point-to-point model (without broadcast), assuming an honest majority. We develop new techniques for analyzing the security of MPC protocols in the point-to-point model. Using these techniques, we are able to give a characterization for several interesting classes of solitary output three-party functionalities (including Boolean and ternary-output functionalities over a polynomial-size domain) that are computable with full security in the setting of an honest majority without a broadcast channel. Furthermore, using our techniques, we make progress in understanding the set of solitary output three-party functionalities that can be computed with full security, assuming broadcast but no honest majority. Specifically, we extend the set of such functionalities that are known to be computable, due to Halevi et al. [TCC ’19].

We implement training of neural networks in secure multi-party computation (MPC) using quantization commonly used in said setting. We are the first to present an MNIST classifier purely trained in MPC that comes within 0.2 percent of the accuracy of the same convolutional neural network trained via plaintext computation. More concretely, we have trained a network with two convolutional and two dense layers to 99.2% accuracy in 3.5 hours (under one hour for 99% accuracy). We have also implemented AlexNet for CIFAR-10, which converges in a few hours. We develop novel protocols for exponentiation and inverse square root. Finally, we present experiments in a range of MPC security models for up to ten parties, both with honest and dishonest majority as well as semi-honest and malicious security.

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners. Proof-of-Stake chains are energy-efficient, have fast finality and some accountability, but face several security issues: susceptibility to non-slashable long-range safety attacks, non-accountable transaction censorship and stalling attacks and difficulty to bootstrap PoS chains from low token valuation. We show these security issues are inherent in any PoS chain without an external trusted source, and propose a new protocol Babylon, where an off-the-shelf PoS protocol uses Bitcoin as an external source of trust to resolve these issues. An impossibility result justifies the optimality of Babylon. Our results shed light on the general question of how much security a PoS chain can derive from an external trusted chain by only making succinct commitments to the trusted chain.

In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. Binary PC oracle-based side-channel attacks are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery, as they only recover a single bit of information per trace. We propose novel parallel PC oracle based side-channel attacks, which are capable of recovering an arbitrary P number of bits of information about the secret key in a single trace. We experimentally validated our attacks on the fastest implementation of unprotected Kyber KEM in the pqm4 library on the ARM Cortex-M4 microcontroller. Our experiments yielded improvements in the range of 2.89x and 7.65x in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of our attack. Finally, we also conduct a thorough study of the capability of our attack in different attack scenarios, based on the presence/absence of a clone device, and also partial key recovery. We also show that our proposed attacks are able to achieve the lowest number of queries for key recovery, even over implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking.

We propose NTT implementations with each supporting at least one parameter of NTRU and one parameter of NTRU Prime. Our implementations are based on size-1440, size-1536, and size-1728 convolutions without algebraic assumptions on the target polynomial rings. We also propose several improvements for the NTT computation. Firstly, we introduce dedicated radix-(2,3) butterflies combining Good–Thomas FFT and vector-radix FFT. In general, there are six dedicated radix-(2, 3) butterflies and they together support implicit permutations. Secondly, for odd prime radices, we show that the multiplications for one output can be replaced with additions/subtractions. We demonstrate the idea for radix-3 and show how to extend it to any odd prime. Our improvement also applies to radix-(2, 3) butterflies. Thirdly, we implement an incomplete version of Good–Thomas FFT for addressing potential code size issues. For NTRU, our polynomial multiplications outperform the state-of-the-art by 2.8%−10.3%. For NTRU Prime, our polynomial multiplications are slower than the state-of-the-art. However, the SotA exploits the specific structure of coefficient rings or polynomial moduli, while our NTT-based multiplications exploit neither and apply across different schemes. This reduces the engineering effort, including testing and verification.

In this paper we show that PSPACE is equal to 4th level in the polynomial hierarchy. We also deduce a lot of important consequences. True quantified Boolean formula is indeed generalisation of the Boolean Satisfiability Problem, where determining of interpretation that satisfies a given Boolean formula is replaced by existence of Boolean functions that makes a given QBF to be tautology. Such functions are called the Skolem functions. The essential idea of the proof is to show that for any (fully) quantified Boolean formula ϕ we can obtain a formula ϕ′ which is in the forth level of the polynomial hierarchy, no more than polynomial in the size of a given ϕ, such that the truth of ϕ can be determined from the truth of ϕ′. The idea is to skolemize, and then use additional formulas from the second level of the polynomial hierarchy inside the skolemized prefix to enforce that the skolem variables indeed depend only on the universally quantified variables they are supposed to. However, some dependence is lost when the quantification is reversed. It is called "XOR issue" in the paper because the functional dependence can be expressed by means of an XOR formula. Thus, it is needed to locate these XORs. The last can be done locally for each leaf/ branch/ iteration (keep in mind the algebraic normal form (ANF)), i.e. in polynomial time, since all arguments are specified.

In this paper, we investigate the possibility of performing Gaussian elimination for arbitrary binary matrices on hardware. In particular, we presented a generic approach for hardware-based Gaussian elimination, which is able to process both non-singular and singular matrices. Previous works on hardware-based Gaussian elimination can only process non-singular ones. However, a plethora of cryptosystems, for instance, quantum-safe key encapsulation mechanisms based on rank-metric codes, ROLLO and RQC, which are among NIST post-quantum cryptography standardization round-2 candidates, require performing Gaussian elimination for random matrices regardless of the singularity. We accordingly implemented an optimized and parameterized Gaussian eliminator for (singular) matrices over binary fields, making the intense computation of linear algebra feasible and efficient on hardware. To the best of our knowledge, this work solves for the first time eliminating a singular matrix on reconfigurable hardware and also describes the a generic hardware architecture for rank-code based cryptographic schemes. The experimental results suggest hardware-based Gaussian elimination can be done in linear time regardless of the matrix type.

Side-Channel Analysis (SCA) allows extracting secret keys manipulated by cryptographic primitives through leakages of their physical implementations. Supervised attacks, known to be optimal, can theoretically defeat any counter-measure, including masking, by learning the dependency between the leakage and the secret through the profiling phase. However, defeating masking is less trivial when it comes to unsupervised attacks. While classical strategies such as CPA or LRA have been extended to masked implementations, we show that these extensions only hold for Boolean and arithmetic schemes. Therefore, we propose a new unsupervised strategy, the Joint Moments Regression (JMR), able to defeat any masking schemes (multiplicative, affine, polynomial, inner product...), which are gaining popularity in real implementations. The main idea behind JMR is to directly regress the leakage model of the shares by fitting a system based on higher-order joint moments conditions. We show that this idea can be seen as part of a more general framework known as the Generalized Method of Moments (GMM). This offers strong mathematical foundations on which we can rely on to derive optimizations of JMR. Simulation experiments show that our proposal outperforms state-of-the-art attacks, even in the case of Boolean and arithmetic masking. Eventually, we apply this strategy to provide, to the best of our knowledge, the first unsupervised attack (successful in practice) on the protected AES implementation proposed by the ANSSI for SCA research, which embed an affine masking and shuffling counter-measures.