## IACR News

Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 14 January 2022

###### University of Innsbruck, Austria, EU
Job Posting

The University of Innsbruck, located in the heart of the alps, has a tenure track opportunity in the field of cryptography.

The Department of Computer Science is looking for an ambitious researcher to build a bridge between the interdisciplinary approach taken by its Security & Privacy Lab and theoretical research groups, like Computational Logic and Theoretical Computer Science. Research activities would focus on producing evidence on the security or privacy of cryptographic systems covering theory and/or implementation. The individual should be comfortable teaching multiple approaches to cryptography. The ideal candidate would build a research group on cryptography in the course of the tenure process, the details of which are negotiated in the first year of employment as routinely done in the Austrian academic system.

Tyrol, Austria is one of the most livable places in Europe with world-class healthcare, excellent social security, and free education from kindergarden to university.

Applications are due on 28 January 2022. Follow the link above for more details.

Closing date for applications:

Contact: Rainer Böhme [rainer dot boehme at uibk.ac.at]

#### 10 January 2022

###### Graz University of Technology, Graz, Austria
Job Posting
The Institute of Applied Information Processing and Communications (aka IAIK) is the largest university institute in Austria for research and education in security and privacy. It has been active in this field for more than 30 years and currently employs more than 60 researchers. Within the "Secure Systems" area of our institute Sujoy Sinha Roy is establishing the new research group "Cryptographic Engineering”.

In order to complement our team, we are looking for a full-time PhD researcher in the implementation aspects of cryptography.

Responsibilities:
The PhD researcher will be working on Scientific research in the field of implementation and physical security aspects of novel cryptographic algorithms within the “Cyroptografic Engineering” group within the “Secure Systems” area at IAIK.

Required Qualifications:
• MSc degree in computer science, information and computer engineering, software development, mathematics, or a related field.
• Excellent knowledge of English
• The ability to work in an international environment
• Research experience from MSc projects or publication of scientific publications
• Strong background in the field of cryptography and cryptographic implementations
• Excellent skills in programming and/or digital circuit design

How to apply: Applications, curriculum vitae and other documents should preferably be uploaded here csbme.tugraz.at/go/applications/7050-21-013.
The earliest starting date for the PhD candidate will be March 2022.
The application deadline is February 6th.

Closing date for applications:

Contact: Sujoy Sinha-Roy - sujoy.sinha-roy@iaik.tugraz.at

• ###### ADVA Optical Networking, Munich, Germany
Job Posting
We are currently looking for a highly motivated Engineer Advanced Technology (M/F/D) to join our Advanced Technology team in Munich. If you want to be a part of our growing company and want to work towards a PhD degree on a three-year fixed-term basis, consider applying.

Closing date for applications:

###### Laboratoire Hubert Curien, University of Lyon, Saint-Etienne, France
Job Posting
The main objective of the research in the Embedded System Security Group is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. More information on https://laboratoirehubertcurien.univ-st-etienne.fr/en/teams/secure-embedded-systems-hardware-architectures.html. For a new project which addresses the problem of the security System-on-Chip (inside side channel analysis, fault injection, malicious exploitation of share hardware resources, etc.). We are looking for candidates with an outstanding Ph.D in hardware security and a strong publication record in this field. Knowledge of French is not mandatory. The Post-Doc position will start in March 2022, it is funded for at least 12 monthq. To apply please send your detailed CV (with publication list), motivation for applying (1 page) and names of at least two people who can provide reference letters (e-mail).

Closing date for applications:

Contact: Contact: Prof. Lilian BOSSUET lilian.bossuet(at)univ-st-etienne.fr

###### CryptoExperts, Paris, France
Job Posting

CryptoExperts develops and maintains a white-box cryptography technology which aims at producing white-box cryptography software components secure against beyond-state-of-the-art attacks.

We are looking for a candidate who will take part to the design and implementation effort of CryptoExperts’ white-box cryptography technology.

The complete job offer is available here: https://www.cryptoexperts.com/job-offer-wbc.pdf

Closing date for applications:

Contact: To apply please write to jobs@cryptoexperts.com with a short description of your profile, story and motivation, your CV, and (optionally) recommendation from (former) co-workers.

###### Norwegian University of Sciennce and Technology (NTNU), Dep. of Inf. Security and Comm. Technology
Job Posting
At the Department of Information Security and Communication Technology there is a vacant permanent position as associate professor in Cryptology within our Cryptology Discipline.

Required qualifications: You must have the qualifications required for the position of associate professor in the field of Cyptology, as outlined:
A. Your PhD, or comparable academic work, must be within the field of cryptology (or a comparable relevant field), of particular interest are candidates with a documented acadmic track record within one or several of the following topics: A1. Design and analysis of post-quantum cryptographic primitives; A2. Design and analysis of post-quantum cryptographic protocols; A3. Lightweight cryptography; A4. Blockchain technologies; A5. Cryptography and Privacy; A6. Homomorphic encryption; A7. Secure Cryptographic Hardware, Side Channels Security (attacks and resistance); A8. Cryptology and Biometrics; A9. Cryptology and Software Security (Secure Operating Systems).
B. Relevant academic fields include mathematics, computer science and communication technology. If you can document that you are in the final stages of your PhD studies, your application may also be considered.
C. Good written and oral English language skills.

Closing date for applications:

Contact: Professor Danilo Gligoroski, e-mail danilo.gligoroski@ntnu.no

###### Amit Choudhari, Sylvain Guilley, Khaled Karray
ePrint Report
Cryptographic libraries have become an integral part of every digital device. Studies have shown that these systems are not only vulnerable due to bugs in cryptographic libraries, but also due to misuse of these libraries. In this paper, we focus on vulnerabilities introduced by the application developer. We performed a survey on the potential misusage of well-known libraries such as PKCS #11. We introduced a generic tool CRYScanner, to identify such misuses during and post-development. It works on the similar philosophy of an intrusion detection system for an internal network. This tool provides verification functions needed to check the safety of the code, such as detecting incorrect call flow and input parameters.

We performed a feature-wise comparison with the existing state of the art solutions. CRYScanner includes additional features, preserving the capabilities of both static and dynamic analysis tools. We also show the detection of potential vulnerabilities in the several sample codes found online.
###### Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai , Nathan Keller, Ohad Klein
ePrint Report
Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically close to us can decrypt? To solve this kind of problems, we introduce and study a new type of hash functions for finding shifts in sublinear time. A function $h:\{0,1\}^n\to \mathbb{Z}_n$ is a $(d,\delta)$ {\em locality-preserving hash function for shifts} (LPHS) if: (1) $h$ can be computed by (adaptively) querying $d$ bits of its input, and (2) $\Pr [ h(x) \neq h(x \ll 1) + 1 ] \leq \delta$, where $x$ is random and $\ll 1$ denotes a cyclic shift by one bit to the left. We make the following contributions.

Near-optimal LPHS via Distributed Discrete Log: We establish a general two-way connection between LPHS and algorithms for distributed discrete logarithm in the generic group model. Using such an algorithm of Dinur et al. (Crypto 2018), we get LPHS with near-optimal error of $\delta=\tilde O(1/d^2)$. This gives an unusual example for the usefulness of group-based cryptography in a post-quantum world. We extend the positive result to non-cyclic and worst-case variants of LPHS.

Multidimensional LPHS: We obtain positive and negative results for a multidimensional extension of LPHS, making progress towards an optimal 2-dimensional LPHS.

Applications: We demonstrate the usefulness of LPHS by presenting cryptographic and algorithmic applications. In particular, we apply multidimensional LPHS to obtain an efficient "packed" implementation of homomorphic secret sharing and a sublinear-time implementation of location-sensitive encryption whose decryption requires a significantly overlapping view.
###### Bingyong Guo, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, Zhenfeng Zhang
ePrint Report
Asynchronous BFT consensus can implement robust mission-critical decentralized services in the unstable or even adversarial wide-area network without relying on any form of timing assumption. Starting from the work of HoneyBadgerBFT (CCS 2016), several studies tried to push asynchronous BFT towards practice. In particular, in a recent work of Dumbo (CCS 2020), they redesigned the protocol backbone and used one multi-valued validated Byzantine agreement (MVBA) to replace $n$ concurrent asynchronous binary agreement (ABA) protocols and dramatically improved the performance.

Despite those efforts, asynchronous BFT protocols remain to be slow, and in particular, the latency is still quite large. There are two reasons contributing to the inferior performance: (1) the reliable broadcast (RBC) protocols still incur substantial costs; (2) the MVBA protocols are quite complicated and heavy, and all existing constructions need dozens of rounds and take the majority of he overall latency.

We first present a new construction of asynchronous BFT that replaces RBC instance with a cheaper broadcast component. It not only reduces the $O(n^3)$ message complexity incurred by $n$ RBCs to $O(n^2)$, but also saves up to 67% communications (in the presence of a fair network scheduler). Moreover, our technical core is a new MVBA protocol, Speeding MVBA, which is concretely more efficient than all existing MVBAs. It requires only 6 rounds in the best case and expected 12 rounds in the worst case (by contrast, several dozens of rounds in the MVBA from Cachin et al. [12] and the recent Dumbo-MVBA [32], and around 20 rounds in the MVBA from Abraham et al. [4]). Our new technique of the construction might be of independent interests.

We implemented Speeding Dumbo and did extensive tests among up to 150 EC2 t2.medium instances evenly allocated in 15 AWS regions across the globe. The experimental results show that Speeding Dumbo reduces the latency to about a half of Dumbo's, and also doubles the throughput of Dumbo, through all system scales from 4 nodes to 150 nodes. We also did tests to benchmark individual components such as the broadcasts and the MVBA protocols, which may be of interests for future improvements.
###### Andrada-Teodora Ciulei, Marian-Codrin Crețu, Emil Simion
ePrint Report
Blockchain is a type of Distributed Ledger Technology (DLT) that has been included in various types of fields due to its numerous benefits: transparency, efficiency, reduced costs, decentralization, and distributivity realized through public-key cryptography and hash functions. At the same time, the increased progress of quantum computers and quantum-based algorithms threatens the security of the classical cryptographic algorithms, in consequence, it represents a risk for the Blockchain technology itself. This paper briefly presents the most relevant algorithms and procedures that have contributed to the progress of quantum computing and the categories of post-quantum cryptosystems. We also included a description of the current quantum capabilities because their evolution directly influences the necessity of increasing post-quantum research. Further, the paper continues as a guide to understanding the fundamentals of blockchain technology, and the primitives that are currently used to ensure security. We provide an analysis of the most important cryptocurrencies according to their ranking by market capitalization (MC) in the context of quantum threats, and we end up with a review of post-quantum blockchain (PQB) schemes proposals.
###### Mostafizar Rahman, Dhiman Saha, Goutam Paul
ePrint Report
This work investigates a generic way of combining two very effective and well-studied cryptanalytic tools, proposed almost 18 years apart, namely the boomerang attack introduced by Wagner in FSE 1999 and the yoyo attack by Ronjom et. al. in Asiacrypt 2017. In doing so, the s-box switch and ladder switch techniques are leveraged to embed a yoyo trail inside a boomerang trail. As an immediate application, a 6-round key recovery attack on AES-128 is mounted with time complexity of $2^{78}$. A 10-round key recovery attack on recently introduced AES-based tweakable block cipher Pholkos is also furnished to demonstrate the applicability of the new technique on AES-like constructions. The results on AES are experimentally verified by applying and implementing them on a small scale variant of AES. We provide arguments that draw a relation between the proposed strategy with the retracing boomerang attack devised in Eurocrypt 2020. To the best of our knowledge, this is the first attempt to merge the yoyo and boomerang techniques to analyze SPN ciphers and warrants further attention as it has the potential of becoming an important cryptanalysis tool.

#### 08 January 2022

###### Jean-Philippe Bossuat, Juan Ramón Troncoso-Pastoriza, Jean-Pierre Hubaux
ePrint Report
Bootstrapping parameters for the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17), are usually instantiated using sparse secrets to be efficient. However, using sparse secrets constrains the range of practical parameters within a tight interval, as they must support a large enough depth for the bootstrapping circuit but also be secure with respect to the sparsity of their secret.

We present a bootstrapping procedure for the CKKS scheme that combines both dense and sparse secrets. Our construction enables the use of parameters for which the homomorphic capacity is based on a dense secret, yet with a bootstrapping complexity that remains the one of a sparse secret and with a large security margin. Moreover, this also enables us to easily parameterize the bootstrapping circuit so that it has a negligible failure probability that, to the best of our knowledge, has never been achieved for the CKKS scheme. When using the parameters of previous works, our bootstrapping procedures enables a faster procedure with an increased precision and lower failure probability. For example we are able to bootstrapp a plaintext of $\mathbb{C}^{32768}$ in 20.2 sec, with 32.11 bits of precision, 285 bits of modulus remaining, a failure probability of $2^{-138.7}$ and 128 bit security.
###### Nicolai Müller, David Knichel, Pascal Sasdrich, Amir Moradi
ePrint Report
Accelerated by the increased interconnection of highly accessible devices, the demand for effective and efficient protection of hardware designs against SCA is ever rising, causing its topical relevance to remain immense in both, academia and industry. Among a wide range of proposed countermeasures against SCA, masking is a highly promising candidate due to its sound foundations and well-understood security requirements. In addition, formal adversary models have been introduced, aiming to accurately capture real-world attack scenarios while remaining sufficiently simple to efficiently reason about the SCA resilience of designs. Here, the $d$-probing model is the most prominent and well-studied adversary model. Its extension, introduced as the robust $d$-probing model, covers physical defaults occurring in hardware implementations, particularly focusing on combinational recombinations (glitches), memory recombinations (transitions), and routing recombinations (coupling). With increasing complexity of modern cryptographic designs and logic circuits, formal security verification becomes ever more cumbersome. This started to spark innovative research on automated verification frameworks. Unfortunately, these verification frameworks mostly focus on security verification of hardware circuits in the presence of glitches, but remain limited in identification and verification of transitional leakage. To this end, we extend SILVER, a recently proposed tool for formal security verification of masked logic circuits, to also detect and verify information leakage resulting from combinations of glitches and transitions. Based on extensive case studies, we further confirm the accuracy and practical relevance of our methodology when assessing and verifying information leakage in hardware implementations.
###### Xiuju Huang, Jiashuo Song , Zichen Li
ePrint Report
The verifier-local revocation mechanism (VLR) is an ideal function of group signature. As long as the verifier knows the revocation list, he/she can verify the legitimacy of the signer, prevent the revoked user from impersonating a legitimate user for signature, ensure the timeliness of signature information and save resources. Group signature is often required to realize users' dynamic addition and revocation. Therefore, an efficient lattice signature scheme with a local revocation mechanism and alter the number of users has become an important topic. In this paper, a zero-knowledge proof scheme on the lattice has been proposed. Based on it, a group signature scheme with VLR has been constructed. This scheme can effectively join and revocation without generating the key pair again. The tracking mechanism uses an encryption scheme. As long as given a correct tracking key, the signer index can be opened quickly. And this algorithm has short public key, logarithmic signature length, and efficient implementation of the VLR function.
###### Sisi Duan, Haibin Zhang, Boxin Zhao
ePrint Report
This paper refutes the conventional wisdom that information-theoretic BFT is impractical. We design and implement WaterBear, the first practical information-theoretic asynchronous Byzantine fault-tolerant (BFT) protocol. We also present a more efficient, quantum-secure asynchronous BFT protocol, WaterBear-QS, which, compared to WaterBear, additionally uses a collision-resistant hash function.

We show that WaterBear and WaterBear-QS are efficient under both failure-free and failure scenarios, achieving comparable performance to the state-of-the-art asynchronous BFT protocols. In particular, our failure case evaluation is thus far the most comprehensive evaluation for asynchronous BFT settings.
###### Sisi Duan, Haibin Zhang
ePrint Report
Reaching consensus is the single most crucial problem in fault-tolerant distributed computing. This paper studies asynchronous consensus with Byzantine failures commonly known as asynchronous binary Byzantine agreement (ABA). ABA is a key component as well as a bottleneck for (almost) all known asynchronous Byzantine fault-tolerant (BFT) protocols and asynchronous multi-party computation (MPC) with guaranteed output. This paper addresses two significant problems in ABA: we propose the first common-coin based ABA with 2 steps only in a round and the first practical solution on running ABA in a fully parallelizable manner. We first present Pillar, a new round-based ABA protocol using common coins, having 2 steps in a round. Pillar can be directly used to improve all practical asynchronous BFT protocols implemented and MPC protocols achieving guaranteed output. To demonstrate the performance of Pillar, we use it in the BEAT protocol based on the classic framework of Ben-Or, Kemler, and Rabin and HoneyBadgerBFT, and implement a new BFT protocol, called ACE, providing up to 2x the throughput of BEAT. We go on to suggest reproposable ABA (RABA), a generalized ABA primitive that allows a replica to change its mind and vote twice. In contrast to conventional ABA, RABA requires the protocol to be biased towards 1, but does not require external validity (via, e.g., expensive threshold signatures). We use Pillar to build Pisa, a signature-free RABA protocol that is as efficient as Pillar. We also show how to turn some other ABA protocols (including the one by Cachin, Kursawe, and Shoup) to RABA. We then propose a novel asynchronous BFT framework built on reliable broadcast (RBC) and RABA. This leads to the first fully parallelizable asynchronous BFT protocol, allowing all ABA instances to run in a strictly concurrent manner. Our concrete instantiation, called PACE, consistently and significantly outperforms existing asynchronous BFT protocols in terms of all metrics, having much fewer steps than all asynchronous BFT implemented for all practically large systems. PACE provides 6x the throughput of BEAT when there are 91 replicas. Such a solution can be directly used as a solution to run ABA in parallel, a procedure needed not just in BFT but in interactive consistency and MPC with guaranteed output. Our result, therefore, identifies RABA as a first-class primitive in distributed computing. Also, the PACE framework lays the foundation on information-theoretic asynchronous BFT and asynchronous BFT without public-key cryptography.
###### Fukang Liu, Gaoli Wang, Willi Meier, Santanu Sarkar, Takanori Isobe
ePrint Report
We propose a conceptually intuitive technique called algebraic meet-in-the-middle (MITM) attack in this paper. Different from the common MITM attacks where some intermediate state values are stored, several sets of linear equations will be stored in the algebraic MITM attack. Moreover, at the matching phase, it is necessary to first perform some linear transformations on the to-be-matched intermediate state value and only partial state bit information is used for the match. Once a match is found, retrieve the corresponding linear equation system and solve it to recover the full necessary information. This new technique fits very well with LowMC, a popular and important design using partial nonlinear layers. Based on it, we can reduce the memory complexity of the simple difference enumeration attack over state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. Specifically, the guess-and-determine strategy is no more adopted at the key-recovery phase, instead, we recover the full key by directly solving an overdefined system of quadratic equations. With the above new techniques, the attacks on LowMC and \mbox{LowMC-M} published at CRYPTO 2021 are further improved and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.
###### Ahmet Ramazan Ağırtaş, Oğuz Yayla
ePrint Report
An accountable subgroup multi-signature is a kind of multi-signature scheme in which any subgroup S of the group G of potential signers jointly sign a message $m$, ensuring that each member of S is accountable for the resulting signature. In this paper we propose three novel pairing-based accountable subgroup multi-signature (ASM) schemes. In the first one, we use Feldman's verifiable secret sharing scheme as an implicit authentication and proof-of-possession for setting up the group G. In the second one, the members participating in authentication is decided by the subgroup itself. In the third one, we consider a designated combiner managing the authentication process. All schemes that we propose here require fewer computations in signature generation, signature aggregation and verification phases than the pairing-based ASM scheme proposed by Boneh, Drijvers and Neven. Moreover, our first and the third ones solve the open problem of constructing an ASM scheme in which the subgroup S of signers is not known before the signature generation. Besides, we give a method of eliminating the combiner in case of knowing the subgroup of signers S in advance. Further we extend our proposed schemes to aggregated versions. For $n$ accountable subgroup multi-signatures, aggregated versions of our proposed schemes output an aggregated signature with size of a single group element and require $n+1$ pairings in aggregated signature verification, whereas the partial aggregated ASM scheme of Boneh, Drijvers and Neven gives an aggregated signature with size of $n+1$ group elements and requires $2n+1$ pairings in aggregated signature verification.
###### Shingo Sato, Keita Emura, Atsushi Takayasu
ePrint Report
(Fully) homomorphic encryption ((F)HE) allows users to publicly evaluate circuits on encrypted data. Although public homomorphic evaluation property has various applications, (F)HE cannot achieve security against chosen ciphertext attacks (CCA2) due to its nature. To achieve both the CCA2 security and homomorphic evaluation property, Emura et al. (PKC 2013) introduced keyed-homomorphic public key encryption (KH-PKE) and formalized its security denoted by KH-CCA security. KH-PKE has a homomorphic evaluation key that enables users to perform homomorphic operations. Intuitively, KH-PKE achieves the CCA2 security unless adversaries have a homomorphic evaluation key. Although Lai et al. (PKC 2016) proposed the first keyed-fully homomorphic encryption (keyed-FHE) scheme, its security relies on the indistinguishability obfuscation (iO), and this scheme satisfies a weak variant of KH-CCA security. Here, we propose a generic construction of a KH-CCA secure keyed-FHE scheme from an FHE scheme secure against non-adaptive chosen ciphertext attack (CCA1) and a strong dual-system simulation-sound non-interactive zero-knowledge (strong DSS-NIZK) argument system by using the Naor-Yung paradigm. We show that there are a strong DSS-NIZK and an IND-CCA1 secure FHE scheme that are suitable for our generic construction. This shows that there exists a keyed-FHE scheme from simpler primitives than iO.

#### 07 January 2022

###### Roberto La Scala, Sergio Polese, Sharwan K. Tiwari, Andrea Visconti
ePrint Report
In this paper we study the security of the Bluetooth stream cipher E0 from the viewpoint it is a "difference stream cipher", that is, it is defined by a system of explicit difference equations over the finite field GF(2). This approach highlights some issues of the Bluetooth encryption such as the invertibility of its state transition map, a special set of 14 bits of its 132-bit state which when guessed imply linear equations among the other bits and finally a very small number of spurious keys compatible with a keystream of about 60 bits. Exploiting these issues, we implement an algebraic attack using Grobner bases, SAT solvers and Binary Decision Diagrams. Testing activities suggest that the version based on Grobner bases is the best one and it is able to attack E0 in about 2^79 seconds on an Intel i9 CPU. To the best of our knowledge, this work improves any previous attack based on a short keystream, hence fitting with Bluetooth specifications.