International Association
for Cryptologic Research

Inserting backdoors in encryption algorithms has long seemed like a very interesting, yet difficult problem. Most attempts have been unsuccessful for symmetric-key primitives so far and it remains an open problem how to build such ciphers.

In this work, we propose the MALICIOUS framework, a new method to build tweakable block ciphers that have backdoors hidden which allows to retrieve the secret key. Our backdoor is differential in nature: a specific related-tweak differential path with high probability is hidden during the design phase of the cipher. We explain how any entity knowing the backdoor can practically recover the secret key of a user and we also argue why even knowing the presence of the backdoor and the workings of the cipher will not permit to retrieve the backdoor for an external user. We analyze the security of our construction in the classical black-box model and we show that retrieving the backdoor (the hidden high-probability differential path) is very difficult.

We instantiate our framework by proposing the LowMC-M construction, a new family of tweakable block ciphers based on instances of the LowMC cipher, which allow such backdoor embedding. Generating LowMC-M instances is trivial and the LowMC-M family has basically the same efficiency as the LowMC instances it is based on.

We introduce a category of O-oriented supersingular elliptic curves and derive properties of the associated oriented and nonoriented $\ell$-isogeny supersingular isogeny graphs. As an application we introduce an oriented supersingular isogeny Diffie-Hellman protocol (OSIDH), analogous to the supersingular isogeny Diffie-Hellman (SIDH) protocol and generalizing the commutative supersingular isogeny Diffie-Hellman (CSIDH) protocol.

The intersection of Non-commutative and Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative ring K with the unit. We consider special subsemigroups (platforms) in a semigroup of all endomorphisms of K[x_1, x_2, …, x_n]. Efficiently computed homomorphisms between such platforms can be used in Post Quantum key exchange protocols when correspondents elaborate common transformation of (K*)^n. The security of these schemes is based on a complexity of decomposition problem for an element of a semigroup into a product of given generators. We suggest three such protocols (with a group and with two semigroups as platforms) for their usage with multivariate digital signatures systems. The usage of protocols allows to convert public maps of these systems into private mode, i.e. one correspondent uses the collision map for safe transfer of selected multivariate rule to his/her partner. The ‘’ privatisation’’ of former publicly given map allows the usage of digital signature system for which some of cryptanalytic instruments were found ( estimation of different attacks on rainbow oil and vinegar system, cryptanalytic studies LUOV) with the essentially smaller size of hashed messages. Transition of basic multivariate map to safe El Gamal type mode does not allow the usage of cryptanalytic algorithms for already broken Imai - Matsumoto cryptosystem or Original Oil and Vinegar signature schemes proposed by J.Patarin. So even broken digital signatures schemes can be used in the combination with protocol execution during some restricted ‘’trust interval’’ of polynomial size. Minimal trust interval can be chosen as a dimension n of the space of hashed messages, i. e. transported safely multivariate map has to be used at most n times. Before the end of this interval correspondents have to start the session of multivariate protocol with modified multivariate map. The security of such algorithms rests not on properties of quadratic multivariate maps but on the security of the protocol for the map delivery and corresponding NP hard problem.

We report the successful recovery of the key to a Zip archive containing only two encrypted files. The attack improves on our 2001 ciphertext-only attack, which required five encrypted files. The main innovations are a new differential meet-in-the-middle attack for the initial stages and the use of lattice reduction to recover the internal state of the truncated linear congruential generator.

Election verifiability aims to ensure that the outcome produced by electronic voting systems correctly reflects the intentions of eligible voters, even in the presence of an adversary that may corrupt various parts of the voting infrastructure. Protecting such systems from manipulation is challenging because of their distributed nature involving voters, election authorities, voting servers and voting platforms. An adversary corrupting any of these can make changes that, individually, would go unnoticed, yet in the end will affect the outcome of the election. It is, therefore, important to rigorously evaluate whether the measures prescribed by election verifiability achieve their goals.

We propose a formal framework that allows such an evaluation in a systematic and automated way. We demonstrate its application to the verification of various scenarios in Helios and Belenios, two prominent internet voting systems. For Helios, our analysis is the first one to be, at the same time, fully automated (with the Tamarin protocol prover) and to precisely capture its end-to-end verifiability guarantees, allowing us to derive new security proofs and new attacks on deployed versions of it. For Belenios, similarly, we capture precisely the end-to-end verifiability guarantees when all election authorities are corrupted, which is outside the scope of previous formal definitions. We also find new attacks that apply in weaker corruption scenarios that are expected to be secure. In general, our framework allows a unified analysis and comparison of cryptographic voting protocols, corruption scenarios and verifiability procedures towards ensuring the end goal of election integrity.

The lightweight block cipher PRESENT has become viable for areas like IoT (Internet of Things) and RFID tags, due to its compact design and low power consumption, while providing a sufficient level of security for the aforementioned applications. However, the key scheduling algorithm of a cipher plays a major role in deciding how secure it is. In this paper we test the strength of the key scheduling algorithm (KSA) of the 80-bit key length variant of PRESENT by attempting to retrieve the main key register from the final round key register, using deep learning.

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors ($\mathsf{LWE}$) assumption. For a circuit $C:\{0,1\}^N\rightarrow\{0,1\}$ of size $S$ and depth $D$, the prover runs in time $\mathsf{poly}(S)$, the communication complexity is $D \cdot \mathsf{polylog} (S)$, and the verifier runs in time $(D+N) \cdot \mathsf{polylog} (S)$.

To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the $\mathsf{GKR}$ protocol, assuming the sub-exponential hardness of $\mathsf{LWE}$.

By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $\mathsf{PPAD}$, assuming the sub-exponential hardness of $\mathsf{LWE}$.

Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature $\sigma$ on a message $m$ under a public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent message $m'$ under an equivalent public key $\mathsf{pk}'$ for an appropriate notion of equivalence. For example, $\mathsf{pk}$ and $\mathsf{pk}'$ may be unlinkable pseudonyms of the same user, and $m$ and $m'$ may be unlinkable pseudonyms of a user to whom some capability is delegated.

The only previously known construction of mercurial signatures suffers a severe limitation: in order to sign messages of length $n$, the signer's public key must also be of length $n$. In this paper, we eliminate this restriction and provide a signing protocol that admits messages of any length. This significantly improves the applicability of mercurial signatures to chains of anonymous credentials.

We propose a new cryptanalytic technique and key recovery attack for the Sparx cipher, Partly-Pseudo-Linear Cryptanalysis, a meet-in-the-middle attack combining linear and pseudo-linear approximations. We observe improvements over the linear hull attacks in the literature for Sparx 128/128 and 128/256. Additionally, we generate another attack for comparison purposes, using the Cho-Pieprzyk property for a fully-linear approximation and a corresponding key recovery attack. We observe improvements on the data complexity, bias, and number of recovered key bits, over all variants of Sparx, when compared to the use of only the Cho-Pieprzyk approximation.

The deep learning-based side-channel analysis represents a powerful and easy to deploy option for profiled side-channel attacks. A detailed tuning phase is often required to reach a good performance where one first needs to select relevant hyperparameters and then tune them. A common selection for the tuning phase are hyperparameters connected with the neural network architecture, while those influencing the training process are less explored. In this work, we concentrate on the optimizer hyperparameter, and we show that this hyperparameter has a significant role in the attack performance. Our results show that common choices of optimizers (Adam and RMSprop) indeed work well, but they easily overfit, which means that we must use short training phases, small profiled models, and explicit regularization. On the other hand, SGD type of optimizers works well on average (slower convergence and less overfit), but only if momentum is used. Finally, our results show that Adagrad represents a strong option to use in scenarios with longer training phases or larger profiled models.

Fitzi, Garay, Maurer, and Ostrovsky (Journal of Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we introduce a new $2$-party primitive $\mathcal{F}_{\mathsf{SyX}}$ (``synchronizable fair exchange'') and show that it is complete for realizing any $n$-party functionality with fairness in a setting where all $n$ parties are pairwise connected by independent instances of $\mathcal{F}_{\mathsf{SyX}}$.

In the $\mathcal{F}_{\mathsf{SyX}}$-hybrid model, the two parties load $\mathcal{F}_{\mathsf{SyX}}$ with some input, and following this, either party can trigger $\mathcal{F}_{\mathsf{SyX}}$ with a suitable ``witness'' at a later time to receive the output from $\mathcal{F}_{\mathsf{SyX}}$. Crucially the other party also receives output from $\mathcal{F}_{\mathsf{SyX}}$ when $\mathcal{F}_{\mathsf{SyX}}$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $\mathcal{F}_{\mathsf{SyX}}$, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $\mathcal{F}_{\mathsf{SyX}}$ in any number of multiparty protocols (possibly involving different sets of parties).

We design Aardvark, a novel authenticated dictionary backed by vector commitments with short proofs. Aardvark guarantees the integrity of outsourced data by providing proofs for lookups and modifications, even when the servers storing the data are untrusted. To support high-throughput, highly-parallel applications, Aardvark includes a versioning mechanism that allows the dictionary to accept stale proofs for a limited time.

We apply Aardvark to the problem of decoupling storage from transaction verification in cryptocurrencies. Here networking resources are at a premium and transmission of long proofs can easily become the dominant cost, with multiple users reading and writing concurrently.

We implement Aardvark and evaluate it as a standalone authenticated dictionary. We show that Aardvark saves substantial storage resources while incurring limited extra bandwidth and processing costs.

Modern public key encryption relies on various hardness assumptions for its security. Hardness assumptions may cause security uncertainty, for instance, when a hardness problem is no longer hard or the best solution to a hard problem might not be publicly released.

In this paper, we propose a public key encryption scheme Compact-LWE-MQ^{H} to demonstrate the feasibility of designing public key encryption without relying on hardness assumptions. Instead, its security is based on problems that are called factually hard.The two factually hard problems we proposed in this work are stratified system of linear and quadratic equations, and learning with relatively big errors. Such factually hard problems have the structures to ensure that they can only be solved by exhaustively searching their solution spaces, even when the problem size is very small.

Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or private key components, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} in SageMath. In a configuration for 128-bit security level, the public key has 3708 bytes and a ciphertext is around 574 bytes.

Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that it is necessary to transmit the entire GC during 2PC, even for conditional branches that are not taken.

This folklore belief is false.

We propose a novel GC technique, stacked garbling, that eliminates the communication cost of inactive conditional branches. We extend the ideas of conditional GC evaluation explored in (Kolesnikov, Asiacrypt 18) and (Heath and Kolesnikov, Eurocrypt 20). Unlike these works, ours is for general 2PC where no player knows which conditional branch is taken.

Our garbling scheme, Stack, requires communication proportional to the longest execution path rather than to the entire circuit. Stack is compatible with state-of-the-art techniques, such as free XOR and half-gates.

Stack is a garbling scheme. As such, it can be plugged into a variety of existing protocols, and the resulting round complexity is the same as that of standard GC. The approach does incur computation cost quadratic in the conditional branching factor vs linear in standard schemes, but the tradeoff is beneficial for most programs: GC computation even on weak hardware is faster than GC transmission on fast channels.

We implemented Stack in C++. Stack reduces communication cost by approximately the branching factor: for 16 branches, communication is reduced by 10.5x. In terms of wall-clock time for circuits with branching factor 16 over a 50 Mbps WAN on a laptop, Stack outperforms state-of- the-art half-gates-based 2PC by more than 4x.

In this short note, we describe a practical optimization of the well-known extended binary GCD algorithm, for the purpose of computing modular inverses. The method is conceptually simple and is applicable to all odd moduli (including non-prime moduli). When implemented for inversion in the field of integers modulo the prime $2^{255}-19$, on a recent x86 CPU (Coffee Lake core), we compute the inverse in 7490 cycles, with a fully constant-time implementation.

Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true.

We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bits albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing.

We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function $f(x) = ax + b$, where a sender inputs the field elements $a,b$, and a receiver inputs $x$ and learns $f(x)$. OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more.

In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al., Eurocrypt 2019), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al., Crypto 2018), and design new variants of zero-knowledge arguments that are necessary for some of our constructions.

Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where $b$ is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring $\mathbb{Z}_m$, for a 120-bit modulus $m$, on standard hardware.

Let $\mathbb{F}_{\!p}$ be a prime finite field ($p > 5$) and $E_b\!: y_0^2 = x_0^3 + b$ be an elliptic $\mathbb{F}_{\!p}$-curve of $j$-invariant $0$. In this article we produce the simplified SWU hashing to curves $E_b$ having an $\mathbb{F}_{\!p^2}$-isogeny of degree $5$. This condition is fulfilled for some Barreto--Naehrig curves, including BN512 from the standard ISO/IEC 15946-5. Moreover, we show how to implement the simplified SWU hashing in constant time (for any $j$-invariant), namely without quadratic residuosity tests and inversions in $\mathbb{F}_{\!p}$. Thus in addition to the protection against timing attacks, the new hashing $h\!: \mathbb{F}_{\!p} \to E_b(\mathbb{F}_{\!p})$ turns out to be much more efficient than the (universal) SWU hashing, which generally requires to perform $2$ quadratic residuosity tests.

Presenting a new technology to fit quantum-randomness into a lump of matter where the randomness is held through the molecular bonds of seeded macro-molecules, and reliably measured in two or more sufficiently exact duplicates, serving as a large reservoir for quantum-grade randomness to support cryptographic protocols.

We have (fully funded) multiple PhD positions in the areas of applied cryptography beginning from Fall 2021 (August 2021) or Spring 2021 (January 2021) at University of South Florida (USF). USF is a Rank-1 Research University (rank 31 of CS departments at US public universities per according Academic Analytics on Scholarly Research Index) and offers a competitive salary with an excellent working environment, all within close proximity of high-tech industry and beautiful beaches of Sunny Florida. Tampa/Orlando area is a key part of the Florida High Technology Corridor and harbors major tech and research companies. The qualified candidate will have opportunities for research internship and joint-projects with lead-industrial companies. Topics include:

Trustworthy and Scalable Blockchains

• New cryptographic schemes for consensus and distributed transactions in Blockchains
• Practical quantum-safe cryptographic deployments for Blockchains

Secure and Reliable Internet of Things and Systems (IoT)

• Lightweight cryptography for IoT
• Efficient cryptography for vehicular and unmanned aerial systems
• Efficient digital signatures

Privacy-Enhancing Technologies

• Searchable encryption, Oblivious RAM, and multi-party computation

Trustworthy Machine Learning (TML)

• Privacy-Preserving Machine Learning
• Adversarial Machine Learning

Requirements:

• A BS degree in ECE/CS with a high-GPA
• Very good programming skills (e.g., C, C++), familiarity with Linux
• MS degree in ECE/CS/Math is a big plus. Publications in security and privacy are highly desirable

Please send (by e-mail) to below contact information:

• Transcripts
• Curriculum vitae
• Three reference letters (send by referees)
• Research statement
• GRE and TOEFL

Closing date for applications:

Contact: Dr. Attila A. Yavuz
Email: attilaayavuz@usf.edu
Webpage : http://www.csee.usf.edu/~attilaayavuz/

More information: http://www.csee.usf.edu/~attilaayavuz/article/PositionDescrption_at_USF.pdf