International Association
for Cryptologic Research

Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth's coefficient-product argument (JOC, 2010). Additionally, we use batching techniques. The resulting shuffle argument is the fastest known $\leq 5$-message shuffle argument, and, depending on the implementation, can be faster than Groth's argument (the fastest 7-message shuffle argument).

Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC ’07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX ’16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.

An algebraic differential fault attack (ADFA) is an attack in which an attacker combines a differential fault attack and an algebraic technique to break a targeted cipher. In this paper, we present three attacks using three different algebraic techniques combined with a differential fault attack in the bit-flip fault model to break the SIMON block cipher. First, we introduce a new analytic method that is based on a differential trail between the correct and faulty ciphertexts. This method is able to recover the entire master key of any member of the SIMON family by injecting faults into a single round of the cipher. In our second attack, we present a simplified Grobner basis algorithm to solve the faulty system. We show that this method could totally break SIMON ciphers with only 3 to 5 faults injected. Our third attack combines a fault attack with a modern SAT solver. By guessing some key bits and with only a single fault injected at the round T - 6, where T is the number of rounds of a SIMON cipher, this combined attack could manage to recover a master key of the cipher. For the last two attacks, we perform experiments to demonstrate the effectiveness of our attacks. These experiments are implemented on personal computers and run at very reasonable timing

Anonymous routing is one of the most fundamental online privacy problems and has been studied extensively for decades. Almost all known approaches for anonymous routing (e.g., mix-nets, DC-nets, and others) rely on multiple servers or routers to engage in some {\it interactive} protocol; and anonymity is guaranteed in the {\it threshold} model, i.e., if one or more of the servers/routers behave honestly.

Departing from all prior approaches, we propose a novel {\it non-interactive} abstraction called a Non-Interactive Anonymous Router (NIAR), which works even with a {\it single untrusted router}. In a NIAR scheme, suppose that $n$ senders each want to talk to a distinct receiver. A one-time trusted setup is performed such that each sender obtains a sending key, each receiver obtains a receiving key, and the router receives a {\it token} that ``encrypts'' the permutation mapping the senders to receivers. In every time step, each sender can encrypt its message using its sender key, and the router can use its token to convert the $n$ ciphertexts received from the senders to $n$ {\it transformed ciphertexts}. Each transformed ciphertext is delivered to the corresponding receiver, and the receiver can decrypt the message using its receiver key. Imprecisely speaking, security requires that the untrusted router, even when colluding with a subset of corrupt senders and/or receivers, should not be able to compromise the privacy of honest parties, including who is talking to who, and the message contents.

We show how to construct a communication-efficient NIAR scheme with provable security guarantees based on the standard Decisional Linear assumption in suitable bilinear groups. We show that a compelling application of NIAR is to realize a Non-Interactive Anonymous Shuffler (NIAS), where an untrusted server or data analyst can only decrypt a permuted version of the messages coming from $n$ senders where the permutation is hidden. NIAS can be adopted to construct privacy-preserving surveys, differentially private protocols in the shuffle model, and pseudonymous bulletin boards.

Besides this main result, we also describe a variant that achieves fault tolerance when a subset of the senders may crash. Finally, we further explore a paranoid notion of security called full insider protection, and show that if we additionally assume sub-exponentially secure Indistinguishability Obfuscation and as sub-exponentially secure one-way functions, one can construct a NIAR scheme with paranoid security.

The random probing model is a leakage model in which each wire of a circuit leaks with a given probability $p$. This model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the right formalization for power and electromagnetic side-channel attacks. In addition, the random probing model is much more convenient than the noisy leakage model to prove the security of masking schemes. In a recent work, Ananth, Ishai and Sahai (CRYPTO 2018) introduce a nice expansion strategy to construct random probing secure circuits. Their construction tolerates a leakage probability of $2^{-26}$, which is the first quantified achievable leakage probability in the random probing model. In a follow-up work, Bela\"id, Coron, Prouff, Rivain and Taleb (CRYPTO 2020) generalize their idea and put forward a complete and practical framework to generate random probing secure circuits. The so-called expanding compiler can bootstrap simple base gadgets as long as they satisfy a new security notion called random probing expandability (RPE). They further provide an instantiation of the framework which tolerates a $2^{-8}$ leakage probability in complexity $\mathcal{O}(\kappa^{7.5})$ where $\kappa$ denotes the security parameter.

In this paper, we provide an in-depth analysis of the RPE security notion. We exhibit the first upper bounds for the main parameter of a RPE gadget, which is known as the amplification order. We further show that the RPE notion can be made tighter and we exhibit strong connections between RPE and the strong non-interference (SNI) composition notion. We then introduce the first generic constructions of gadgets achieving RPE for any number of shares and with nearly optimal amplification orders and provide an asymptotic analysis of such constructions. Last but not least, we introduce new concrete constructions of small gadgets achieving maximal amplification orders. This allows us to obtain much more efficient instantiations of the expanding compiler: we obtain a complexity of $\mathcal{O}(\kappa^{3.9})$ for a slightly better leakage probability, as well as $\mathcal{O}(\kappa^{3.2})$ for a slightly lower leakage probability.

In the quantum random oracle model, the adversary may make quantum superposition queries to the random oracle. Since even a single query can potentially probe exponentially many points, classical proof techniques are hard to apply. For example, recording the oracle queries seemed difficult.

In 2018, Mark Zhandry showed that, despite the apparent difficulties, it is in fact possible to ‘record’ the quantum queries. He has defined the compressed oracle, which is indistinguishable from the quantum random oracle, and records information the adversary has gained through the oracle queries. It is a technically subtle work, which we believe to be a challenging work to grasp fully.

Our aim is to obtain a mathemathically clean, simple reinterpretation of the compressed oracle technique. For each partial function, we define what we call the formation and the completion of that partial function. The completions describe what happens to the real quantum random oracle, and the formations describe what happens to the compressed oracle. We will show that the formations are 'isomorphic' to the completions, giving an alternative proof that the compressed oracle is indistinguishable from the quantum random oracle.

We present a novel protocol XORBoost for both training gradient boosted tree models and for using these models for inference in the multiparty computation (MPC) setting. Similarly to [AEV20], our protocol is the first one supporting training for generically split datasets (vertical and horizontal splitting, or combination of those) while keeping all the information about the features and thresholds associated with the nodes private, thus, having only the depths and the number of the binary trees as public parameters of the model. By using optimization techniques reducing the number of oblivious permutation evaluations as well as the quicksort and real number arithmetic algorithms from the recent Manticore MPC framework [CDG+21], we obtain a scalable implementation operating under information-theoretic security model in the honest-but-curious setting with a trusted dealer. On a training dataset of 25,000 samples and 300 features in the 2-player setting, we are able to train 10 regression trees of depth 4 in less than 5 minutes per tree (using histograms of 128 bins).

We consider the problem of round-optimal unbounded MPC: in the first round, parties publish a message that depends only on their input. In the second round, any subset of parties can jointly and securely compute any function $f$ over their inputs in a single round of broadcast. We do not impose any a-priori bound on the number of parties nor on the size of the functions that can be computed. Our main result is a semi-malicious two-round protocol for unbounded MPC in the plain model from the hardness of the standard learning with errors (LWE) problem. Prior work in the same setting assumes the hardness of problems over bilinear maps. Thus, our protocol is the first example of unbounded MPC that is post-quantum secure. The central ingredient of our protocol is a new scheme of attribute-based secure function evaluation (AB-SFE) with public decryption. Our construction combines techniques from the realm of homomorphic commitments with delegation of lattice basis. We believe that such a scheme may find further applications in the future.

The Kannan-Fincke-Pohst lattice enumeration algorithm is the classical method for solving the shortest vector problem in lattices. It is also a fundamental tool for most lattice reduction algorithms that provide speed-length tradeoffs. As this algorithm allows efficient parallel implementations, it is likely that implementing it on modern graphics processing units (GPUs) can significantly improve performance. We provide such an implementation that is compatible with the fplll lattice reduction library [fplll16] and achieves a considerable speedup in higher lattice dimensions, compared to current, multithreaded versions. For this, we use the CUDA technology that provides an abstract language for programming GPUs.

[fplll16] The FPLLL development team. “fplll, a lattice reduction library”. 2016. URL: https://github.com/fplll/fplll

Multivariate cryptography is dominated by schemes supporting various tweaks, or ``modifiers,'' designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature--- either requiring an extra composition with an affine map, or being evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers.

In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.

We formally prove that the C implementation of the X25519 key-exchange protocol in the TweetNaCl library is correct. We prove both that it correctly implements the protocol from Bernstein's 2006 paper, as standardized in RFC 7748, as well as the absence of undefined behavior like arithmetic overflows and array out-of-bounds errors. We also formally prove, based on the work of Bartzia and Strub, that X25519 is mathematically correct, i.e., that it correctly computes scalar multiplication on the elliptic curve Curve25519.

The proofs are all computer-verified using the Coq theorem prover. To establish the link between C and Coq we use the Verified Software Toolchain (VST).

At EUROCRYPT 2021, Bao et al. proposed an automatic method for systematically exploring the configuration space of meet-in-the-middle (MITM) preimage attacks. We further extend it into a constraint-based framework for finding exploitable MITM characteristics in the context of key-recovery and collision attacks by taking the subtle peculiarities of both scenarios into account. Moreover, to perform attacks based on MITM characteristics with nonlinear constrained neutral words, which have not been seen before, we present a procedure for deriving the solution spaces of neutral words without solving the corresponding nonlinear equations or increasing the overall time complexities of the attack. We apply our method to concrete symmetric-key primitives, including SKINNY, ForkSkinny, Romulus, Saturnin, Grostl, Whirlpool, and hashing modes with AES-256. As a result, we identify the first 23-round key-recovery attack on SKINNY-$n$-$3n$ and the first 24-round key-recovery attack on ForkSkinny-$n$-$3n$ in the single-key model with extremely low memories. Moreover, improved (pseudo) preimage or collision attacks on round-reduced Whirlpool, Grostl, and hashing modes with AES-256 are obtained. In particular, employing the new representation of the \texttt{AES} key schedule due to Leurent and Pernot (EUROCRYPT 2021), we identify the first preimage attack on 10-round \texttt{AES}-256.

Given two ciphertexts generated with a public-key encryption scheme, the problem of plaintext equality consists in determining whether the ciphertexts hold the same value. Similarly, the problem of plaintext inequality consists in deciding whether they hold a different value. Previous work has focused on building new schemes or extending existing ones to include support for plaintext equality/inequality. We propose generic and simple zero-knowledge proofs for both problems, which can be instantiated with various schemes. First, we consider the context where a prover with access to the secret key wants to convince a verifier, who has access to the ciphertexts, on the equality/inequality without revealing information about the plaintexts. We also consider the case where the prover knows the encryption’s randomness instead of the secret key. For plaintext equality, we also propose sigma protocols that lead to non-interactive zero-knowledge proofs. To prove our protocols’ security, we formalize notions related to malleability in the context of public-key encryption and provide definitions of their own interest.

We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with n < m. This includes Expanding Feistel Networks (EFNs) that purely rely on such expanding round functions, and Alternating Feistel Networks (AFNs) that alternate expanding and contracting round functions. We show that, when two independent keys $K_1,K_2$ are alternatively used in each round, (a) $2\lceil\frac{m}{n}\rceil+2$ rounds are sufficient for related-key security of EFNs, and (b) a constant number of 4 rounds are sufficient for related-key security of AFNs. Our results complete the picture of provable related-key security of GFNs, and provide additional theoretical support for the AFN-based NIST format preserving encryption standards FF1 and FF3.

As people become more and more privacy conscious, the need for end-to-end encryption (E2EE) has become widely recognized. We study the security of SFrame, an E2EE mechanism recently proposed to IETF for video/audio group communications over the Internet. Although a quite recent project, SFrame is going to be adopted by a number of real-world applications. We inspected the original specification of SFrame. We found a critical issue that will lead to an impersonation (forgery) attack by a malicious group member with a practical complexity. We also investigated the several publicly-available SFrame implementations, and confirmed that this issue is present in these implementations.

Large semigroups and groups of transformations of finite affine space of dimension n with the option of computability of the composition of n arbitrarily chosen elements in polynomial time are described in the paper. Constructions of such families are given together with effectively computed homomorphisms between members of the family. These algebraic platforms allow us to define protocols for several generators of subsemigroup of affine Cremona semigroups with several outputs. Security of these protocols rests on the complexity of the word decomposition problem, It allows to introduce algebraic protocols expanded to cryptosystems of El Gamal type which are not a public key system. In particular symbiotic combination of these protocol of Noncommutative cryptography with one time pad encryption is given. Some of these nonclassical multivariate cryptosystems are implemented with platforms of cubical transformations.

Micro-architectural timing channels are one of the most popular side channels in modern processors exploited by attackers. The presence of such timing channels enables attackers to recover sensitive information by exploiting dynamic software properties (e.g. time, cache misses, and memory access statistics). In the recent decade, the security research community has identified numerous shreds of evidence of practical timing attacks, with more recent and critical attacks reflected in Spectre, and Meltdown. In this project, we will design a secure processor against timing side channels. Our goal is to use a set of ML and computer architecture techniques to propose a countermeasure to deal with realistic timing-channel attacks. SOC group at the National University of Singapore(NUS) opens a few positions for post-doc researchers and Ph.D. on the topic of Timing side channels. We are looking for team players who are motivated and able to drive top-quality research. The area of research lies between several fields and we expect in some of the following fields: • Micro-architecture • Side-channel analysis • Machine learning • Security We will look for applications until the positions are filled. However, prospective applicants are highly encouraged to submit their applications by 31st May 2021. As one of the top universities in the world for computer science (Ranked number 4), NUS provides excellent future career training and opportunities, research environment, and facilities to international and national academic researchers. Competitive salary, tax benefit, and welfare package will be provided. Note the start date of the post-doc and Ph.D. could be flexible but no later than the end of this year (2021). Applicants should prepare and send their CV and cover letter to the following contact email.

Closing date for applications:

Contact: Arash Pashrashid (pashrashid.arash@u.nus.edu)

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography. The student is expected to work on topics that include security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The position is funded with a competitive salary.
Research area: Research areas include but are not limited to:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Your Profile:

• A MsC degree in Computer Science, Applied Mathematics or a relevant field;
• Strong mathematical and algorithmic CS background;
• Excellent programming skills;
• Excellent written and verbal communication skills in English

Final Deadline for applications: 15 April 2021
Starting date: By mutual agreement
Apply online: https://jobs.unisg.ch/offene-stellen/phd-position-in-applied-cryptography-and-information-security-m-w-d/09f75f22-649c-48a6-9aa4-659bbd686a84

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/phd-position-in-applied-cryptography-and-information-security-m-w-d/09f75f22-649c-48a6-9aa4-659bbd686a84

The Applied Cryptography Lab at the Friedrich-Alexander-University Erlangen-Nürnberg (FAU) invites applications for a Post-doc position. We are interested in the theory and application of provably secure cryptography. Topics of interest include (but are not limited to):

• privacy-enhancing-technologies
• cryptocurrencies
• password-based cryptography
• proof systems

Work Environment: The Applied Cryptography Lab is part of FAU, which is one of the largest universities in Germany. With its five faculties, FAU offers a scope of subjects ranging from the Humanities to Law and Economics as well as Sciences, Medicine, and Engineering. FAU’s mission statement “Advance through Networks” reflects the close collaboration between the single disciplines. FAU has been ranked the third year in a row the most innovative University in Germany.

Requirements: Candidates for this position should hold a Ph.D. degree in Computer Science or a related discipline (mathematics, ...). The ideal candidate shows strong enthusiasm about research, publishes at leading venues in cryptography or IT security, and has excellent teamworking abilities.

Program details and contact for application/questions: Funding is available for at least 36 months; the salary range is between 32.671 - 78.136 EUR year, depending on your background and experience. Prospective applicants should apply with a cover letter, a research statement, and an academic CV that includes the contact information for two references. Please send a single PDF file and include [PostDoc] in the subject. Applications will be accepted until the position is filled.

Closing date for applications:

Contact: Dominique Schroeder

More information: https://www.chaac.tf.fau.eu

The Applied Cryptography Lab at the Friedrich-Alexander-University Erlangen-Nürnberg (FAU) invites applications for a Ph.D. position in Computer Science. We are interested in the theory and application of provably secure cryptography. Topics of interest include (but are not limited to):

• privacy-enhancing-technologies
• cryptocurrencies
• password-based cryptography
• proof systems

Work Environment: The Applied Cryptography Lab is part of FAU, which is one of the largest universities in Germany. With its five faculties, FAU offers a scope of subjects ranging from the Humanities to Law and Economics as well as Sciences, Medicine, and Engineering. FAU’s mission statement “Advance through Networks” reflects the close collaboration between the single disciplines. FAU has been ranked the third year in a row the most innovative University in Germany.

Requirements: Candidates for this position should have a master or comparable degree in Computer Science or a related discipline (mathematics, ...). Knowledge of one or several of the areas cryptography, IT security, complexity theory, privacy,... is desired. The ideal candidate shows strong enthusiasm about research and has excellent teamworking abilities.

Program details and contact for application/questions: The project start date is as soon as possible. Funding is available for at least 36 months; an extension is possible. Prospective applicants should apply with a cover letter, a list of attended (Master) courses, and an academic CV. Please send a single PDF file and include [PhD] in the subject. Applications will be accepted until the position is filled.

Closing date for applications:

Contact: Dominique Schröder

More information: https://www.chaac.tf.fau.eu