Topics in Cryptology – CT-RSA 2024

Multi-Recipient Encryption allows users to send secure messages to any chosen set of registered users. In ACISP’21, Blazy et al. proposed a multi-recipient encryption with attribute-hiding revocation where ciphertexts do not reveal any information about the users that have been revoked. However, their work only achieved secret key instantiations of multi-recipient encryption with attribute-hiding revocation.

Our work gives the first public-key Identity-Based Revocation with fully attribute-hiding security and computational function privacy. For this purpose, we construct the first fully attribute-hiding Non-zero Inner-Product Encryption (NIPE) with computational function privacy. Toward this goal, we also study the relationship between Zero Inner-Product Encryption (ZIPE) and Non-Zero Inner-Product Encryption (NIPE). We propose a compiler to convert a fully attribute-hiding secure ZIPE into a fully attribute-hiding secure NIPE. We then construct the ZIPE with the necessary security properties. This construction along with the compiler produces the first NIPE with the said full attribute-hiding security. We also argue that this NIPE construction achieves computational function privacy due to a falsifiable assumption. A variation of Attrapadung and Libert’s transformation (PKC’11) on our NIPE thus achieves the first attribute-hiding identity-based revocation (IBR) scheme in the standard model. We further show that our IBR construction achieves function privacy under another novel assumption which we show to be falsifiable.

Ephemeral Diffie-Hellman Over COSE (EDHOC) is designed to be a compact and lightweight authenticated key exchange protocol, providing mutual authentication, forward secrecy, and identity protection. EDHOC aims at being suitable for low-power networks such as cellular IoT, 6TiSCH, and LoRaWAN. In this paper, we perform a security analysis of the last draft of EDHOC (draft \(23\)). We analyse the full protocol including its four different authentication methods. Our results show that the security of the authenticated key exchange in EDHOC depends essentially on that of the authenticated encryption algorithm used during that phase. Finally, we provide more precise estimates of the computational security bounds for all authentication methods in EDHOC so that meaningful choices of quantitative parameters can be done to instantiate the protocol securely.

The security of block-cipher-based hash-then-encrypt-type message authentication codes (MACs) has been proven with universal hash functions. Thus, the security of the underlying hash functions has been evaluated with the pseudo-random-permutation assumption, i.e., the block ciphers are replaced with random permutations to which an adversary cannot directly access. Due to a hybrid argument, this replacement offers tight multi-user bounds regarding online security. However, it degrades its offline security depending on the number of users \(u\): from \(k\) bits (key size) to \(k- \log _2 u\) bits.

We thus revise the definitions of universal hashing, \(\epsilon _1\)-regular and \(\epsilon _2\)-almost XOR universal, by involving ideal cipher, and show that multi-user security of several hash-then-encrypt-type MACs does not degrade from the single-user security.

\(\texttt{ACE}\), a second-round candidate of the NIST Lightweight Cryptography Standardization project, is a 16-step iterative permutation that operates on a 320-bit state. It aims to optimize the software efficiency and hardware cost for authentication encryption (AE) mode and a hashing mode based on sufficient security margins. However, the security of such permutation has not been studied well so far. In this paper, an algorithm is used for searching rebound distinguishers of \(\texttt{ACE}\) permutation. By applying this algorithm, we obtained the first 14-step rebound attack on \(\texttt{ACE}\) permutation. The nonlinear function (ordinary represented as Sbox) of \(\texttt{ACE}\) permutation is based on 8 rounds unkeyed \(\texttt{Simeck}\)-64 abbreviated as \(\texttt{SB}\)-64. By constructing an SMT model, the lower bound on the number of active \(\texttt{SB}\)-64s for the differential characteristics of \(\texttt{ACE}\) has been verified. Then, by making use of \(\texttt{SB}\)-64’s iterative differentials, we construct 128 11-step/13-step rebound distinguishers and 9 14-step rebound distinguishers for \(\texttt{ACE}\) permutation, the complexity of these rebound attacks was also discussed. All these attacks are the best ones so far, and this reduces the security margin of \(\texttt{ACE}\) permutation to \(12.5\%\).

We study the tight multi-user (mu) security of 2-key triple encryption (2kTE) with its application to 2-key TDES. With an n-bit block and k-bit key primitive block cipher, our new mu lower bound regarding the number of primitive queries is \(2^{\min \{2k,k+n\}}/q\) with \(q\) construction queries, which matches the previous best attacks and is tight. The bound ensures \((112 - \log _2 q)\)-bit security with 2-key TDES, and this can be used to evaluate and predict the security of systems supporting 2-key TDES for legacy use. We finally show that the FX construction does not efficiently improve the mu security with 2kTE, unlike the previous result with 3-key triple encryption appeared in CCS 2022. We show a concrete key-recovery attack with \(O(2^{n+k}/q)\) primitive queries.

In the single-key attack scenario, meet-in-the-middle (MitM) attack method has led to the best currently published cryptanalytic results on the AES block cipher, except biclique attack. Particularly, for AES with a 192-bit key (AES-192), Li et al. published 5-round MitM distinguishers and 9-round MitM attacks in 2014, by introducing the key-dependent sieve technique to reduce the number of unknown constants for a MitM distinguisher and using a so-called weak-key approach to reduce the memory complexity of an ordinary MitM attack, and their final main result is an attack on the first 9 rounds of AES-192 with a data complexity of \(2^{121}\) chosen plaintexts, a memory complexity of \(2^{181}\) bytes and a time complexity of \(2^{187.7}\) encryptions. In this paper, we observe that Li et al. used a wrong direction for the rotation operation of the AES-192 key schedule, which causes all their distinguishers and attacks to be seriously flawed, but fortunately we exploit a correct 5-round distinguisher with different active input and output byte positions, so that the resulting 9-round AES-192 attacks with/without Li et al.’s weak-key approach have the same complexities as Li et al.’s (flawed) attacks. Further, we give a trick to exploit two complicated additional one-byte linear relations (between the round keys of precomputation phase and the round keys of online phase) to further reduce memory complexity, and finally we make an attack on the 9-round AES-192 with a data complexity of \(2^{121}\) chosen plaintexts, a memory complexity of \(2^{172.3}\) bytes and a time complexity of \(2^{187.6}\) encryptions. Besides, we show that the 5-round MitM distinguisher can be extended to a 6-round MitM distinguisher, which can also attack the 9-round AES-192 with the same complexity. Our work corrects and improves Li et al.’s work, and the trick can potentially be used for MitM attacks on other block ciphers.

We revisit batch signatures (previously considered in a draft RFC and used in multiple recent works), where a single, potentially expensive, “inner” digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties.

We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST’s post-quantum project, to high throughput, with a mild increase in latency and demonstrate the practical efficiency of batch signing in the context of TLS. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2, at the cost of an increase in the signature size by 14% and the median latency by 25%; both run on the same 30 core server. For SPHINCS\(^+\)-128, throughput improves by a factor 4.6, with a negligible impact on signature size and an 11% impact on median latency.

We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for 16 Falcon-512 signatures, once one batch signature is available, the additional bandwidth for each of the remaining is only 82 bytes.

A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA). In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions. In this paper, we propose a (partial-signature) history-free SAS within the probabilistic hash-and-sign with retry paradigm, generalizing existing techniques to generic trapdoor functions. We prove the security of our scheme in the random oracle model and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the lack of security of two existing multivariate schemes.

Attribute-based cryptography allows fine-grained control on the use of the private key. In particular, attribute-based signature (ABS) specifies the capabilities of the signer, which can only sign messages associated to a policy that is authorized by his set of attributes. Furthermore, we can expect signature to not leak any information about the identity of the signer. ABS is a useful tool for identity-preserving authentication process which requires granular access-control, and can furthermore be enhanced with additional properties, for example delegation where users are able to manage a set of keys derived from their original one.

In this paper, we address delegation of signing keys. Our first delegation works for any subset of the original attributes, which is the intuitive approach of delegation. Furthermore, we also provide another kind of delegation where the delegator can choose a policy at delegation time to produce keys that can sign any message under this specific policy. This last approach to delegation is a direct application of a new version of the indexing technique, which was first introduced by Okamoto and Takashima in order to prove adaptive security in ABS and its counterpart for encryption, ABE. On top of that, we prove that our scheme is compatible with a well studied feature of ABS, traceability, by using an approach based on Linearly-Homomorphic signatures. All our schemes also guarantee the anonymity of the real signer.

Recently, Boneh and Komlo (CRYPTO 2022) initiated the study of threshold, accountable, and private signature (TAPS) schemes. Classical threshold signature schemes are either fully private or fully accountable. At a high level, a fully private threshold signature reveals no information about the signing parties, while the signers of a fully accountable threshold signature can be easily traced because their identities are revealed directly in the signature. TAPS opens up a brand new opportunity to enjoy the two seemingly contradicting features at the same time and therefore has great potential to be applicable in emerging blockchain applications. Unfortunately, the only TAPS to date are based on classical cryptographic assumptions that do not hold against quantum computers.

In this paper, we propose the first TAPS from lattice-based assumptions, which remain hard against quantum algorithms. Our main building blocks are a new lattice-based t-out-of-N proof of knowledge that employs a recent framework by Lyubashevsky et al. (CRYPTO 2022) and a lattice-based accountable threshold signature, which may be of independent interest. Using these building blocks, we provide a compact construction of lattice-based TAPS with asymptotically optimal signature size. Instantiating the scheme with our suggested parameters, the signature size is 42.34 KB for \(N=32\).

Fully homomorphic encryption allows directly processing encrypted data without having to decrypt it. The result of the computation is encrypted, typically under the same key. This unique feature offers a strong form of privacy. A service provider can so provide the same service but without ever seeing the user’s data. Examples of application include [privacy-preserving] preventive medicine, facial recognition or voice assistants. Fully homomorphic encryption can also be used to solve the privacy issues of the blockchain.

This paper introduces a public-key variant of fully homomorphic encryption scheme TFHE. The output ciphertexts are of LWE type and compatible with TFHE. Interestingly, the public key is much shorter and the resulting ciphertexts are less noisy. The security of the scheme holds under the standard RLWE assumption. Several variations and extensions are also described. The proposed scheme has been integrated in fhEVM, a protocol enabling developers to create encrypted on-chain smart contracts.

Homomorphic Encryption (HE) is a type of cryptography that allows computing on encrypted data, enabling computation on sensitive data to be outsourced securely. Many popular HE schemes rely on noise for their security. On the other hand, Differential Privacy (DP) seeks to guarantee the privacy of data subjects by obscuring any one individual’s contribution to an output. Many mechanisms for achieving DP involve adding appropriate noise. In this work, we investigate the extent to which the noise native to Homomorphic Encryption can provide Differential Privacy “for free”.

We identify the dependence of HE noise on the underlying data as a critical barrier to privacy, and derive new results on the Differential Privacy under this constraint. We apply these ideas to a proof of concept HE application, ridge regression training using gradient descent, and are able to achieve privacy budgets of \(\varepsilon \approx 2\) after 50 iterations.

This paper presents an adaptively secure identity-based encryption (IBE) scheme from Learning With Errors (LWE) in the standard model. Compared to the previous LWE-based most compact construction of Yamada (CRYPTO17), one of the distinguishing properties of our IBE scheme is that the master public key size of our IBE scheme is significantly smaller, and our design is explicitly given, and thus all the IBE parameters can be instantiated.

To achieve this, we design a more compact homomorphic equality test algorithm over LWE problems, which is significantly better than the previous bit-wise comparison of Yamada (CRYPTO17) and Katsumata (ASIACRYPT17). We show that our homomorphic equality test algorithms can pack a super-constant number of GSW-type bit encodings and thus may find other improvements in other LWE-based crypto schemes.

Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users’ secret keys requires huge public parameters. In this work, we specify a compact IBE instantiation for practical use by introducing various optimizations. Specifically, we first propose a modified gadget that offers a tradeoff between security and compactness, making it more suitable for the instantiation of practical IBEs. Then, by incorporating our gadget and the non-spherical Gaussian technique, we provide an efficient preimage sampling algorithm, based on which, we give a specification of a compact IBE on ideal lattice. Finally, two parameter sets and a proof-of-concept implementation are presented. Given the importance of the preimage sampling algorithm in lattice-based cryptography, we believe that our technique can also be applied to the practical instantiation of other advanced cryptographic schemes.

In 2023, NIST has selected Ascon as the new standard for lightweight cryptography. The Ascon v1.2 family provides authenticated encryption, hash functions, and extendable output functions, all using the same Ascon permutation. The main use case of Ascon is to provide efficient cryptographic primitives for resource-constraint devices. While additional primitives can be built on top of the existing Ascon functions, dedicated schemes are often more efficient. In this paper, we enrich the functionality of Ascon by providing efficient Pseudorandom Functions (PRFs), Message Authentication Codes (MACs), and a fast short-input PRF for messages up to 128 bits.

This work is motivated by the following question: can an untrusted quantum server convince a classical verifier of the answer to an efficient quantum computation using only polylogarithmic communication? We show how to achieve this in the quantum random oracle model (QROM), after a non-succinct instance-independent setup phase.

We introduce and formalize the notion of post-quantum interactive oracle arguments for languages in QMA, a generalization of interactive oracle proofs (Ben-Sasson–Chiesa–Spooner). We then show how to compile any non-adaptive public-coin interactive oracle argument (with private setup) into a succinct argument (with setup) in the QROM.

To conditionally answer our motivating question via this framework under the post-quantum hardness assumption of LWE, we show that the ZX local Hamiltonian problem with at least inverse-polylogarithmic relative promise gap has an interactive oracle argument with instance-independent setup, which we can then compile.

In this paper, we narrow our focus to fault attacks and countermeasures specific to ASICs, and introduce a novel parameterized fault adversary model capturing an adversary’s control over an ASIC. We systematically map (a) the physical fault injection mechanisms, (b) adversary models assumed in fault analysis, and (c) adversary models used to design countermeasures into our introduced model. This model forms the basis for our comprehensive exploration that covers a broad spectrum of fault attacks and countermeasures within symmetric key cryptography as a comprehensive survey. Furthermore, our investigation highlights a notable misalignment among the adversary models assumed in countermeasures, fault attacks, and the intrinsic capabilities of the physical fault injection mechanisms. Through this study, we emphasize the need to reevaluate existing fault adversary models, and advocate for the development of a unified model.

Group actions are fundamental mathematical tools, with a long history of use in cryptography. Indeed, the action of finite groups at the basis of the discrete logarithm problem is behind a very large portion of modern cryptographic systems. With the advent of post-quantum cryptography, however, other group actions, such as isogeny-based ones, received interest from the cryptographic community, attracted by the possibility of translating old discrete logarithm-based functionalities.

Usually, research focuses on abelian group actions; however in this work we show that isomorphism problems which stem from non-abelian cryptographic group actions can be viable building blocks for threshold signature schemes. In particular, we construct a full N-out-of-N threshold signature scheme, and discuss the efficiency issues arising from extending it to the generic T-out-of-N case. To give a practical outlook on our constructions, we instantiate them with two different flavors of code-based cryptographic group actions, respectively at the basis of the LESS and MEDS signature schemes, two of NIST’s candidates in the recent call for post-quantum standardization.