International Association
for Cryptologic Research

There are many recent results on reverse-engineering (potentially hidden) structure in cryptographic S-boxes. The problem of recovering structure in the other main building block of symmetric cryptographic primitives, namely, the linear layer, has not been paid that much attention so far. To fill this gap, in this work, we develop a systematic approach to decomposing structure in the linear layer of a substitution-permutation network (SPN), covering the case in which the specification of the linear layer is obfuscated from applying secret linear transformations to the S-boxes. We first present algorithms to decide whether an $ms \times ms$ matrix with entries in a prime field $\mathbb{F}_p$ can be represented as an $m \times m$ matrix over the extension field $\mathbb{F}_{p^s}$. We then study the case of recovering structure in MDS matrices by investigating whether a given MDS matrix follows a Cauchy construction. As an application, for the first time, we show that the $8 \times 8$ MDS matrix over $\mathbb{F}_{2^8}$ used in the hash function Streebog is a Cauchy matrix.

K-Cipher is an ultra-low latency block cipher with variable-length parameters designed by Intel Labs. In this work, we analyze the security of K-Cipher and propose a differential cryptanalysis attack with the complexity of $2^{29.7}$ for a variant of K-Cipher with state size $n=24$ bits state and block size $m=8$ bits. Our attack recovers the secret key and secret randomizer values with a total length of 240 bits in $\sim 30$ minutes on a standard desktop machine. We show that it is possible to extend the same attack for an arbitrary set of parameters.

We propose three constructions of classically verifiable non-interactive zero-knowledge proofs and arguments (CV-NIZK) for QMA in various preprocessing models.

1. We construct a CV-NIZK for QMA in the quantum secret parameter model where a trusted setup sends a quantum proving key to the prover and a classical verification key to the verifier. It is information theoretically sound and zero-knowledge.

2. Assuming the quantum hardness of the learning with errors problem, we construct a CV-NIZK for QMA in a model where a trusted party generates a CRS and the verifier sends an instance-independent quantum message to the prover as preprocessing. This model is the same as one considered in the recent work by Coladangelo, Vidick, and Zhang (CRYPTO '20). Our construction has the so-called dual-mode property, which means that there are two computationally indistinguishable modes of generating CRS, and we have information theoretical soundness in one mode and information theoretical zero-knowledge property in the other. This answers an open problem left by Coladangelo et al, which is to achieve either of soundness or zero-knowledge information theoretically. To the best of our knowledge, ours is the first dual-mode NIZK for QMA in any kind of model.

3. We construct a CV-NIZK for QMA with quantum preprocessing in the quantum random oracle model. This quantum preprocessing is the one where the verifier sends a random Pauli-basis states to the prover. Our construction uses the Fiat-Shamir transformation. The quantum preprocessing can be replaced with the setup that distributes Bell pairs among the prover and the verifier, and therefore we solve the open problem by Broadbent and Grilo (FOCS '20) about the possibility of NIZK for QMA in the shared Bell pair model via the Fiat-Shamir transformation.

The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation (CPFE) and its relaxed version (rCPFE) was proposed in [11]. We define an ideal functionality for the latter task and present a UC-secure realization of the functionality against static malicious parties. The core primitive is functional encryption (FE) and essentially this determines the conditions of realizability. Accordingly, in the case of non-adaptive FE-setting secure realization of the ideal functionality is achievable in the standard model, otherwise, accessibility of random oracle is required.

We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as $\mathbb{Z}^n$ , leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The most significant change from recent LIP proposals is the use of module lattices, reusing algorithms and ideas from NTRUSign and Falcon.

Its simplicity makes Hawk competitive. We provide cryptanalysis with experimental evidence for the design of Hawk and implement two parameter sets, Hawk-512 and Hawk-1024. Signing using Hawk-512 and Hawk-1024 is four times faster than Falcon on x86 architectures, produces signatures that are about 15% more compact, and is slightly more secure against forgeries by lattice reduction attacks. When floating-points are unavailable, Hawk signs 15 times faster than Falcon.

We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.

The efficiency of constant-time SM4 implementation has been lagging behind that of AES for most internet traffic and applicable data encryption scenarios. The best performance before our works was 3.77 cpb for x86 platform (AESNI + AVX2), and 8.62 cpb for Arm platform (NEON). Meanwhile the state of art constant-time AES implementation could reach 0.63 cpb. Dedicated SM4 instruction set extensions like those optionally available in Armv8.2, could achieve comparable cpb to AES. But they are only available in limited processors, therefore does not impact much to real-world uses. To fill the gap we explored some novel techniques with Intel GFNI instruction set extension and Arm NEON coprocessor. We achieved 1.51 cpb with GFNI + AVX512 and 2.62 cpb with GFNI + AVX2 for Intel processors; we also achieved 6.74 cpb with NEON. In addition, we simplified the algebraic expression of SM4 S-Box. And our technique to exploit L1 cache could also be applied to other applications and hardware platforms if the circumstances apply.

We provide optimized range proofs, called $\mathsf{Sharp}$, in discrete logarithm and hidden order groups, based on square decomposition. In the former setting, we build on the paradigm of Couteau et al. (Eurocrypt '21) and optimize their range proof (from now on, CKLR) in several ways: (1) We introduce batching via vector commitments and an adapted $\Sigma$-protocol. (2) We introduce a new group switching strategy to reduce communication. (3) As repetitions are necessary to instantiate CKLR in standard groups, we provide a novel batch shortness test that allows for cheaper repetitions. The analysis of our test is nontrivial and forms a core technical contribution of our work. For example, for $\kappa = 128$ bit security and $B = 64$ bit ranges for $N = 1$ (resp. $N = 8$) proof(s), we reduce the proof size by $34\%$ (resp. $75\%$) in arbitrary groups, and by $66\%$ (resp. $88\%)$ in groups of order $256$-bit, compared to CKLR.

As $\mathsf{Sharp}$ and CKLR proofs satisfy a der 256-bit “relaxed” notion of security, we show how to enhance their security with one additional hidden order group element. In RSA groups, this reduces the size of state of the art range proofs (Couteau et al., Eurocrypt '17) by $77\%$ ($\kappa = 128, B = 64, N = 1$).

Finally, we implement our most optimized range proof. Compared to the state of the art Bulletproofs (Bünz et al., S&P 2018), our benchmarks show a very significant runtime improvement. Eventually, we sketch some applications of our new range proofs.

Functional Encryption (FE) has been extensively studied in the recent years, mainly focusing on the feasibility of constructing FE for general functionalities, as well as some realizations for restricted functionalities of practical interest, such as inner-product. However, little consideration has been given to the issue of key leakage on FE. The property of FE that allows multiple users to obtain the same functional keys from the holder of the master secret key raises an important problem: if some users leak their keys or collude to create a pirated decoder, how can we identify at least one of those users, given some information about the compromised keys or the pirated decoder? Moreover, how do we disable the decryption capabilities of those users (i.e. traitors)?

Two recent works have offered potential solutions to the above traitor scenario. However, the two solutions satisfy weaker notions of security and traceability, can only tolerate bounded collusions (i.e., there is an a priori bound on the number of keys the pirated decoder obtains), or can only handle a polynomially large universe of possible identities. In this paper, we study trace-and-revoke mechanism on FE and provide the first construction of trace-and-revoke FE that supports arbitrary identities, is both fully collusion resistant and fully anonymous. Our construction relies on a generic transformation from revocable predicate functional encryption with broadcast (RPFE with broadcast, which is an extension of revocable predicate encryption with broadcast proposed by Kim and J. Wu at ASIACRYPT'2020) to trace-and-revoke FE. Since this construction admits a generic construction of trace-and-revoke inner-product FE (IPFE), we instantiate the trace-and-revoke IPFE from the well-studied Learning with Errors (LWE). This is achieved by proposing a new LWE-based attribute-based IPFE (ABIPFE) scheme to instantiate RPFE with broadcast.

Blockchain technology provides efficient and secure solutions to various online activities by utilizing a wide range of cryptographic tools. In this paper, we survey the existing literature on post-quantum secure digital signatures that possess exotic advanced features and which are crucial cryptographic tools used in the blockchain ecosystem for (i) account management, (ii) consensus efficiency, (iii) empowering scriptless blockchain, and (iv) privacy. The exotic signatures that we particularly focus on in this work are the following: multi-/aggregate, threshold, adaptor, blind and ring signatures. Herein the term exotic refers to signatures with properties which are not just beyond the norm for signatures e.g. unforgeability, but also imbue new forms of functionalities. Our treatment of such exotic signatures includes discussions on existing challenges and future research directions in the post-quantum space. We hope that this article will help to foster further research to make post-quantum cryptography more accessible so that blockchain systems can be made ready in advance of the approaching quantum threats.

The pseudorandom function Farfalle, proposed by Bertoni et al. at ToSC 2017, is a permutation based arbitrary length input and output PRF. At its core are the public permutations and feedback shift register based rolling functions. Being an elegant and parallelizable design, it is surprising that the security of Farfalle has been only investigated against generic cryptanalysis techniques such as differential/linear and algebraic attacks and nothing concrete about its provable security is known. To fill this gap, in this work, we propose Farasha, a new permutation-based parallelizable PRF with provable security. Farasha can be seen as a simple and provable Farfalle-like construction where the rolling functions in the compression and expansion phases of Farfalle are replaced by a uniform almost xor universal (AXU) and a simple counter, respectively. We then prove that in the random permutation model, the compression phase of Farasha can be shown to be an uniform AXU function and the expansion phase can be mapped to an Even-Mansour block cipher. Consequently, combining these two properties, we show that Farasha achieves a security of min(keysize, permutation size/2). Finally, we provide concrete instantiations of Farasha with AXU functions providing different performance trade-offs. We believe our work will bring new insights in further understanding the provable security of Farfalle-like constructions.

In 3GPP mobile networks, application data is transferred between the phone and an access point over a wireless link. The mobile network wireless link is special since one channel endpoint is handed over from one access point to another as the phone physically moves. Key evolution during handover has been analyzed in various works, but these do not combine the analysis with analysis of the wireless-link application-data encryption protocol that uses the keys.

To enable formal analysis of the 4G/5G wireless link, we develop a game-based security framework for such channels and define flexible key insulation security notions for application data transfer, including forward and backward security in the given adversary model. Our notions are modular and combine a bidirectional application data transfer channel with a generic framework for multiparty channel-evolution protocols. These two components interact, and the security of the channel-evolution protocol may rely on the security of the data transfer channel for some or all its messages.

We also develop the first formal model of 4G/5G wireless link security including both handover key evolution and application data transfer, in the complexity theoretic setting. We prove the model secure w.r.t. our security notions. As a byproduct, we identify recommendations for improving the security of future mobile network standards to achieve key insulation. Specifically, we show that the current standards do not achieve forward secure encryption, even though this appears to be an explicit goal. We show how this can be rectified.

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}'$.