International Association
for Cryptologic Research

The Hybrid Public Key Encryption (HPKE) scheme is an emerging standard currently under consideration by the Crypto Forum Research Group (CFRG) of the IETF as a candidate for formal approval. Of the four modes of HPKE, we analyse the authenticated mode HPKE_Auth in its single-shot encryption form as it contains what is, arguably, the most novel part of HPKE and has applications to other upcoming standards such as MLS.

HPKE_Auth’s intended application domain is captured by a new primitive which we call Authenticated Public Key Encryption (APKE). We provide syntax and security definitions for APKE schemes, as well as for the related Authenticated Key Encapsulation Mechanisms (AKEMs). We prove security of the AKEM scheme DH-AKEM underlying HPKE Auth based on the Gap Diffie-Hellman assumption and provide general AKEM/DEM composition theorems with which to argue about HPKE_Auth’s security. To this end, we also formally analyse HPKE_Auth’s key schedule and key derivation functions. To increase confidence in our results we use the automatic theorem proving tool CryptoVerif. All our bounds are quantitative and we discuss their practical implications for HPKE_Auth.

As an independent contribution we propose the new framework of nominal groups that allows us to capture abstract syntactical and security properties of practical elliptic curves, including the Curve25519 and Curve448 based groups (which do not constitute cyclic groups).

EPID systems are anonymous authentication protocols where a device can be revoked by including one of its signatures in a revocation list. Such protocols are today included in the ISO/IEC 20008-2 standard and are embedded in billions of chips, which make them a flagship of advanced cryptographic tools. Yet, their security analysis is based on a model that suffers from several important limitations, which either questions the security assurances EPID can provide in the real world or prevents such systems from achieving their full impact. The most prominent example is the one of revocation lists. Although they could be managed locally by verifiers, which would be natural in most use-cases, the security model assumes that they are managed by a trusted entity, a requirement that is not easily met in practice and that is thus tempting to ignore, as illustrated in the corresponding standard.

In this paper, we propose to revisit the security model of EPID, by removing some limitations of previous works but mostly by answering the following question: what can we achieve when revocation lists are generated by a malicious entity?

Surprisingly, even in this disadvantageous context, we show that it is possible to retain strong properties that we believe to better capture the spirit of EPID systems. Moreover, we show that we can construct very efficient schemes resisting such powerful adversaries by essentially tweaking previous approaches. In particular, our constructions do not require to perform any significant test on the revocation lists during the signature generation process. These constructions constitute the second contribution of this paper.

Optimization of finite field arithmetic is important for the deployment of public key cryptography, particularly in the context of elliptic curve cryptography. Until now the primary concern has been operations over the prime field $\F_p$, where $p$ is a prime. With the advent of pairing-based cryptography there arises a need to also look at optimal arithmetic over extension fields $\F_{p^n}$ for small values of $n$. Here we focus on the determination of quadratic residuosity and the calculation of inverses and square roots over these fields, operations often carried out in conjunction with one another. We demonstrate with a minor improvement in a hash-to-curve algorithm, and a major speed-up in the calculation of square roots in quadratic extensions.

We have 3 open positions for PhD students in the area of symmetric cryptography in the Digital Security group at Radboud University in Nijmegen. One position is on the study of provable security of modes of use, one on design of primitives supported by cryptanalysis, and one on protection against implementation attacks based on power, electromagnetic side channel analysis, and fault attacks. We focus hereby on cryptography based on permutations as in the sponge, duplex and farfalle constructions, especially suited for low energy consumption.

The Digital Security Group of Radboud University is one of the leading groups in computer security in the Netherlands and Europe, and one of the pioneers in permutation-based crypto and corresponding leakage-resilient modes.

The successful candidate should ideally have a master in Computer Science, Mathematics, or Electrical Engineering. Applications will be considered until the positions are filled.

To apply, please send the following documents to dis-secr (at) cs.ru.nl, with the subject "PhD position in symmetric crypto":
- a motivation letter
- your cv
- your master diploma certificate (scanned)
- transcript of the courses you took (including grades)
- up to 3 references

Closing date for applications:

Contact: To enquire about the positions you can contact: Joan Daemen, joan (at) cs.ru.nl, Lejla Batina, lejla (at) cs.ru.nl, and Bart Mennink, b.mennink (at) cs.ru.nl

The stipend is open for appointment from April 1, 2021, or soon as possible thereafter.

We seek a PhD in Security in thing-to-cloud IoTalentum (http://www.iotalentum.eu) architectures for IoT ecosystems. The objective of the research is to identify and describe new models mapping, quantifying, forecasting and ensuring adequate levels of privacy and security within the distributed computing centers the IoTalentum cloud-to-thing continuum. To develop and testing of a hardware-free identification tool for computing centers to increase the level of security and privacy of collected data in IoT virtual environments.

The PhD is part of the opening of 15 Early Stage Researchers (ESRs) positions within the IoTalentum project (www.iotalentum.eu). IoTalentum is a European Training Network (ETN) funded by the European Commission under the Horizon 2020 Marie Sklodowska-Curie Action (MSCA). The MSCA ITN programme offers a highly competitive and attractive salary and working conditions.

Eligibility Criteria
The applicants must, at the date of the call deadline, comply with the following eligibility criteria:

• To hold a MSc degree (or equivalent) in Engineering, Mathematics, Physics or a related field.
• To have not been awarded a doctoral degree.
• At the time of recruitment by the host organization, candidates should be in the first four years (full-time equivalent research experience) of their research career.
• Candidates must comply with the European Commission’s mobility rule, meaning at the time of recruitment by the host organization, they must not have resided or carried out their main activity (work, studies, etc.) in the country of the host organization for more than 12 months in the 3 years immediately before the starting employment contract date. Compulsory national service and/or short stays such as holidays are not taken into account. The positions are open to all nationalities.
• To be proficient in English language

Closing date for applications:

Contact: Prof. Knud Erik Skouby (skouby@cmi.aau.dk) and Assoc. Prof. Sokol Kosta (sok@cmi.aau.dk)

More information: https://www.stillinger.aau.dk/vis-stilling/?vacancy=1134091

Multiple positions on all levels at the Ding Lab in Privacy Protection and Blockchain Security at the Beijing Institute of Mathematical Sciences and Applications（BIMSA）

The BIMSA is a Mathematics research institution co-sponsored by Beijing Municipal Government and Tsinghua University. The BIMSA is located in the Huairou District of Beijing, and is part of Beijing’s strategic plans to build world-class new-style research & development institutions and national innovation center for science and technology. The BIMSA aims to develop fundamental scientific research and build a bridge between mathematics and industry applications. The director of BIMSA is the renowned mathematician, Prof. Shing-Tung Yau.

The Ding Lab in Privacy Protection and Blockchain Security will be led by Professor Jintai Ding and the lab currently has multiple open positions on all levels from full tenured professor to postdoc and research associate (without PhD) Anyone who works in related areas including (but not restricted to) computational algebra, computational algebraic geometry, number theory, mathematical optimization, quantum algorithms, post-quantum cryptography, multi-party computation, zero-knowledge proof, fully homomorphic encryption, privacy preserving algorithms, block chain, high performance computing, and algorithm implementations are welcome to apply. BIMSA offers internationally competitive salary packages and salary will be determined by applicant's qualification. Recent PhDs are especially encouraged to apply. A typical appointment for postdoc of BIMSA is for two-years, renewable for the third year with annual salary ranges from 300,000 RMB to 500,000 RMB depending on experience and qualifications. Ding Lab is an open lab with English as a working language. Interested applicants, please send email with CV to DingLab@bimsa.cn.

Closing date for applications:

Contact: Jintai Ding

In this paper, we study the connections between pseudo-free families of computational $\Omega$-algebras (in appropriate varieties of $\Omega$-algebras for suitable finite sets $\Omega$ of finitary operation symbols) and certain standard cryptographic primitives. We restrict ourselves to families $(H_d)_{d\in D}$ of computational $\Omega$-algebras (where $D\subseteq\{0,1\}^*$) such that for every $d\in D$, each element of $H_d$ is represented by a single bit string of length polynomial in the length of $d$. Very loosely speaking, our main results are as follows: (i) pseudo-free families of computational mono-unary algebras with one-to-one fundamental operations (in the variety of all mono-unary algebras) exist if and only if one-way families of permutations exist; (ii) for any $m\ge2$, pseudo-free families of computational $m$-unary algebras with one-to-one fundamental operations (in the variety of all $m$-unary algebras) exist if and only if claw-resistant families of $m$-tuples of permutations exist; (iii) for a certain $\Omega$ and a certain variety $\mathfrak V$ of $\Omega$-algebras, the existence of pseudo-free families of computational $\Omega$-algebras in $\mathfrak V$ implies the existence of families of trapdoor permutations.

An important security risk in cloud Field-Programmable Gate Arrays (FPGAs) is power wasting, occurring when a design exercises excessive switching activity with the intention to cause voltage-drop related faults in the host FPGA or, in the extreme case, FPGA reset and denial-of-service. In this paper, we introduce the idea of infiltrating undercover sensors for monitoring the fluctuations of FPGA core voltage. Our approach ensures that the shell has full control over sensor placement, done so that FPGA users do not have to sacrifice an inch of their design space nor to be aware that the voltage-fluctuations caused by their design are being monitored. Additionally, we describe how to design voltage-drop sensors that have higher coverage than the state-of-the-art alternatives and experimentally demonstrate that our sensors are indeed able to accurately monitor voltage fluctuations across the entire FPGA. Finally, we propose a novel metric which, after applied on sensor measurements, reveals the location of the source of the highest activity on the FPGA.

With every new generation, high-end FPGAs are becoming richer in features and resources, making the usage model of single-user per FPGA decreasingly cost-efficient. Although virtualized FPGAs enable multiple users to share the same FPGA, this multi-tenancy is not employed in practice because of potential security threats, such as voltage attacks. These attacks use power-wasting circuits to exercise excessive switching activity on the target FPGA to cause extreme voltage fluctuations, which produce timing faults in collocated circuits or, in extreme cases, reset target FPGA. In this work, we present the idea of automated embedding of the on-chip voltage sensors into the virtualized FPGAs and continuous monitoring of the core voltage for suspected fluctuations caused by a voltage attacker. Our sensors are nonintrusive and placement-adaptive because we implement them immediately after placing and routing the user design with resources that are left unused. We devise a novel measurement technique to continuously analyze the sensor outputs and locate the power-wasting circuits. Additionally, we are the first to use a synchronous power-wasting attacker, capable of producing timing faults, on Xilinx 7-series FPGAs and to successfully locate it. Hence, our proposed monitoring system enables the virtualized FPGA to identify the voltage attackers, at minimal cost, and prevent them from repeating the attack.

This paper presents detailed and computer-verified proofs of formulas that, given a permutation pi of 2^m indices with m>=1, produce control bits for a standard permutation network that uses 2^m(m-1/2) swaps to apply pi to a list. The formulas match the control bits computed by a serial algorithm of Stone (1968) and a parallel algorithm of Nassimi–Sahni (1982). The proofs are a step towards computer-verified correctness proofs for efficient implementations of these algorithms.

We examine some historical proto-mechanical cryptographic devices, such as the Wheatstone Cryptograph, that employ revolving clock hands or rotating concentric disks. The action of these “cipher clocks” can be factored into a stream cipher followed by a monoalphabetic substitution. This allows us to perform a stochastic hill-climbing attack to break the substitution. The attack maximizes a fitness that measures how well a decryption of the substitution cipher resembles an encryption of the stream cipher alone.

In this paper we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input and output whether the decryption key belongs to some known subset of keys. Partitioning oracles can arise when encryption schemes are not committing with respect to their keys. We detail adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords and de-anonymize anonymous communications. The attacks utilize efficient key multi-collision algorithms --- a cryptanalytic goal that we define --- against widely used authenticated encryption with associated data (AEAD) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305.

We build a practical partitioning oracle attack that quickly recovers passwords from Shadowsocks proxy servers. We also survey early implementations of the OPAQUE protocol for password-based key exchange, and show how many could be vulnerable to partitioning oracle attacks due to incorrectly using non-committing AEAD. Our results suggest that the community should standardize and make widely available committing AEAD to avoid such vulnerabilities.

Sanitizable signatures (SaS) allow a (single) sanitizer, chosen by the signer, to modify and re-sign a message in a somewhat controlled way, that is, only editing parts (or blocks) of the message that are admissible for modification.

This primitive is an efficient tool, with many formally defined security properties, such as unlinkability, transparency, immutability, invisibility, and unforgeability. An SaS scheme that satisfies these properties can be a great asset to the privacy of any field it will be applied to, e.g., anonymizing medical files.

In this work, we look at the notion of γ-sanitizable signatures ( γSaS): we take the sanitizable signatures one step further by allowing the signer to not only decide which blocks can be modified, but also how many of them at most can be modified within a single sanitization, setting a limit, denoted with γ. We adapt the security properties listed above to γSaS and propose our own scheme, ULISS (Unlinkable Limited Invisible Sanitizable Signature), then show that it verifies these properties. This extension of SaS can not only improve current use cases, but also introduce new ones, e.g., restricting the number of changes in a document within a certain timeframe.

In a universally composable framework, a global setup is intended to capture the ideal behavior of a primitive which is accessible by multiple protocols, allowing them to share state. The ledger implemented by blockchain protocols such as Bitcoin is a representative example of such global setup, since the Bitcoin ledger is known to be useful in various scenarios. Therefore, it has become increasingly popular to capture such ledgers as a global setup. One would hope that this allows one to make security statements about protocols that use such a global setup, e.g., a global ledger, which can then be automatically translated into the setting where the setup is replaced by a protocol implementing it, such as Bitcoin.

We show that the above reasoning is flawed and such a generic security-preserving replacement can only work under very (often unrealistic) strong conditions on the global setup. For example, the composable security of Bitcoin, cast as realizing an ideal ledger such as the one by Badertscher et al. [CRYPTO'17], is not sufficient per se to allow us to replace the ledger by Bitcoin when used as a global setup and to expect that security statements that are made in the global ledger-hybrid world would be preserved.

On the positive side, we provide characterizations of security statements for protocols that make use of global setups, for which the replacement is sound. Our results can be seen as a first guide on how to navigate the very tricky question of what constitutes a ``good'' global setup and how to use it in order to keep the modular protocol-design approach intact.

The concept of quantum bit commitment was introduced more than three decades ago in a failed attempt to base unconditional bit commitment solely on quantum information theory. In this work, we explore general properties of \textit{conditional} quantum bit commitment, which additionally assumes quantum computational hardness but without any mathematical structure (e.g. quantum-secure one-way function). While it is well known that a general quantum bit commitment scheme can only guarantee a fairly weak binding property compared with its classical counterpart, interestingly, we show that it also enjoys some other nice properties that its classical counterpart does not have. Among others, we show that any (interactive) quantum bit commitment scheme can be compiled into a non-interactive generic form (by an ensemble of quantum circuit pair). These general properties not only enable us to simplify both the construction and the security analysis of quantum bit commitment significantly but also suggest a potential use of it as a replacement of the classical one in quantum cryptography.

We prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of the quantum-hard one-way function.

Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments from quantum-hard one-way functions in the standard model. Instantiating the Bennet-Brassard-Crépeau-Skubiszewska (CRYPTO 91) framework with these commitments yields simulation-secure quantum oblivious transfer.

Permissionless blockchain systems such as Bitcoin or Ethereum are slow and expensive, since transactions are processed in a distributed network by a large set of parties. To improve on these shortcomings, a prominent approach is given by so-called 2nd-layer protocols. In these protocols parties process transactions off-chain directly between each other, thereby drastically reducing the costly and slow interaction with the blockchain. In particular, in the optimistic case, when parties behave honestly, no interaction with the blockchain is needed. One of the most popular off-chain solutions are Plasma protocols (often also called commit-chains). These protocols are orchestrated by a so-called operator that maintains the system and processes transactions between parties. Importantly, the operator is trustless, i.e., even if it is malicious users of the system are guaranteed to not lose funds. To achieve this guarantee, Plasma protocols are highly complex and require involved and expensive dispute resolution processes. This has significantly slowed down development and deployment of these systems.

In this work we propose CommiTEE-- a simple and efficient Plasma system leveraging the power of trusted execution environments (TEE). Besides its simplicity, our protocol requires minimal interaction with the blockchain, thereby drastically reducing costs and improving efficiency. An additional benefit of our solution is that it allows for switching between operators, in case the main operator goes offline due to system failure, or behaving maliciously. We implemented and evaluated our system over Ethereum and show that it is at least $2$ times (and in some cases more than $16$ times) cheaper in terms of communication complexity when compared to existing Plasma implementations. Moreover, for protocols using zero-knowledge proofs (like NOCUST-ZKP), CommiTEE decreases the on-chain gas cost by a factor $\approx 19$ compared to prior solution.

Grover's search algorithm gives a quantum attack against block ciphers with query complexity $O(\sqrt{N})$ to search a keyspace of size $N$, when given a sufficient number of plaintext-ciphertext pairs. At EUROCRYPT 2020, Jaques, Naehrig, Roetteler, and Virdia have estimated the cost of quantum key search attacks against AES under different security categories as defined in NIST's PQC standardization process.

In this work, we extend their approach to lightweight block ciphers for the cost estimates of quantum key search attacks under circuit depth restrictions. We design quantum circuits for the lightweight block ciphers GIFT, SKINNY, and SATURNIN. Our circuits give overall cost in both the gate count and depth-times-width cost models. Based on the NIST' security categories for maximum depth, we present the concrete cost of quantum key search against GIFT, SKINNY, and SATURNIN.

We implement the full Grover oracle for GIFT-64, GIFT-128, SKINNY-64, SKINNY-128 and SATURNIN-256 in Q\# quantum programming language for unit tests and automatic resource estimations.

We present a sub-exponential forger by using a $k$-sum algorithm against the aggregate $\Gamma$ signature, which was proposed at AsiaCCS2019 by Zhao. Our forger is a universal forger under a key-only attack and effective in the knowledge of secret key model.

Machine learning is an important tool for analyzing large data sets, but its use on sensitive data may be limited by regulation. One solution to this problem is to perform machine learning tasks on encrypted data using homomorphic encryption, which enables arbitrary computation on encrypted data. We take a fresh look at one specific task: training a logistic regression model on encrypted data. The most important factor in the efficiency of a solution is the multiplicative depth of the homomorphic circuit. Two prior works have given circuits with multiplicative depth of five per training iteration. We optimize one of these solutions, by Han et al. [Han+18], and give a circuit with half the multiplicative depth per iteration on average, which allows us to perform twice as many training iterations in the same amount of time. In the process of improving the state-of-the-art circuit for this task, we identify general techniques to improve homomorphic circuit design for two broad classes of algorithms: iterative algorithms, and algorithms based on linear algebra over real numbers. First, we formalize the encoding scheme from [Han+18] for encoding linear algebra objects as plaintexts in the CKKS homomorphic encryption scheme. We also show how to use this encoding to homomorphically compute many basic linear algebra operations, including novel operations not discussed in prior work. This “toolkit” is generic, and can be used in any application based on linear algebra. Second, we demonstrate how generic compiler techniques for loop optimization can be used to reduce the multiplicative depth of iterative algorithms.