International Association
for Cryptologic Research

The Computer Science Department at Université libre de Bruxelles is seeking to recruit several teaching assistants. These half teaching / half research PhD positions are for three years, usually renewable for another three years. PhD salaries in Belgium are very competitive.

Teaching assistants will perform high-quality research under the supervision of one professor from the Department in order to obtain a PhD degree. Possible research topics include any area of cryptography, particularly applied, post-quantum and mathematical cryptography. Cryptography researchers affiliated with ULB include Liran Lerman, Olivier Markowitch, Christophe Petit and Gilles Van Assche

Main requirements:
- master degree in computer science or a cognate discipline
- sufficient knowledge of French to teach at undergraduate level

More information here: http://wwwdev.ulb.ac.be/greffe/files/7311.pdf

For informal inquiries, particularly related to post-quantum and mathematical cryptography, please contact Christophe Petit (first name dot last name at ulb dot be)

Closing date for applications:

Contact: Christophe Petit

More information: http://wwwdev.ulb.ac.be/greffe/files/7311.pdf

We examine Multi-Party Computation protocols in the active-security-with-abort setting for $Q_2$ access structures over small and large finite fields $F_p$ and over rings $Z_{p^k}$. We give general protocols which work for any $Q_2$ access structure which is realised by a multiplicative Extended Span Program. We generalize a number of techniques and protocols from various papers and compare the different methodologies. In particular we examine the expected communication cost per multiplication gate when the protocols are instantiated with different access structures.

We investigate *all* NIST PQC Round~3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test of re-encryption in decapsulation is critical.

We survey effective key-recovery attacks if we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two KEM schemes in NTRU Prime, and SIKE. We propose a new key-recovery attack against the other KEM scheme in NTRU Prime. We also report an attack against BIKE that leads to leakage of information of secret keys.

The open-source pqm4 library contains all KEM schemes except Classic McEliece and HQC. We show that giving a single instruction-skipping fault in the decapsulation processes leads to skipping the equality test *virtually* for Kyber, NTRU, Saber, BIKE, and SIKE. We also report the experimental attacks against them. We also report the implementation of NTRU Prime allows chosen-ciphertext attacks freely and the timing side-channel of FrodoKEM reported in Guo, Johansson, and Nilsson (CRYPTO 2020) remains.

From June 2019 to March 2020, IETF conducted a selection process to choose password authenticated key exchange (PAKE) protocols for standardization. Similar standardization efforts were conducted before by IEEE (P1362.2) and ISO/IEC (11770-4). An important hallmark for this IETF selection process is its openness: anyone can nominate any candidate; all reviews are public; all email discussions on the IETF mailing lists are archived and publicly readable. However, despite the openness, it is unclear whether this IETF selection process has presented a successful model. Several important questions that were raised during the selection process had remained unaddressed even after the two winners (CPace and OPAQUE) were announced. We reflect on the IETF PAKE selection process as a case study, and summarize lessons in a set of principles with the hope to improve security standardization in the future.

Well-known authentication mechanisms such as Public-key Infrastructure (PKI) and Identity-based Public-key Certificates (ID-PKC) are not suitable to integrate with the peer-to-peer (P2P) network environment. The reason is the difficulty in maintaining a centralized authority to manage the certificates. The authentication becomes even harder in an anonymous environment. We present three authentication protocols such that the users can authenticate themselves in an anonymous P2P network, without revealing their identities. Firstly, we propose a way to use existing ring signature schemes to obtain anonymous authentication. Secondly, we propose an anonymous authentication scheme utilizing secret sharing schemes. Finally, we propose a zero-knowledge-based anonymous authentication protocol. We provide security justifications of the three protocols in terms of anonymity, completeness, soundness, resilience to impersonation attacks, and resilience to replay attacks.

One of the finalists in the NIST post-quantum cryptography competition is the Classic McEliece cryptosystem. Unfortunately, its public key size represents a practical limitation. One option to address this problem is to use different families of error-correcting codes. Most of such attempts failed as those cryptosystems were proved not secure. In this paper, we propose a McEliece type cryptosystem using high minimum distance self-dual codes and punctured codes derived from them. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. For the 80-bit security case, we construct an optimal self-dual code of length 1\,064, which, as far as we are aware, was not presented before. Compared to the original McEliece cryptosystem, this allows us to reduce the key size by about 38.5\%.

General-purpose zero-knowledge proofs for all \textsf{NP} languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains black-box calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only black-box access to the function. Rosulek (Crypto'12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access.

We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function $f$, we seek to construct a \textit{new} one-way function $F$ given only black-box access to $f$, \textit{and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a \textit{proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions.

We show how to construct proof-based versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically,

- We first show that if the prover entirely chooses the input, then proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary.

- We next present black-box constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used Goldreich-Levin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input.

Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.

Secure Multiparty Computation (MPC) is an invaluable tool for training machinelearning models when the training data cannot be directly accessed by the modeltrainer. Unfortunately, complex algorithms, such as deep learning models, havetheir computational complexities increased by orders of magnitude when performedusing MPC protocols. In this contribution, we study how to efficiently train animportant class of machine learning problems by using MPC where features areknown by one of the computing parties and only the labels are private. We proposenew protocols combining differential privacy (DP) and MPC in order to privatelyand efficiently train a deep learning model in such scenario. More specifically, werelease differentially private information during the MPC computation to dramat-ically reduce the training time. All released information idoes not compromisethe privacy of the labels at the individual level. Our protocols can have runningtimes that are orders of magnitude better than a straightforward use of MPC at amoderate cost in model accuracy.

The best known $n$ party unconditional multiparty computation protocols with an optimal corruption threshold communicates $O(n)$ field elements per gate. This has been the case even in the semi-honest setting despite over a decade of research on communication complexity in this setting. Going to the slightly sub-optimal corruption setting, the work of Damgard, Ishai, and Kroigaard (EUROCRYPT 2010) provided the first protocol for a single circuit achieving communication complexity of $O(\log|C|)$ elements per gate. While a number of works have improved upon this result, obtaining a protocol with $O(1)$ field elements per gate has been an open problem.

In this work, we construct the first unconditional multi-party computation protocol evaluating a single arithmetic circuit with amortized communication complexity of $O(1)$ elements per gate.

In this work, we address communication, computation, and round efficiency of unconditionally secure multi-party computation for arithmetic circuits in the honest majority setting. We achieve both algorithmic and practical improvements:

-- The best known result in the semi-honest setting has been due to Damgard and Nielsen (CRYPTO 2007). Over the last decade, their construction has played an important role in the progress of efficient secure computation. However despite a number of follow-up works, any significant improvements to the basic semi-honest protocol have been hard to come by. We show 33% improvement in communication complexity of this protocol. We show how to generalize this result to the malicious setting, leading to the best known unconditional honest majority MPC with malicious security. -- We focus on the round complexity of the Damgard and Nielsen protocol and improve it by a factor of 2. Our improvement relies on a novel observation relating to an interplay between Damgard and Nielsen multiplication and Beaver triple multiplication. An implementation of our constructions shows an execution run time improvement compared to the state of the art ranging from 30% to 50%.

For decades signature verification has been regarded as a unique, monolithic process. Here, we want to look at it with fresh eyes and pose two fundamental questions: (1) is it possible to extract meaningful information from a partial signature verification? (flexibility); and (2) is it possible to speed up the verification process without impacting unforgeability? (efficiency). We answer both questions in a positive way for specific classes of post-quantum secure schemes.

In detail, we develop formal frameworks for signatures with efficient verification, flexible verification and combinations of the two. Crucially, we regard these as features that may enhance existing constructions. Flexibility is of particular interest as standard verification cannot provide any meaningful information about the validity of a given signature if interrupted in media res. We exhibit generic transformations to realize efficient (and) flexible verification for schemes that involve matrix-vector multiplications among the verification checks. In addition, we present concrete instantiations of efficient (and) flexible verification for Rainbow [ACNS05] (as representative of schemes based on multivariate quadratic equations), MP [EC12] and GVW [STOC15] (as representative of lattice-based constructions). Interestingly, we are able to efficiently verify Rainbow signatures using 50% of the original computational cost, and as little as 0.4% for GVW homomorphic signatures, provided a one-time preprocessing and with only negligible impact on security.

We consider a distributed function computation problem in which parties observing noisy versions of a remote source facilitate the computation of a function of their observations at a fusion center through public communication. The distributed function computation is subject to constraints, including not only reliability and storage but also secrecy and privacy. Specifically, 1) the function computed should remain secret from an eavesdropper observing the public communication and correlated observations, measured in terms of the information leaked about the arguments of the function, to ensure secrecy regardless of the exact function used; 2) the remote source should remain private from the eavesdropper and the fusion center, measured in terms of the information leaked about the remote source itself. We derive the exact rate regions for lossless and lossy single-function computation and illustrate the lossy single-function computation rate region for an information bottleneck example, in which the optimal auxiliary random variables are characterized for binary-input symmetric-output channels. We extend the approach to lossless and lossy asynchronous multiple-function computations with joint secrecy and privacy constraints, in which case inner and outer bounds for the rate regions that differ only in the Markov chain conditions imposed are characterized.

To compensate for the poor reliability of Physical Unclonable Function (PUF) primitives, some low complexity solutions not requiring error-correcting codes (ECC) have been proposed. One simple method is to discard less reliable bits, which are indicated in the helper data stored inside the PUF. To avoid discarding bits, the Two-metric Helper Data (TMH) method, which particularly applies to oscillation-based PUFs, allows to keep all bits by using different metrics when deriving the PUF response. However, oscillation-based PUFs are sensitive to side-channel analysis (SCA) since the frequencies of the oscillations can be observed by current or electromagnetic measurements. This paper studies the security of PUFs using TMH in order to obtain both reliable and robust PUF responses. We show that PUFs using TMH are sensitive to SCA, but can be greatly improved by using temporal masking and adapted extraction metrics. In case of public helper data, an efficient protection requires the randomization of the measurement order. We study two different solutions, providing interesting insights into trade-offs between security and complexity.

In their Eurocrypt 2021 paper, Beierle et al. showed that the proprietary stream ciphers GEA-1 and GEA-2, widely used for GPRS encryption in the late 1990s and during the 2000s, are cryptographically weak and presented attacks on both algorithms with practical time complexity. Although GEA-1 and GEA-2 are classical stream ciphers, the attack on GEA-1 is interesting from a cryptanalytic point of view. As outlined in the aforementioned paper, there is a strong indication that the security of GEA-1 was deliberately weakened to 40 bits in order to fulfill European export restrictions. In this paper we analyze the design further and answer the open question on how to construct a GEA-1-like cipher with such a reduced security. Indeed, the actual GEA-1 instance could be obtained from this construction. Our observations and analysis yields new theoretical insights in designing secure stream ciphers.

Pilsung is an AES-based North Korean cipher, which uses key-dependent S-Boxes and permutation. The use of pseudo-random ShiftRows permutations gives rise to a potential for weak keys. In this work we show how to build distinguishers to such weak keys and how to effectively search for them. We conclude that no such class of weak keys exist.

Masking and desynchronization of power traces are two widely used countermeasures against power attacks. Higher-order power attacks are used to break cryptographic implementations protected by masking countermeasures. However, they require to capture long-distance dependency, the dependencies among distant Points-of-Interest (PoIs) along the time axis, which together contribute to the information leakage. Desynchronization of power traces provides resistance against power attacks by randomly shifting the individual traces, thus, making the PoIs misaligned for different traces. Consequently, a successful attack against desynchronized traces requires to be invariant to the random shifts of the power traces. A successful attack against cryptographic implementations protected by both masking and desynchronization countermeasures requires to be both shift-invariant and capable of capturing long-distance dependency. Recently, Transformer Network (TN) has been introduced in natural language processing literature. TN is better than both Convolutional Neural Network (CNN) and Recurrent Neural Network (RNN) at capturing long-distance dependency, and thus, a natural choice against masking countermeasures. Furthermore, a TN can be made shift-invariant making it robust to desynchronization of traces as well. In this work, we introduce a TN-based model, namely TransNet, for power attacks. Our experiments show that the proposed TransNet model successfully attacks implementation protected by both masking and desynchronization even when it is trained on only synchronized traces. Particularly, it can bring down the mean key rank below 1 using only 400 power traces if evaluated on highly desynchronized ASCAD_desync100 dataset even when it is trained on ASCAD dataset which has no trace desynchronization. Moreover, if compared to other state-of-the-art deep learning models, our proposed model performs significantly better when the attack traces are highly desynchronized.

Event date: 6 January to 8 January 2022
Submission deadline: 30 September 2021
Notification: 15 December 2021

Event date: 20 June to 23 June 2022
Submission deadline: 3 September 2021
Notification: 5 January 2021

A fully-funded PhD scholarship is available at the Cryptography and Security Group (https://cs.au.dk/research/cryptography-and-security/) at Aarhus University.

Project description. The PhD candidate will develop new algorithms and implementation techniques to accelerate public-key cryptography in both the classical and postquantum settings. The project includes designing arithmetic algorithms that are friendlier to parallelization, more precise complexity analysis of existing techniques, and aspects of formal verification to ensure correctness and real-world implementation security.

The PhD candidate will also be involved in other educational activities, such as serving as teaching assistant in courses related to his/her expertise.

Qualifications. We are looking for dedicated and enthusiastic applicants, preferably with a Master’s degree in Computer Science/Engineering, Mathematics or related discipline. A BSc. degree with demonstrated research experience is also welcome. A background in cryptography or formal verification is required. Practical experience with software development will be seen as a plus. Further requirements are fluency in English, good reporting/organization skills and being able to work independently.

Application process: You can apply online at https://phd.nat.au.dk/for-applicants/apply-here >Choose August 2021 Call with deadline 1 August 2021 at noon (11.59 AM CEST) and the corresponding project.

Closing date for applications:

Contact: Contact: Diego F. Aranha, Associate Professor of Computer Science, dfaranha (at) cs.au.dk

More information: https://phd.nat.au.dk/for-applicants/apply-here/

The University of Luxembourg aspires to be one of Europe’s most highly regarded universities with a distinctly international and interdisciplinary character. It fosters the cross-fertilisation of research and teaching, is relevant to its country, is known worldwide for its research and teaching in targeted areas, and is establishing itself as an innovative model for contemporary European Higher Education. The Faculty of Science, Technology and Medicine (FSTM) contributes multidisciplinary expertise in the fields of Mathematics, Physics, Engineering, Computer Science, Life Sciences and Medicine. Through its dual mission of teaching and research, the FSTM seeks to generate and disseminate knowledge and train new generations of responsible citizens, in order to better understand, explain and advance society and environment we live in. Your Role... Cryptolux is a team of cryptographers and security researchers interested in applied cryptography, cryptanalysis, privacy, network security, cryptographic blockchains and is led by Prof. Alex Biryukov, we are affiliated to the Departement of Computer Science (DCS) and to the Security and Trust center (SnT). You will perform the following tasks: Prepare a doctoral thesis in Cryptography and IT Security Publish research papers and give talks at the top international venues Provide guidance to MSc students and TA for classes, depending on the needs of the team Organize science outreach activities, e.g. science for kids, … Area / Potential topics of the thesis Cryptanalysis and design of cryptographic primitives Lightweight block ciphers, hash functions, authenticated encryption schemes Financial Cryptography (security of distributed ledgers, smart contracts) Privacy Enhancing Technology (Tor-like networks, privacy for cryptocurrencies, blockchains) Design of proofs of work, resource-hard functions, commitment schemes Side-channel attacks and countermeasures White-box cryptography What we expect from you. MSc. degree in Computer Science, Applied Mathematics, Electrical Engineering with outstanding grades (GPA > 85%) Strong mathematical and/or algorithmic CS background (Olympiads, CTFs a plus) Backg

Closing date for applications:

Contact: Alex Biryukov (alex.biryukov@uni.lu)

More information: http://emea3.mrted.ly/2qpcj