International Association
for Cryptologic Research

Although a memory-efficient practical collision attack has been recently proposed for 31-step \shas at ASIACRYPT 2024, the best practical collision attack on \shass still only reaches 28 steps, and the best theoretic collision attack on 31-step \shass has the time complexity of $2^{97.3}$. This is mainly due to the large state of \shass compared with \shas, despite their structural similarity. To enhance the collision attacks on \shass, we propose a new local collision by injecting difference at the message words $(W_9, W_{10}, W_{14}, W_{17}, W_{19})$, allowing us to achieve the first practical collision attack on 29 steps of \shass. Moreover, to improve the collision attack on 31-step \shass, we improve Liu et al.'s method to model the signed difference transition through Boolean functions, by introducing a novel model to capture the 2-bit conditions, which frequently occur in \shass characteristics. In this way, we can further improve the 31-step \shass characteristic and reduce the time complexity of the collision attack on 31-step \shass from $2^{97.3}$ to $2^{85.5}$.

Functional encryption (FE) which covers the notion of attribute-based encryption (ABE), is the cryptographic tool to realize fine-grained control on the accessibility of encrypted data. The traditional FE requires a central trusted authority to issue secret keys. It depends on the full-trust model, and is vulnerable to the security issue caused by key-escrow. While the registered FE (Reg-FE) achieves the zero-trust model and addresses the security issue by removing the use of central authority. It allows users to generate secret keys themselves and join the system by registering corresponding public keys to a curator. This work introduces delegated Reg-FE, which is a primitive with a new registration paradigm. It allows the registration of certain authorities that can issue secret keys for their respective classical FE sub-systems, beyond the prior work of registering plain users. Delegated Reg-FE implements a hybrid trust model within a two-level hierarchy. By redefining key escrow as a functional mechanism rather than a security concern, this model employs a zero-trust upper level which removes key-escrow, while the subsystem of each authority is locally full-trust and retains key-escrow mechanism. We construct four delegated Reg-FE schemes for functionalities that can be described as the 2\times 2 combinations of linear function and policy check. Namely, Delegated Reg-IPFE, Delegated Reg-ABE, Reg-IPFE with delegated ABE, and Reg-ABE with delegated IPFE. All concrete schemes support bounded registrations and delegations, and achieve standard adaptive security under MDDH assumption on prime-order bilinear group. Furthermore, these schemes only rely on black-box techniques. Technically, these schemes relies on dual-system techniques as prior registration-based works. And we devise a new "hierarchically invoked dual-system" technique on schemes which have sub-ABE delegation systems. Furthermore, we present a generic construction of Delegated Reg-FE from the combination of Reg-FE and FE. The instantiations of this generic construction demonstrate the feasibility of delegated Reg-FE, supporting arbitrary functions as well as unbounded numbers of registrations and delegations. However, this approach requires non-black-box techniques and achieves weaker semi-adaptive security without malicious registration, where the semi-adaptive means the adversary claims the challenge after seeing common reference string but before making any query. Its security relies solely on the underlying assumptions of the Reg-FE and FE components.

Proxy Re-Encryption (PRE) enables a proxy to transform ciphertexts encrypted under Alice's key into ciphertexts under Bob's key, allowing Bob to decrypt them. As a powerful cryptographic primitive, PRE has been extensively studied over the past two decades. However, an open problem remains unresolved, namely constructing an adaptively secure PRE scheme where the security reduction is tight. In this paper, we present the first PRE scheme that achieves adaptive security in a multi-challenge setting, with a tight security reduction, i.e., constant security loss O(1). In our setting, the adversary can obtain multiple challenge ciphertexts for multiple target users, capturing a more realistic and powerful adversary. In contrast, previous works established adaptive security only under the single-challenge setting, where the adversary is restricted to a single challenge query, and such schemes incur security losses of n^{O(log n)} for trees and chains, and n^{O(n)} for general graphs, where n is the number of users. Our construction is based on composite-order bilinear groups, and we prove the security in the standard model. The results indicate that our security guarantees do not degrade with respect to either the number of users or the number of ciphertexts, thanks to the tight reduction.

In the past decade, much progress has been made on proposing encryption schemes with multi-user security. However, no known work aims at constructing a Public-key Encryption with Keyword Search (PEKS) scheme that is secure in multi-user setting. PEKS is a well-known primitive to solve the problem of searching over encrypted data. In this paper, we fill the gap. For more realistic multi-user scenario, we consider a strong security notion. Specifically, the adversary can adaptively corrupt some users' secret keys, and can adaptively request searchable ciphertexts of related keywords under different public keys as well as trapdoors of related keywords under different secret keys. We present two multi-user PEKS schemes both under simple assumptions in the standard model to achieve this strong security notion. \text{\qquad}Technically, our first scheme is a variation of the Lewko-Waters identity-based encryption scheme, and our second scheme is a variation of the Wee identity-based encryption scheme. However, we need to prove that the presented public key encryption schemes are secure in the multi-user, multi-challenge setting under adaptive corruptions. We modify the dual system encryption methodology to meet the goal. In particular, the security loss is constant.

This work initiates the study of \emph{concrete} registered functional encryption (Reg-FE) beyond ``all-or-nothing'' functionalities: - We build the first Reg-FE for linear function or inner-product evaluation (Reg-IPFE) from pairing. The scheme achieves adaptive IND-security under $k$-Lin assumption in the prime-order bilinear group. A minor modification yields the first Registered Inner-Product Encryption (Reg-IPE) scheme from $k$-Lin assumption. Prior work achieves the same security in the generic group model. - We build the first Reg-FE for quadratic function (Reg-QFE) from pairing. The scheme achieves \emph{very selective} simulation-based security (SIM-security) under bilateral $k$-Lin assumption in the prime-order bilinear group. Here, ``very selective'' means that the adversary claims challenge messages, all quadratic functions to be registered and all corrupted users at the beginning. Besides focusing on the compactness of the master public key and helper keys, we also aim for compact ciphertexts in Reg-FE. Let $L$ be the number of slots and $n$ be the input size. Our first Reg-IPFE has \emph{weakly compact} ciphertexts of size $O(n\cdot\log L)$ while our second Reg-QFE has \emph{compact} ciphertexts of size $O(n+\log L)$. Technically, for our first Reg-IPFE, we employ \emph{nested} dual-system method within the context of Reg-IPFE; for our second Reg-QFE, we follow Wee's ``IPFE-to-QFE'' transformation [TCC' 20] but devise a set of new techniques that make our \emph{pairing-based} Reg-IPFE compatible. Along the way, we introduce a new notion named \emph{Pre-Constrained Registered IPFE} which generalizes slotted Reg-IPFE by constraining the form of functions that can be registered.

This paper presents the first generic black-box construction of registered attribute-based encryption (Reg-ABE) via predicate encoding [TCC'14]. The generic scheme is based on $k$-Lin assumption in the prime-order bilinear group and implies the following concrete schemes that improve existing results: - the first Reg-ABE scheme for span program in the prime-order group; prior work uses composite-order group; - the first Reg-ABE scheme for zero inner-product predicate from $k$-Lin assumption; prior work relies on generic group model (GGM); - the first Reg-ABE scheme for arithmetic branching program (ABP) which has not been achieved previously. Technically, we follow the blueprint of Hohenberger et al. [EUROCRYPT'23] but start from the prime-order dual-system ABE by Chen et al. [EUROCRYPT'15], which transforms a predicate encoding into an ABE. The proof follows the dual-system method in the context of Reg-ABE: we conceptually consider helper keys as secret keys; furthermore, malicious public keys are handled via pairing-based quasi-adaptive non-interactive zero-knowledge argument by Kiltz and Wee [EUROCRYPT'15].