International Association
for Cryptologic Research

Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. The predictability of truncated sequences that predict the whole sequences by the truncated high-order bits of the sequences is not only a crucial aspect of evaluating the security of pseudorandom number generators but also serves an important role in the design of pseudorandom number generators. This paper improves the work of Sun et al on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we adopt the resultant, the Chinese Remainder Theorem and the idea of recovering $p$-adic coordinates of the coefficients layer by layer, and Kannan's embedding technique to recover the modulus, the coefficients and the initial state, respectively. Experimental results show that our new method is superior to that of the work of Sun et al, no matter in terms of the running time or the number of truncated digits required.

Cloud storage provides highly available and low cost resources to users. However, as massive amounts of outsourced data grow rapidly, an effective data deduplication scheme is necessary. This is a hot and challenging field, in which there are quite a few researches. However, most of previous works require dual-server fashion to be against brute-force attacks and do not support batch checking. It is not practicable for the massive data stored in the cloud. In this paper, we present a secure batch deduplication scheme for backup system. Besides, our scheme resists the brute-force attacks without the aid of other servers. The core idea of the batch deduplication is to separate users into different groups by using short hashes. Within each group, we leverage group key agreement and symmetric encryption to achieve secure batch checking and semantically secure storage. We also extensively evaluate its performance and overhead based on different datasets. We show that our scheme saves the data storage by up to 89.84%. These results show that our scheme is efficient and scalable for cloud backup system and can also ensure data confidentiality.

Elections are an important corner stone of democratic processes. In addition to publishing the final result (e.g., the overall winner), elections typically publish the full tally consisting of all (aggregated) individual votes. This causes several issues, including loss of privacy for both voters and election candidates as well as so-called Italian attacks that allow for easily coercing voters.

Several e-voting systems have been proposed to address these issues by hiding (parts of) the tally. This property is called tally-hiding. Existing tally-hiding e-voting systems in the literature aim at hiding (part of) the tally from everyone, including voting authorities, while at the same time offering verifiability, an important and standard feature of modern e-voting systems which allows voters and external observers to check that the published election result indeed corresponds to how voters actually voted. In contrast, real elections often follow a different common practice for hiding the tally: the voting authorities internally compute (and learn) the full tally but publish only the final result (e.g., the winner). This practice, which we coin publicly tally-hiding, indeed solves the aforementioned issues for the public, but currently has to sacrifice verifiability due to a lack of practical systems.

In this paper, we close this gap. We formalize the common notion of publicly tally-hiding and propose the first provably secure verifiable e-voting system, called Kryvos, which directly targets publicly tally-hiding elections. We instantiate our system for a wide range of both simple and complex voting methods and various result functions. We provide an extensive evaluation which shows that Kryvos is practical and able to handle a large number of candidates, complex voting methods and result functions. Altogether, Kryvos shows that the concept of publicly tally-hiding offers a new trade-off between privacy and efficiency that is different from all previous tally-hiding systems and which allows for a radically new protocol design resulting in a practical e-voting system.

Observation and manipulation of physical characteristics are well-known and powerful threats to cryptographic devices. While countermeasures against passive side-channel and active fault-injection attacks are well understood individually, combined attacks, i.e., the combination of fault injection and side-channel analysis, is a mostly unexplored area. Naturally, the complexity of analysis and secure construction increases with the sophistication of the adversary, making the combined scenario especially challenging. To tackle complexity, the side-channel community has converged on the construction of small building blocks, which maintain security properties even when composed. In this regard, Probe-Isolating Non-Interference (PINI) is a widely used notion for secure composition in the presence of side-channel attacks due to its efficiency and elegance. In this work, we transfer the core ideas behind PINI to the context of fault and combined security and, from that, construct the first trivially composable gadgets in the presence of a combined adversary.

During the last decades, many advances in the field of automated security protocol analysis have seen the field mature and grow from being applicable to toy examples, to modeling intricate protocol standards and finding real-world vulnerabilities that extensive manual analysis had missed.

However, modern security protocols often contain elements for which such tools were not originally designed, such as protocols that construct, by design, terms of unbounded size, such as counters, trees, and blockchains. Protocol analysis tools such as Tamarin and ProVerif have some very restricted support, but typically lack the ability to effectively reason about dynamically growing unbounded-depth terms.

In this work, we introduce subterm-based proof techniques that are tailored for automated protocol analysis in the Tamarin prover. In several case studies, we show that these techniques improve automation (allow for analyzing more protocols, or remove the need for manually specified invariants), efficiency (reduce proof size for existing analyses), and expressive power (enable new kinds of properties). In particular, we provide the first automated proofs for TreeKEM, S/Key, and Tesla Scheme~2; and we show substantial benefits, most notably in WPA2 and 5G-AKA, two of the largest automated protocol proofs.

Microarchitectural attacks utilize the performance optimization constructs that have been studied over decades in computer architecture research and show the vulnerability of such optimizations in a realistic framework. One such highly performance driven vulnerable construct is speculative execution. In this paper, we focus on the problem of breaking the kernel address-space layout randomization (KASLR) on modern mobile devices without using cache memory as a medium of observation. However, there are some challenges to breaking KASLR on ARM CPUs. The first challenge is that eviction strategies on ARM CPUs are slow, and the microarchitectural attacks exploiting the cache as a covert channel cannot be implemented on modern ARM CPUs. The second challenge is that non-canonical addresses are stored in the store buffer, although they are invalid. As a result, previous microarchitectural attacks distinguish such addresses as valid kernel addresses erroneously. In this paper, we focus on these challenges to close current gaps in the implementation of recent attacks against modern CPUs. We show how a Translation Look-aside Buffer (TLB) can be used to circumvent the cache memory as a covert channel in order to attack ASLR on both ARM and Intel CPUs. To the best of our knowledge, we are the first to break KASLR on ARM-based Android and iOS mobile devices. Furthermore, our attacks can be performed in JavaScript to break KASLR of the browser without the need for an Evict+Reload operation, which consumes a lot of time. The results of our attacks show that the attacker can distinguish whether or not the virtual address is valid in less than 0.0417 seconds and 0.0488 seconds on Android and iOS mobile devices, respectively.

In the current paper we investigate the possibility of designing secure blind signature scheme based on ElGamal signature equation. We define the generalized construction and analyze its security. We consider two types of schemes with the proposed construction, that cover all existing schemes. For schemes of the first type we provide generic ROS-style attack that violates unforgeability in the parallel setting. For schemes of the second type we prove that they do not provide either blindness, or unforgeability. As the result, we prove that all known ElGamal blind signature schemes are not secure. Moreover, these results show that the existence of secure ElGamal blind signature scheme is potentially possible only for small set of signature equations and requires the non-standard way of generating the first component of the signature.

In the UC framework, a protocol must be subroutine respecting; therefore, shared trusted setup might cause security issues. To address this drawback, Generalized UC (GUC) framework is introduced by Canetti et al. (TCC 2007). In this work, we investigate the impossibility and feasibility of GUC-secure commitments with global random oracles (GRO) as trusted setup. In particular, we show it is impossible to have a 2-round (1 round for the committing phase and 1 round for the opening phase) GUC-secure commitment in the global observable RO model by Canetti et al. (CCS 2014). We then give a new round-optimal GUC-secure commitment that uses only MiniCrypt assumptions (i.e. the existence of one-way functions) in the global observable RO model. In addition, we also examine the complete picture on round complexity of the GUC-secure commitments in various global RO models.

During the last five decades, many different secondary constructions of bent functions were proposed in the literature. Nevertheless, apart from a few works, the question about the class inclusion of bent functions generated using these methods is rarely addressed. Especially, if such a ``new'' family belongs to the completed Maiorana-McFarland ($\mathcal{MM}^\#$) class then there is no proper contribution to the theory of bent functions. In this article, we provide some fundamental results related to the inclusion in $\mathcal{MM}^\#$ and eventually we obtain many infinite families of bent functions that are provably outside $\mathcal{MM}^\#$. The fact that a bent function $f$ is in/outside $\mathcal{MM}^\#$ if and only if its dual is in/outside $\mathcal{MM}^\#$ is employed in the so-called 4-decomposition of a bent function on $\mathbb{F}_2^n$, which was originally considered by Canteaut and Charpin \cite{Decom} in terms of the second-order derivatives and later reformulated in \cite{HPZ2019} in terms of the duals of its restrictions to the cosets of an $(n-2)$-dimensional subspace $V$. For each of the three possible cases of this 4-decomposition of a bent function (all four restrictions being bent, semi-bent, or 5-valued spectra functions), we provide generic methods for designing bent functions provably outside $\mathcal{MM}^\#$. For instance, for the elementary case of defining a bent function $h(\mathbf{x},y_1,y_2)=f(\mathbf{x}) \oplus y_1y_2$ on $\mathbb{F}_2^{n+2}$ using a bent function $f$ on $\mathbb{F}_2^n$, we show that $h$ is outside $\mathcal{MM}^\#$ if and only if $f$ is outside $\mathcal{MM}^\#$. This approach is then generalized to the case when two bent functions are used. More precisely, the concatenation $f_1||f_1||f_2||(1\oplus f_2)$ also gives bent functions outside $\mathcal{MM}^\#$ if either $f_1$ or $f_2$ is outside $\mathcal{MM}^\#$. The cases when the four restrictions of a bent function are semi-bent or 5-valued spectra functions are also considered and several design methods of designing infinite families of bent functions outside $\mathcal{MM}^\#$, using the spectral domain design are proposed.

This paper presents an efficient attack that, in the standard IND-CCA2 attack model plus a one-time single-bit fault, recovers the NTRU-HRSS session key. This type of fault is expected to occur for many users through natural DRAM bit flips. In a multi-target IND-CCA2 attack model plus a one-time single-bit fault, the attack recovers every NTRU-HRSS session key that was encapsulated to the targeted public key before the fault. Software carrying out the full multi-target attack, using a simulated fault, is provided for verification. This paper also explains how a change in NTRU-HRSS in 2019 enabled this attack.

We propose the first unbounded functional encryption (FE) scheme for quadratic functions and its extension, in which the sizes of messages to be encrypted are not a priori bounded. Prior to our work, all FE schemes for quadratic functions are bounded, meaning that the message length is fixed at the setup. In the first scheme, encryption takes $\{x_{i}\}_{i \in S_{c}}$, key generation takes $\{c_{i,j}\}_{i,j \in S_{k}}$, and decryption outputs $\sum_{i,j \in S_{k}} c_{i,j}x_{i}x_{j}$ if and only if $S_{k} \subseteq S_{c}$, where the sizes of $S_{c}$ and $S_{k}$ can be arbitrary. Our second scheme is the extension of the first scheme to partially-hiding FE that computes an arithmetic branching program on a public input and a quadratic function on a private input. Concretely, encryption takes a public input $\vec{u}$ in addition to $\{x_{i}\}_{i \in S_{c}}$, a secret key is associated with arithmetic branching programs $\{f_{i,j}\}_{i,j \in S_{k}}$, and decryption yields $\sum_{i,j \in S_{k}} f_{i,j}(\vec{u})x_{i}x_{j}$ if and only if $S_{k} \subseteq S_{c}$. Both our schemes are based on pairings and secure under the standard MDDH assumption.

Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving crypto problems that otherwise required significant effort. Since this inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as an optimization problem to leverage the ease provided by state-of-the-art solvers. The other direction is to improve existing models to make them more efficient and/or accurate. The current work is an attempt to contribute to the latter. In this work, a general model referred to as DEEPAND has been devised to capture the correlation between AND gates in NLFSR-based lightweight block ciphers. DEEPAND builds upon and generalizes the idea of joint propagation of differences through AND gates captured using refined MILP modeling of TinyJAMBU by Saha et al. in FSE 2020. The proposed model has been applied to TinyJAMBU and KATAN and can detect correlations that were missed by earlier models. This leads to more accurate differential bounds for both the ciphers. In particular, a 384-round type-4 trail is found for TinyJAMBU with 14-active AND gates using the new model, while the refined model reported this figure to be 19. Moreover, we have found a full round type-4 trail of TinyJAMBU keyed permutation $P_{1024}$ with probability $2^{-108}$ ($\gg2^{-128}$), which violates designer's security claim. Thus, our results shows that TinyJAMBU's underlying keyed-permutation have non-random properties. As a result, it cannot be expected to provide the same security levels as robust block ciphers and also, the provable security of TinyJAMBU AEAD scheme should be carefully revisited.

Similarly, for KATAN32, DEEPAND modeling improves the 42-round trail with $2^{-11}$ probability to $2^{-7}$. DEEPAND seems to capture the underlying correlation better when multiple AND gates are at play and can be adapted to other classes of ciphers as well.

TinyJambu is one of the finalists in the NIST lightweight cryptography competition. It has undergone extensive analysis in the recent years as both the keyed permutation as well as the mode are new designs. In this paper we present a related-key forgery attackon the updated TinyJambu scheme with 256- and 192-bit keys. We introduce a high probability related-key differential attack were the differences are only introduced into the key state. Therefore, the characteristic is applicable to the TinyJambu mode and can be used to mount a forgery attack. The time and data complexity of the forgery are $2^{32}$ using $2^{10}$ related-keys for the 256-bit key version, and $2^{42}$ using $2^{12}$ related-keys for the 192-bit key version. For the 128-bit key we construct a related-key differential characteristic on the full keyed permutation of TinyJambu with a probability of $2^{-16}$. We extend the related-key differential characteristics on TinyJambu to practical time key recovery attacks that extract the full key from the keyed permutation with a time and data complexity of $2^{23}$, $2^{20}$, and $2^{18}$ for respectively the 128-, 192-, and 256-bit key variants. All characteristics are experimentally verified and we provide key nonce pairs that produce the same tag to show the feasibility of the forgery attack.

FRIET is a duplex-based authenticated encryption scheme proposed at EUROCRYPT 2020. It follows a novel design approach for built-in countermeasures against fault attacks. By a judicious choice of components, the designers propose the permutation FRIET-PC that can be used to build an authenticated encryption cipher denoted as FRIET-AE. And FRIET-AE provides a 128-bit security claim for integrity and confidentiality. In this paper, we research the propagation of differences and liner masks through the round function of FRIET-PC. For full-round FRIET-PC, we can construct a differential distinguisher whose probability is 1 and a linear distinguisher whose absolute value of correlation is 1. For the authenticated encryption cipher PRIET-AE, we use the differential distinguisher with probability 1 to construct a set consisting of valid tags and ciphertexts which are not created by legal users. This breaks FRIET-AE's security claim for integrity and confidentiality. As far as we know, this is the first practical attack that threatens the security of FRIET-AE.

Since 2015, a crypto engineering challenge is organized every year in cooperation with CHES. Former editions have focused on practical side-channel attacks, design of countermeasures, deep learning-based attacks, white-box cryptography, and hardware security.

We welcome proposals of challenge organisation for CHES 2023.

Interested? Please refer to the call: https://ches.iacr.org/2023/challenge.php

Event date: 1 May to 4 May 2023

The KASTEL Institute of Information Security and Dependability is looking for multiple PhD students and PostDocs committed to privacy-preserving cryptography. Experiences with secure multi-party computation or UC-based security are a plus. For PostDocs a track record in this field is expected, including publications at reputable conferences such as Crypto, Eurocrypt, ACM CCS, PETS, etc.

You will be a member of the KASTEL Security Research Labs (https://zentrum.kastel.kit.edu). Your research will be dealing with privacy-preserving cryptographic building blocks and protocols for important application scenarios and result in both theoretical security concepts (protocol designs, security proofs, etc.) and their efficient implementation (e.g., a demonstrator). The contract will initially be limited to 1 year, but can be extended to several years (particularly for PhD candidates).

If you are interested, please send an email including your CV and a list of publications (for PostDocs) to andy.rupp@partner.kit.edu.

Closing date for applications:

Contact: Andy Rupp (PI at KASTEL)

More information: https://zentrum.kastel.kit.edu/english/index.php

ISTA invites applications for several open positions in all areas of computer science including cryptography, systems security and privacy.

We offer:

• A highly international and interdisciplinary research environment with English as working language on campus
• State-of-the-art facilities and scientific support services
• Substantial start-up package and attractive salary
• Guaranteed annual base funding including funding for PhD students and postdocs
• An international Graduate School with high admissions criteria and a rigorous training program
• Leadership program
• Employee Assistance program
• Dual Career support packages
• Child-care facilities on campus (for children aged 3 months till school age)

ISTA is an international institute dedicated to basic research and graduate education in the natural, mathematical, and computational sciences. The Institute fosters an interactive, collegial, and supportive atmosphere, sharing space and resources between research groups whenever possible, and facilitating cross-disciplinary collaborations.

Assistant professors receive independent group leader positions with an initial contract of six years, at the end of which they are reviewed by international peers. If the evaluation is positive, an assistant professor is promoted to a tenured professor.

Candidates for tenured positions are distinguished scientists in their respective research fields and typically have at least six year of experience in leading a research group.

ISTA values diversity and is committed to equal opportunities. We strive to increase the number of women, particularly in fields where they are underrepresented, and therefore we strongly encourage female researchers.

Please apply online at: www.ista.ac.at/jobs/faculty

The closing date for applications is October 27, 2022.

Closing date for applications:

Contact:

Prof. Krzysztof Pietrzak (pietrzak@ista.ac.at) or Prof. Lefteris Kokoris Kogias (ekokoris@ista.ac.at)

I am searching for an outstanding Ph.D. candidate to start on 1st November 2022 (negotiable) in the Coding Theory and Cryptology group at Eindhoven Technical University (TU/e).

Possible topics fall into the field of provable security with a focus on the construction of efficient cryptographic building blocks and protocols, including
-(post-quantum) secure key exchange and messaging protocols and
-efficient digital signatures and public key encryption in realistic security models.

The fully-funded position offers exciting research in a highly international research environment. Candidates from outside of the Netherlands can be eligible for an additional tax reduction scheme.

Requirements:
-a Master's degree (or equivalent) with excellent grades in computer science, mathematics, or IT security.
-strong mathematical and/or algorithmic/theoretical CS background.
-good knowledge of cryptography and provable security.
-good written and verbal communication skills in English (Dutch is not required).

TU/e embraces diversity and inclusion. Therefore, people from all backgrounds are invited to apply, without regard to sex, gender, race, ethnicity, nationality, age, socio-economic status, identity, visible or invisible disability, religion, or sexual orientation.

To apply, prepare a single PDF file that includes a CV with a course list and grades. Applications received until 9th September 2022 receive full consideration. After that, the position is filled as soon as possible.

Applications and questions can be directed at s.schage@tue.nl.

Closing date for applications:

Contact: Sven Schäge

Job Description: A candidate will work in the area of post-quantum cryptography. A candidate will conduct research on analysis of post-quantum cryptography; the emphasis is on quantum analysis on symmetric cipher and PQC. The work requires to carry out some simulations. Applicants are expected to have a PhD degree in Mathematics/Physics/Computer Science and a strong background in quantum algorithm, algebra, linear algebra or algebraic number theory. Preferred candidates are expected to be proficient in Magma software or SAGEMATH software or knowledge on quantum software (eg. Qiskit, etc), a team worker and able to conduct independent research. Interested candidates will kindly include their full CV and transcripts in their applications and send to Dr Chik How Tan, tsltch@nus.edu.sg. Only shortlisted applications will be notified.

Closing date for applications:

Contact: Dr Chik How Tan, tsltch@nus.edu.sg