International Association
for Cryptologic Research

If you had a time machine, what cryptography would you be able to break?

In this work, we investigate the notion of time travel, formally defining models for adversaries equipped with a time machine, and exploring the consequences for cryptography. We find that being able to rewind time breaks some cryptographic schemes, and being able to freely move both forwards and backwards in time breaks even more schemes.

We look at the impacts of time travel on encryption and signatures in particular, finding that the $\text{IND-CCA}$ and $\text{EUF-CMA}$ security games are broken, while $\text{IND-CPA}$ and $\text{UUF-CMA}$ remain secure.

Impossible differential (ID) and zero-correlation (ZC) attacks are a family of important attacks on block ciphers. For example, the impossible differential attack was the first cryptanalytic attack on 7 rounds of AES. Evaluating the security of block ciphers against these attacks is very important, but also challenging: Finding these attacks usually implies a combinatorial optimization problem involving many parameters and constraints that is very hard to solve using manual approaches. Automated solvers, such as Constraint Programming (CP) solvers, can help the cryptanalyst to find suitable distinguishers. However, previous CP-based methods are focused on finding only the ID or ZC distinguishers, and often only in a limited search space. Notably, none of them can be extended to a unified optimization problem for finding full attacks including efficient key-recovery steps.

In this paper, we present a new CP-based method to search for ID and ZC distinguishers and extend it to a unified constraint optimization problem for finding full ID, ZC, and integral attacks. To show the effectiveness and usefulness of our method, we apply it to the ISO standard block cipher SKINNY and improve all of the existing ID, ZC, and integral attacks on it. In particular, we improve the integral attacks on SKINNY-$n$-$3n$ and SKINNY-$n$-$2n$ by 3 and 2 rounds, respectively, obtaining the best cryptanalytic results on these variants in the single-key setting. We improve the ZC attack on SKINNY-$n$-$2n$ and SKINNY-$n$-$n$ by 1 and 2 rounds, respectively. Applying our tool to discover ID attacks, we improve the ID attacks on all variants of SKINNY in the single-tweakey setting. Particularly, we improve the time complexity of the best previous single key ID attack on SKINNY-$128$-$256$ by a factor of $2^{22.57}$, while keeping the data and memory complexities much smaller. We also improve the ID attack on SKINNY-$n$-$3n$ in the related-tweakey setting. Our method is generic and applicable to other word-oriented block ciphers.

Both multi-user PRFs and sponge-based constructions have generated a lot of research interest lately. Dedicated analyses for multi-user security have improved the bounds a long distance from the early generic bounds obtained through hybrid arguments, yet the bounds generally don't allow the number of users to be more than birthday-bound in key-size. Similarly, known sponge constructions suffer from being only birthday-bound secure in terms of their capacity. We present in this paper $\textsf{Muffler}$, a multi-user PRF built from a random permutation using a full-state sponge with feed-forward, which uses a combination of the user keys and unique user IDs to solve both the problems mentioned by improving the security bounds for multi-user constructions and sponge constructions. For $D$ construction query blocks and $T$ permutation queries, with key-size $\kappa = n/2$ and tag-size $\tau$ = $n/2$ (where $n$ is the state-size or the size of the underlying permutation), both $D$ and $T$ must touch birthday bound in $n$ in order to distinguish $\textsf{Muffler}$ from a random function.

This note describes two pairing-friendly curves that embed ed25519, of different bit security levels. Our search is not novel---it follows the standard recipe of the Cocks-Pinch method. We implemented these two curves on arkworks-rs. This note is intended to provide a document on how the parameters are being generated and how to implement these curves in arkworks-rs 0.4.0, for further reference. We name the two curves as Yafa-108 and Yafa-146:

- Yafa-108 is estimated to offer 108-bit security, which we parameterized to match the 102-bit security of BN254

- Yafa-146 is estimated to offer 146-bit security, which we parameterized to match the 131-bit security of BLS12-446 or 122-bit security of BLS12-381

We use these curves as an example to demonstrate two things:

- The "elastic" zero-knowledge proofs, Gemini (EUROCRYPT '22), is more than being elastic, but it is more curve-agnostic and hardware-friendly. - The cost of nonnative field arithmetics can be drastic, and the needs of application-specific curves may be inherent. This result serves as evidence of the necessity of EIP-1962, and the insufficiency of EIP-2537.

We explore a bitwise modification in Ajtai's one-way function. Our main contribution is to define the higher-bit approximate inhomogeneous short integer solution (ISIS) problem and prove its reduction to the ISIS problem. In this new instance, our main idea is to discard low-weighted bits to gain compactness. As an application, we construct a bitwise version of a hash-and-sign signature in the random oracle model whose security relies on the (Ring)-LWE and (Ring)-ISIS assumptions. Our scheme is built from the hash-and-sign digital signature scheme based on the relaxed notion of approximate trapdoors introduced by Chen, Genise and Mukherjee (2019). Their work can be interpreted as a bitwise optimization of the work of Micciancio and Peikert (2012). We extend this idea and apply our technique to the scheme by discarding low-weighted bits in the public key. Our modification brings improvement in the public key size but also in the signature size when used in the right setting. However, constructions based on the higher-bit approximate ISIS save memory space at the expense of loosening security. Parameters must be set in regards with this trade-off.

A threshold public key encryption protocol is a public key system where the private key is distributed among $n$ different servers. It offers high security since no single server is entrusted to perform the decryption in its entirety. It is the core component of many multiparty computation protocols which involves mutually distrusting parties with common goals. It is even more useful when it is homomorphic, which means that public operations on ciphertexts translate to operations on the underlying plaintexts. In particular, Cramer, Damgård and Nielsen at Eurocrypt 2001 provided a new approach to multiparty computation from linearly homomorphic threshold encryption schemes. On the other hand, there has been recent interest in developing multiparty computations modulo $2^k$ for a certain integer $k$, that closely match data manipulated by a CPU. Multiparty computation would therefore benefit from an encryption scheme with such a message space that would support a distributed decryption.

In this work, we provide the first threshold linearly homomorphic encryption whose message space is $\mathbf{Z}/2^k\mathbf{Z}$ for any $k$. It is inspired by Castagnos and Laguillaumie's encryption scheme from RSA 2015, but works with a class group of discriminant whose factorisation is unknown.

Its natural structure à la Elgamal makes it possible to distribute the decryption among servers using linear integer secret sharing, allowing any access structure for the decryption policy. Furthermore its efficiency and its flexibility on the choice of the message space make it a good candidate for applications to multiparty computation.

Security against side-channels and faults is a must for the deployment of embedded cryptography. A wide body of research has investigated solutions to secure implementations against these attacks at different abstraction levels. Yet, to a large extent, current solutions focus on one or the other threat. In this paper, we initiate a mode-level study of cryptographic primitives that can ensure security in a (new and practically-motivated) adversarial model combining leakage and faults. Our goal is to identify constructions that do not require a uniform protections of all their operations against both attack vectors. For this purpose, we first introduce a versatile and intuitive model to capture leakage and faults. We then show that a MAC introduced at Asiacrypt 2021 natively enables a leveled implementation where only its underlying tweakable block cipher must be protected, as long as only its tag verification can be faulted. We finally describe two approaches to amplify security in the case where also the tag generation can be faulted. One is based on iteration and requires the adversary to inject increasingly large faults to succeed. The other is based on randomness and allows provable security against differential faults.

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no general construction for all S-boxes was ever presented. The lower bound for the number of shares of threshold implementation is $t+1$, where $t$ is the algebraic degree of the S-box. Since the smallest number of shares $t+1$ is not possible for all S-Boxes, as proven by Bilgin et al. in 2015, then there does not exist a universal construction with $t+1$ shares. Hence, if there is a universal construction working for all permutations then it should work with at least $t+2$ shares. In this paper, we present the first optimal universal construction with $t+2$ shares. This construction enables low latency hardware implementations without the need for randomness. In particular, we apply this result to find the first two uniform sharings of the AES S-box. Area and performance figures for hardware implementations are provided.

Witness encryption (WE) allows us to use an arbitrary NP statement $x$ as a public key to encrypt a message, and the witness $w$ serves as a decryption key. Security ensures that, when the statement $x$ is false, the encrypted message remains computationally hidden. WE appears to be significantly weaker than indistinguishability obfuscation (iO). Indeed, WE is closely related to a highly restricted form of iO that only guarantees security for null circuits (null iO). However, all current approaches towards constructing WE under nice assumptions go through iO. Such constructions are quite complex and are unlikely to lead to practically instantiable schemes. In this work, we revisit a very simple WE and null iO candidate of Chen, Vaikuntanathan and Wee (CRYPTO 2018). We show how to prove its security under a nice and easy-to-state assumption that we refer to as "evasive LWE" following Wee (EUROCRYPT 2022). Roughly speaking, the evasive LWE assumption says the following: assume we have some joint distributions over matrices $\mathbf{P}$, $\mathbf{S}$ and auxiliary information $\mathsf{aux}$ such that $$({\mathbf{S}\mathbf{B} + \mathbf{E}},{\mathbf{S} \mathbf{P} + \mathbf{E}'}, \mathsf{aux}) \approx_c ({\mathbf{U}},{\mathbf{U'}}, \mathsf{aux}),$$ for a uniformly random (and secret) matrix $\mathbf{B}$, where $\mathbf{U}, \mathbf{U}'$ are uniformly random matrices, and $\mathbf{E},\mathbf{E}'$ are chosen from the LWE error distribution with appropriate parameters. Then it must also be the case that: $$\mathbf{S}\mathbf{B} + \mathbf{E}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}) \approx_c (\mathbf{U}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}).$$ Essentially the above says that given $\mathbf{S}\mathbf{B} + \mathbf{E}$, getting the additional component $\mathbf{B}^{-1}(\mathbf{P})$ is no more useful than just getting the product $({\mathbf{S}\mathbf{B} + \mathbf{E}})\cdot \mathbf{B}^{-1}(\mathbf{P}) \approx \mathbf{S} \mathbf{P} + \mathbf{E}'$.

We present a novel, complete definition of metadata-private messaging (MPM) and show that our definition is achievable and non-trivially more general than previous attempts that we are aware of. Our main contributions are:

1) We describe a vulnerability in existing MPM implementations through a variation of the compromised-friend (CF) attack proposed by Angel et al. Our attack can compromise the exact metadata of any conversations between honest users.

2) We present a security definition for MPM systems assuming that some friends may be compromised.

3) We present a protocol satisfying our security definition based on Anysphere, an MPM system we deployed in practice.

We propose Designated-Verifier Linkable Ring Signatures with unconditional anonymity, a cryptographic primitive that protects the privacy of signers in two ways: Firstly, it allows them to hide inside a ring (i.e. an anonymity set) they can create by collecting a set of public keys all of which must be used for verification. Secondly, it allows a designated entity to simulate signatures thus making it difficult for an adversary to deduce their identity from the content of the exchanged messages. Our scheme differs from similar proposals since the anonymity guarantees are unconditional.

In this paper, we propose a new protocol for private computation on set intersection (PCI) which is an extension of private set intersection (PSI). In PSI, each party has a private set and both want to securely compute the intersection of their sets such that only the result is revealed and nothing else. In PCI, we want to additionally apply a private computation on the result. The goal is to reveal only the result of such a secure evaluation on the intersection and nothing else. We particularly focus on a client-server setting where the server's set is significantly larger than the client's set and the result of the computation should be revealed only to the client. The protocol aims at a low communication overhead which is sublinear in the server's set size. Such PSI protocols have already been realized using fully homomorphic encryption (FHE). However, they do not allow for private post-processing to enable PCI. There are also protocols enabling PCI which are in addition very fast with respect to the computational overhead. Their drawback is that they have a communication overhead which is at least linear in the larger set. We present a PSI protocol which can be used for arbitrary post-processing without creating a new protocol for every special-purpose PCI functionality. Our construction relies on the evaluation of a branching program using an FHE scheme. Using the properties of an FHE scheme, we build a non-interactive protocol with extendable functionalities. That means, we can not only securely compute the intersection but use the encrypted result to apply further computations without revealing the intersection itself. To the best of our knowledge, this results in the first PCI protocol with communication cost sublinear in the larger set. Compared to previous work, we can reduce the communication by factor 47.

In this paper, we consider the new version of tropical cryptography protocol, i.e the tropical version of ElGamal encryption. We follow the ideas and modify the classical El Gamal encryption using tropical matrices and matrix power in tropical algebra. Then we also provide a toy example for the reader’s understanding.

Cryptographic group actions are a relaxation of standard cryptographic groups that have less structure. This lack of structure allows them to be plausibly quantum resistant despite Shor's algorithm, while still having a number of applications. The most famous example of group actions are built from isogenies on elliptic curves.

Our main result is that CDH for abelian group actions is quantumly *equivalent* to discrete log. Galbraith et al. (Mathematical Cryptology) previously showed *perfectly* solving CDH to be equivalent to discrete log quantumly; our result works for any non-negligible advantage. We also explore several other questions about group action and isogeny protocols.

Event date: 15 December to 17 December 2022
Notification: 31 October 2022

Applications are invited for the MS and PhD positions in Information Security at the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. The successful candidate will work under the guidance of Dr. Arijit Karati on the diverse topics in Applied Cryptology. Candidates must comprehend formal security analysis, secure coding, and effective security integration in the application domains.

Responsibilities: Apart from academic work, student must involve in several activities in a group or individually, such as (not limited to):

Design and implementation of security protocol.

Assesment of the security and performance metric.

Research meeting with the supervisor.

Requirements: Apart from the university's basic admission policies (https://cse.nsysu.edu.tw/?Lang=en), students are desired to have following key requirements:

Strong motivation on information security.

Knowledge of modern technology.

Knowledge of basic mathematics for cryptography.

Knowledge of at least two programming languages, such as Python/Java/C/C++.

Scholarship:

Under the university policy.

Project funding (based on availability for master's Ph.D. students).

What students can expect:

Cooperation from the supervisor and labmates.

The rich culture in research and related activities.

Flexibility in communication, e.g., English.

What the supervisor can expect: Apart from academic and research works, students are expected to have

Good moral character.

Hardworking and dedication.

Deadline: Until September 2022 (for spring semester) and March 2023 (for fall semester)

Closing date for applications:

Contact: Arijit Karati (arijit.karati@mail.cse.nsysu.edu.tw)

Devices and Services Trust and Security (DSTS) group at Amazon is looking for a senior cryptographer with cryptography implementation experience. Candidate is expected to be a primary contributor to the development and execution of a post-quantum transition strategy within DSTS with impacts Amazon wide. In addition, candidate will identify security and cryptography concerns in devices/web services/applications at all stages of development (from concept to in-production). Candidate will lead or participate in the development of proof-of-concept implementations and guidance/training material regarding secure/proper use of cryptography. Key job responsibilities * Develop strategy, plans, and collateral to transition to PQ cryptographic algorithms * Develop and productize software implementations for PQ algorithms capable of running on Amazon devices and low-cost MCUs * Write collateral and training material to aid development teams in use of cryptography and transition to PQ algorithms * Perform trade-offs between cryptography, business-needs and security requirements to recommend best algorithm solutions and timings for algorithm transitions, taking into account software, hardware, backend services and market acceptance * Participate in development of requirements and hardware/software implementations for performant implementations of new cryptographic algorithms * Asses and resolve trouble tickets from development teams regarding use of crypto in design, implementation and/or production * Develop tools to assess use of cryptography across DSTS teams

Closing date for applications:

Contact: Apply through link above

More information: https://www.amazon.jobs/en/jobs/2033486/sr-applied-cryptographer-ds-crypto

The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill some positions of post-doctoral research fellows and PhD students with full scholarship support on symmetric-key cryptography. Topics include but are not limited to the following sub-areas:

• tool aided cryptanalysis, such as MILP, CP, STP, and SAT
• machine learning aided cryptanalysis and designs
• privacy-preserving friendly symmetric-key designs
• quantum cryptanalysis
• theory and proof
• threshold cryptography
• cryptanalysis against SHA-2, SHA-3 and AES

Established in 2014, the Cryptanalysis Taskforce is a group dedicated for research in symmetric-key cryptography, it currently comprises more than 15 members of Postdocs, (exchange) PhD students, and visiting professors. Since establishment, the team has been active in both publications in and services for IACR. It has done quite some cryptanalysis work on various important targets such as SHA-3 and AES, and is expanding its interests to the areas mentioned above, with strong funding support from the university and government agencies in Singapore. We offer competitive salary package with extremely low tax (around 5%), as well as excellent environment dedicating for top-venues publication orientated research in Singapore. The contract for postdocs will be initially for one and half years, and has the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences. Interested candidates are to send their CV and 2 reference letters to Jian Guo. Review of applicants will start immediately until the positions are filled. Details on requirements of PhD admission to NTU and financial supports provided by the scholarships can be found here: https://guo.crypto.sg/students More information about the Cryptanalysis Taskforce research group can be found via https://team.crypto.sg

Closing date for applications:

Contact: Jian Guo, guojian@ntu.edu.sg, with subject [IACR-CATF]

More information: https://team.crypto.sg

The group of Prof. Dr. Cas Cremers at CISPA has multiple open positions. CISPA is one of the leading research institutions in Information Security worldwide, and is situated in Saarbrücken, Germany.

Positions are fully funded and we offer at least two year contracts with optional extension.

We have several ongoing projects in the areas of:

• Provable security : methodologies and automation (e.g., (manual) computational proofs, our work on the Tamarin Prover, or other tools),
• Protocol design, and
• Secure messaging.

We highly welcome new directions, and appreciate applicants with a passion for projects that are different from, but possibly connected to, our ongoing research.

Positions are fully funded and full-time.

Application deadline: September 22, 2022.

For more information, please click the link (title) of this job posting.

Closing date for applications:

Contact: Cas Cremers

More information: https://cispa.saarland/group/cremers/positions/index.html

The group of Prof. Dr. Cas Cremers at CISPA has open positions. CISPA is one of the leading research institutions in Information Security worldwide, and is situated in Saarbrücken, Germany.

We have several open projects in the areas of:

• Provable security : methodologies and automation (e.g., (manual) computational proofs, our work on the Tamarin Prover, or other tools),
• Protocol design, and
• Secure messaging.

Positions are fully funded and full-time.
Application deadline: September 22, 2022.

For more information, please click the link (title) of this job posting.

Closing date for applications:

Contact: Cas Cremers

More information: https://cispa.saarland/group/cremers/positions/index.html