## 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:

#### 16 September 2022

###### Federico Canale, Tim Güneysu, Gregor Leander, Jan Thoma, Yosuke Todo, Rei Ueno
ePrint Report
Randomized cache architectures have proven to significantly increase the complexity of contention-based cache side channel attacks and therefore pre\-sent an important building block for side channel secure microarchitectures. By randomizing the address-to-cache-index mapping, attackers can no longer trivially construct minimal eviction sets which are fundamental for contention-based cache attacks. At the same time, randomized caches maintain the flexibility of traditional caches, making them broadly applicable across various CPU-types. This is a major advantage over cache partitioning approaches.

A large variety of randomized cache architectures has been proposed. However, the actual randomization function received little attention and is often neglected in these proposals. Since the randomization operates directly on the critical path of the cache lookup, the function needs to have extremely low latency. At the same time, attackers must not be able to bypass the randomization which would nullify the security benefit of the randomized mapping. In this paper we propose \cipher (\underline{S}ecure \underline{CA}che \underline{R}andomization \underline{F}unction), the first dedicated cache randomization cipher which achieves low latency and is cryptographically secure in the cache attacker model. The design methodology for this dedicated cache cipher enters new territory in the field of block ciphers with a small 10-bit block length and heavy key-dependency in few rounds.
###### George Lu, Brent Waters
ePrint Report
The random oracle methodology is central to the design of many practical cryptosystems. A common challenge faced in several systems is the need to have a random oracle that outputs from a structured distribution $\mathcal{D}$, even though most heuristic implementations such as SHA-3 are best suited for outputting bitstrings.

Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We make the following contributions:

-We provide a definitional framework for our results. We say that a sampling algorithm $\mathsf{Sample}$ for a distribution is explainable if there exists an algorithm $\mathsf{Explain}$ where, for a $x$ in the domain, we have that $\mathsf{Explain}(x) \rightarrow r \in \{0,1\}^n$ such that $\mathsf{Sample}(r)=x$. Moreover, if $x$ is sampled from $\mathcal{D}$ the explained distribution is statistically close to choosing $r$ uniformly at random. We consider a variant of this definition that allows the statistical closeness to be a "precision parameter'' given to the $\mathsf{Explain}$ algorithm. We show that sampling algorithms which satisfy our `explainability' property can be programmed as a random oracle.

-We provide a simple algorithm for explaining \emph{any} sampling algorithm that works over distributions with polynomial sized ranges. This includes discrete Gaussians with small standard deviations.

-We show how to transform a (not necessarily explainable) sampling algorithm $\mathsf{Sample}$ for a distribution into a new $\mathsf{Sample}'$ that is explainable. The requirements for doing this is that (1) the probability density function is efficiently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density above a given threshold $p$, showing the equivalence of random oracles to these distributions and random oracles to uniform bitstrings. This includes a large class of distributions, including all discrete Gaussians.

-A potential drawback of the previous approach is that the transformation requires an additional computation of the density function. We provide a more customized approach that shows the Miccancio-Walter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.
###### Hao Guo, Jintai Ding
ePrint Report
We give algebraic relations among equations of three algebraic modelings for MinRank problem: support minors modeling, Kipnis–Shamir modeling and minors modeling.
###### Protocol Labs, Remote
Job Posting
Lurk is an in-development, Turing-complete programming language for recursive zk-SNARKs. It is a statically scoped dialect of Lisp, implemented in Rust to support evaluation, proving, and verification in zero-knowledge. Since Lurk is Turing-complete, it can be used (within resource limits) to make and prove arbitrary computational claims without the constraints of traditional fixed-circuit SNARKs. A Rust Cryptography Engineer for Lurk will help drive the development of the Lurk programming language. The ideal candidate for this job will have deep knowledge of zero-knowledge cryptography and experience writing zk-proofs or zk-proof adjacent software in Rust. You can learn more about Lurk at https://github.com/lurk-lang and the Rust implementation at https://github.com/lurk-lang/lurk-rs.

Closing date for applications:

Contact: Luke Sandquist

###### UNSW, Sydney, Australia
Job Posting
We have two PhD positions in Post Quantum Cryptography at UNSW, Sydney funded by the Sydney Quantum Academy (SQA).

1. Post Quantum Cryptography for Blockchains
2. Towards a Quantum-Safe Internet
The scholarships are for a maximum period of 4 years.

Prospective students are expected to have strong mathematical inclination and strong background in data structures, discrete mathematics and algorithms. Candidates with knowledge of cryptography (such as completion of undergraduate/graduate course or research project) will be preferred.

Open to students who have completed a bachelor’s degree or a master’s degree in Computer Science, Mathematics or a related discipline. Candidates in their final year of study are welcome to apply.

Closing date for applications:

###### Sorbonne Université, Paris, France
Job Posting
Topic: Remote attack on a quantum key distribution system. Modern-era cryptography is threatened by recent developments in quantum computing. One way of mitigating this threat is quantum cryptography, or more specifically quantum key distribution (QKD) protocol. A QKD system consists in hardware to create and transport quantum states, as well as software to interface quantum hardware with classical communication infrastructure. Literature on attacks is still limited in this field. Examples are Makarov et al., Nature Photon. 2010 and Alléaume et al., Phys. Rev. A 2016. These works mainly concern physical vulnerabilities on the hardware hence they require to gain physical access to the network in order to perform the attack. In an objective of certification and standardisation of future QKD systems, the whole spectrum of vulnerabilities must be studied, including remote attacks. The subject of this post-doc offer aims at finding attacks on a QKD system without physical access to the hardware, as well as suggesting countermeasures. In the target attack scenario, the attacker has no physical access to hardware, but he can leave a third-party software on one of the machines of the QKD system. How the attacker gains access to the machine to drop the software file is out of scope. The objective of this work is to make the third-party software modify the behaviour of physical systems in order to cause a leak of sensitive information or a denial of service. Fully software oriented attacks, such as memory scrapping or random generation weakening, are thus excluded from this work. An example of acceptable attack would be a modification of the clock by the third-party, see Jouguet et al., Phys. Rev. A 2020 (the difference being that clock modification is caused by software instead of hardware). Another possibility would be to change the physical parameters of the QKD system, e.g. by using the API of the pilot component of the system. the post-doc will focus on a specific operational QKD system. Ideal profile: PhD in quantum physics with interest for computer security or the opposite. Useful skills: cryptography; reverse engineering; software development.

Closing date for applications:

Contact: Eleni Diamanti, Laboratoire d’Informatique de Sorbonne Université (LIP6)

###### Inria of the University of Rennes
Job Posting
Private and Secure Computation on Personal Data The recruited postdoctoral researcher is expected to work on the design of a distributed data vault that can (i) store personal data while keeping it safe from third parties, (ii) support computation on encrypted or otherwise protected personal data to obtain aggregate statistics while respecting the privacy of the individual data items, (iii) provide means to remunerate users that enable computation on their personal data. In particular, we aim to address this challenge by relying on a byzantine-fault tolerant [1,2] decentralized storage platform that can store data reliably in encrypted form. We plan to combine techniques like multiparty computation [3] and homomorphic encryption [4] with technologies like trusted execution environments [5] to enable computation on such encrypted data. This will allow us to address a variety of use cases, such as decentralized [6] and federated machine learning algorithms [7]. The system should also keep track of the usage of personal data to support remuneration schemes. To this end, we plan to leverage our recent theoretical work on lightweight distributed ledgers [8, 9]. The postdoctoral researcher will contribute by performing original research on these topics, and will also participate in the supervision of Masters and PhD students. In doing so, he or she will collaborate with Davide Frey and other members of the WIDE team, as well as with international partners within the SOTERIA project and other related projects. Although teaching is not a requirement, the candidate can also choose to teach relevant courses at the University of Rennes 1 and affiliated institutions.

Closing date for applications:

Contact: Davide Frey

###### QuSoft / University of Amsterdam
Job Posting

The Theory of Computer Science (TCS) group at the Informatics Institute (IvI) of the University of Amsterdam (UvA) is looking for an excellent candidate for a fully funded PhD position as part of QSI (Quantum-Safe Internet), a Marie Curie Innovative Training Network (MSCA-ITN). The QSI network involves top-ranking partner universities from France, Italy, Germany, the Netherlands, Denmark, Spain, the UK, and Switzerland, as well as industrial partners.

You will conduct research at the intersection of quantum and post-quantum cryptography and publish/ present the results at top venues for research in crypto/ IT Security. You will be supervised by Prof. Christian Schaffner and Dr. Florian Speelman.

We are looking for a candidate with:
• a MSc in computer science, mathematics, or a related field;
• strong academic performance in university-level courses related to cryptography, IT security, theoretical CS, or mathematics;
• professional command of English and good presentation skills;
• compliance with the MSCA-ITN mobility rule: you must not have resided or carried out your main activity (work, studies, etc.) in the Netherlands for more than 12 months in the 36 months immediately before your recruitment date.
Familiarity with provable security and/ or a strong mathematical background are a plus.

We offer:
• Full-time employment for the duration of the PhD
• A well-rounded training offered by the QSI network, covering a range of topics related to secure communications in the quantum era, as well as complementary training intended to enhance your personal development.
• Generous travel budget that allows for, e.g., exposure to different sectors via planned placements and attendance to summer schools.

Closing date for applications:

Contact: Prof. Christian Schaffner

###### George Mason University
Job Posting
Associate/Full Professor of Cybersecurity and Commonwealth Cyber Initiative Fellow

The George Mason University and Commonwealth Cyber Initiative (CCI), within the College of Engineering and Computing (CEC), invites applications for an Associate/Full Professor of Cybersecurity and Commonwealth Cyber Initiative Fellow position. GMU has a strong institutional commitment to the achievement of excellence and diversity among its faculty and staff, and strongly encourages candidates to apply who will enrich Mason’s academic and culturally inclusive environment.

The incumbent will conduct research at GMU and as part of the Northern Virginia Node of the Commonwealth Cyber Initiative, and in partnership with researchers from the Coastal Node of the Commonwealth Cyber Initiative and Old Dominion University. Successful candidates will have access to the faculty and facilities of both GMU and Old Dominion University to enable their success.

Responsibilities:

Serve as the director of the interdisciplinary research effort between GMU, Old Dominion University and the Northern Virginia and Coastal Nodes of the CCI;

Leverage university-level strategic priorities in cybersecurity research to lead transformative growth and impact the research portfolio, and to further encourage and foster new and existing collaborations with academic, industrial, and governmental institutions in Northern Virginia, Coastal Virginia and the greater Washington, D.C., area;

Accelerate the growth of high-quality academic programs, facilitate interdisciplinary research initiatives, and broaden the scope and focus areas of research in Mason with significant potential for commercialization.

Required Qualifications:

Doctorate in CS, ECE, IT, or a related field;

Eligible for a tenured appointment as associate or full professor;

Outstanding cybersecurity research and publication record;

US citizen

Closing date for applications:

#### 15 September 2022

###### Diana Ghinea, Fabian Kaczmarczyck, Jennifer Pullman, Julien Cretin, Stefan Kölbl, Rafael Misoczki, Jean-Michel Picod, Luca Invernizzi, Elie Bursztein
ePrint Report
Recent advances in quantum computing are increasingly jeopardizing the security of cryptosystems currently in widespread use, such as RSA or elliptic-curve signatures. To address this threat, researchers and standardization institutes have accelerated the transition to quantum-resistant cryptosystems, collectively known as Post-Quantum Cryptography (PQC). These PQC schemes present new challenges due to their larger memory and computational footprints and their higher chance of latent vulnerabilities.

In this work, we address these challenges by introducing a scheme to upgrade the digital signatures used by security keys to PQC, focusing on both its theoretical and practical aspects. Specifically, we introduce a hybrid digital signature scheme based on two building blocks: a classically-secure scheme, ECDSA, and a post-quantum secure one, Dilithium. Our hybrid scheme maintains the guarantees of each underlying building block even if the other one is broken, thus being resistant to classical and quantum attacks. Additionally, our hybrid scheme ensures that an adversary cannot derive ECDSA or Dilithium signatures that this authentication protocol considers valid. On the practical aspect, we experimentally show that our hybrid signature scheme can successfully execute on current security keys, even though secure PQC schemes are known to require substantial resources.

We publish an open-source implementation of our scheme at http://anonymous.4open.science/r/OpenSK-D018/ so that other researchers can reproduce our results on a nRF52840 development kit.
###### Ehsan Ebrahimi
ePrint Report
We say a public-key encryption is plaintext-extractable in the random oracle model if there exists an algorithm that given access to all inputs/outputs queries to the random oracles can simulate the decryption oracle. We argue that plaintext-extractability is enough to show the indistinguishably under chosen ciphertext attack (IND-CCA) of OAEP+ transform (Shoup, Crypto 2001) when the underlying trapdoor permutation is one-way.

We extend the result to the quantum random oracle model (QROM) and show that OAEP+ is IND-CCA secure in QROM if the underlying trapdoor permutation is quantum one-way.
###### Matthew Green, Mathias Hall-Andersen, Eric Hennenfent, Gabriel Kaptchuk, Benjamin Perez, Gijs Van Laer
ePrint Report
We consider the problem of proving in zero-knowledge the existence of vulnerabilities in executables compiled to run on real-world processors. We demonstrate that it is practical to prove knowledge of real exploits for real-world processor architectures without the need for source code and without limiting our consideration to narrow vulnerability classes. To achieve this, we devise a novel circuit compiler and a toolchain that produces highly optimized, non-interactive zero-knowledge proofs for programs executed on the MSP430, an ISA commonly used in embedded hardware. Our toolchain employs a highly optimized circuit compiler and a number of novel optimizations to construct efficient proofs for program binaries. To demonstrate the capability of our system, we test our toolchain by constructing proofs for challenges in the Microcorruption capture the flag exercises.
###### Ali Şah Özcan
ePrint Report
Homomorphic encryption (HE) is a cryptosystem that allows secure processing of encrypted data. One of the most popular HE schemes is the Brakerski-Fan-Vercauteren (BFV), which supports somewhat (SWHE) and fully homomorphic encryption (FHE). Since overly involved arithmetic operations of HE schemes are amenable to concurrent computation, GPU devices can be instrumental in facilitating the practical use of HE in real world applications thanks to their superior parallel processing capacity.

This paper presents an optimized and highly parallelized GPU library to accelerate the BFV scheme. This library includes state-of-the-art implementations of Number Theoretic Transform (NTT) and inverse NTT that minimize the GPU kernel function calls. It makes an efficient use of the GPU memory hierarchy and computes 128 NTT operations for ring dimension of $2^{14}$ only in $176.1~\mu s$ on RTX~3060Ti GPU. To the best of our knowlede, this is the fastest implementation in the literature. The library also improves the performance of the homomorphic operations of the BFV scheme. Although the library can be independently used, it is also fully integrated with the Microsoft SEAL library, which is a well-known HE library that also implements the BFV scheme. For one ciphertext multiplication, for the ring dimension $2^{14}$ and the modulus bit size of $438$, our GPU implementation offers $\mathbf{63.4}$ times speedup over the SEAL library running on a high-end CPU. The library compares favorably with other state-of-the-art GPU implementations of NTT and the BFV operations. Finally, we implement a privacy-preserving application that classifies encrpyted genome data for tumor types and achieve speedups of $42.98$ and $5.7$ over a CPU implementations using single and 16 threads, respectively. Our results indicate that GPU implementations can facilitate the deployment of homomorphic cryptographic libraries in real world privacy preserving applications.
###### Wonseok Choi, Hwigyeom Kim, Jooyoung Lee, Yeongmin Lee
ePrint Report
For several decades, constructing pseudorandom functions from pseudorandom permutations, so-called Luby-Rackoff backward construction, has been a popular cryptographic problem. Two methods are well-known and comprehensively studied for this problem: summing two random permutations and truncating partial bits of the output from a random permutation. In this paper, by combining both summation and truncation, we propose new Luby-Rackoff backward constructions, dubbed SaT1 and SaT2, respectively. SaT2 is obtained by partially truncating output bits from the sum of two independent random permutations, and SaT1 is its single permutation-based variant using domain separation. The distinguishing advantage against SaT1 and SaT2 is upper bounded by O(\sqrt{\mu q_max}/2^{n-0.5m}) and O({\sqrt{\mu}q_max^1.5}/2^{2n-0.5m}), respectively, in the multi-user setting, where n is the size of the underlying permutation, m is the output size of the construction, \mu is the number of users, and q_max is the maximum number of queries per user. We also prove the distinguishing advantage against a variant of XORP[3]~(studied by Bhattacharya and Nandi at Asiacrypt 2021) using independent permutations, dubbed SoP3-2, is upper bounded by O(\sqrt{\mu} q_max^2}/2^{2.5n})\$. In the multi-user setting with \mu = O(2^{n-m}), a truncated random permutation provides only the birthday bound security, while SaT1 and SaT2 are fully secure, i.e., allowing O(2^n) queries for each user. It is the same security level as XORP[3] using three permutation calls, while SaT1 and SaT2 need only two permutation calls.
###### Juan Garay, Aggelos Kiayias, Yu Shen
ePrint Report
The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates --- possibly very widely --- over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt ’21].

In this work, we present the first proof-of-work (PoW)-based permissionless clock synchronization protocol. Our construction assumes a public setup (e.g., a CRS) and relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.
###### Azam Soleimanian
ePrint Report
Random Allocation -the random assignment of the data to the parties- is a well-studied topic in the analysis of medical or judicial data, and the context of resource distribution. Random allocation reduces the chance of bias or corruption in the relevant applications, which makes the results more reliable. This is done by preventing a special or pre-planned assignment of the data to accommodate the assessment toward the desired results. This paper provides the first formal syntax and security notion of a random allocation scheme. Based on our new security notions of anonymity, confidentiality, and data-integrity, random allocation can cover more applications such as the distributed audit system where the confidentiality of data and the anonymity of auditors are of paramount importance. Our protocol allows the parties to stay anonymous during the concurrent executions of the protocol even if they have revealed themselves at a certain execution. The revelation property gives the possibility to the parties to claim certain advantages/faults at the end of a protocol-execution (without breaking the data-privacy or anonymity in other protocol-executions). We instantiate our syntax and prove the security based on simple cryptographic components and assumptions such as the Diffie-Hellman assumption, in the random oracle model.
###### Jiahui He, Kai Hu, Bart Preneel, Meiqin Wang
ePrint Report
Cube attacks exploit the algebraic properties of symmetric ciphers by recovering a special polynomial, the superpoly, and subsequently the secret key. When the algebraic normal forms of the corresponding Boolean functions are not available, the division property based approach allows to recover the exact superpoly in a clever way. However, the computational cost to recover the superpoly becomes prohibitive as the number of rounds of the cipher increases. For example, the nested monomial predictions (NMP) proposed at ASIACRYPT 2021 stuck at round 845 for Trivium. To alleviate the bottleneck of the NMP technique, i.e., the unsolvable model due to the excessive number of monomial trails, we shift our focus to the so-called valuable terms of a specific middle round that contribute to the superpoly. Two new techniques are introduced, namely, Non-zero Bit-based Division Property (NBDP) and Core Monomial Prediction (CMP), both of which result in a simpler MILP model compared to the MILP model of MP. It can be shown that the CMP technique offers a substantial improvement over the monomial prediction technique in terms of computational complexity of recovering valuable terms. Combining the divide-and-conquer strategy with these two new techniques, we catch the valuable terms more effectively and thus avoid wasting computational resources on intermediate terms contributing nothing to the superpoly. As an illustration of the power of our techniques, we apply our framework to Trivium, Grain, Kreyvium and Acorn. As a result, the computational cost of earlier attacks can be significantly reduced and the exact ANFs of the superpolies for 846-, 847- and 848-round Trivium, 192-round Grain, 895-round Kreyvium and 776-round Acorn can be recovered in practical time, even though the superpoly of 848-round Trivium contains over 500 million terms; this corresponds to respectively 3, 1, 1 and 1 rounds more than the previous best results. Moreover, by investigating the internal properties of Möbius transformation, we show how to perform key recovery using superpolies involving full key bits, which leads to the best key recovery attacks on the targeted ciphers.
###### You Lyu, Shengli Liu, Shuai Han, Dawu Gu
ePrint Report
Privacy-Preserving Authenticated Key Exchange (PPAKE) provides protection both for the session keys and the identity information of the involved parties. In this paper, we introduce the concept of robustness into PPAKE. Robustness enables each user to confirm whether itself is the target recipient of the first round message in the protocol. With the help of robustness, a PPAKE protocol can successfully avoid the heavy redundant communications and computations caused by the ambiguity of communicants in the existing PPAKE, especially in broadcast channels.

We propose a generic construction of robust PPAKE from key encapsulation mechanism (KEM), digital signature (SIG), message authentication code (MAC), pseudo-random generator (PRG) and symmetric encryption (SE). By instantiating KEM, MAC, PRG from the DDH assumption and SIG from the CDH assumption, we obtain a specific robust PPAKE scheme in the standard model, which enjoys forward security for session keys, explicit authentication and forward privacy for user identities. Thanks to the robustness of our PPAKE, the number of broadcast messages per run and the computational complexity per user are constant, and in particular, independent of the number of users in the system.

#### 14 September 2022

Eurocrypt
The Eurocrypt 2023 organizing committee is soliciting for affiliated events to be held in conjunction with Eurocrypt 2023, on Saturday, April 22 and/or Sunday, April 23, in Lyon, France.

Each such event is expected to provide a forum discussing a specific topic of the broad cryptographic world (theory, practice, implementation, standardizations, etc.). The format of the event (e.g. workshop, tutorial, etc.) is up to the organizers.

Proposals for events should be submitted by email to the Eurocrypt 2023 workshop chair at eurocrypt2023workshops@iacr.org by September 30, 2022.