Reachability query, which determines whether a path exists between any two nodes in a graph, has been the cornerstone of graph operation research for decades. Traditional algorithms, such as depth-first search and transitive closure, are often limited by either slow query or substantial storage. Extensive efforts have increasingly focused on designing reachability indexes to balance the tradeoff between index space and query time. However, existing solutions are limited to specific tradeoff points and lack theory for adjustable, quantifiable tradeoffs. In this work, we introduce Reachability-state Encoding (RE), which adjusts the number of encoded node pairs per chunk to affect compression ratio and decoding time, thus allowing for a smooth transition between the minimal storage and the fastest query. We establish theoretical upper bounds for the minimum encoding length of RE in relation to the size and entropy of reachability-states, which quantifies the limits of compression within the encoding process and ensures superior performance in dense graphs compared to traditional methods. We have implemented a prototype algorithm, RE-toy, to validate the effectiveness of RE. Through experiments conducted on both synthetic and real-world graphs, RE-toy consistently achieves numerous optimal tradeoff points in space-time, demonstrating robust performance across graphs of varying densities. RE thus provides a practical and adaptable approach for managing the balance between storage demands and computational efficiency in reachability queries.
The increasing popularity of container technology raises significant challenges in efficiently storing millions of container images in registries to enable fast on-demand image pulling. This is further complicated by (1) registries are geographically distributed, with independent and heterogeneous storage resources; (2) container images are pulled in layers, but can be stored at different levels of granularity, i.e., layer-level or file-level, each with varying storage requirement and pulling latency. To address the above challenges, we propose MIS, a multi-granularity image storage strategy, for distributed registries to determine the storage granularity and schedule image storage collaboratively, aiming to reduce the image pulling latency while improving the storage utilization. We formulate the image storage problem into a nonlinear mixed-integer programming form with NP-hardness by incorporating both layer-level and file-level storage constraints. We propose a low computational complexity algorithm via randomized rounding with a guaranteed approximation ratio. Extensive experimental results demonstrate the effectiveness of our strategy, with image pulling latency reductions of 28.67%, 21.69%, and 28.94% respectively compared to the state-of-the-art solutions.
Controllability has become a crucial aspect of trustworthy machine learning, enabling learners to meet predefined targets and adapt dynamically at test time without requiring retraining as the targets shift. We provide a formal definition of controllable learning (CL), and discuss its applications in information retrieval (IR) where information needs are often complex and dynamic. The survey categorizes CL according to what is controllable (e.g., multiple objectives, user portrait, scenario adaptation), who controls (users or platforms), how control is implemented (e.g., rule-based method, Pareto optimization, hypernetwork, and others), and where to implement control (e.g., pre-processing, in-processing, post-processing methods). Then, we identify challenges faced by CL across training, evaluation, task setting, and deployment in online environments. Additionally, we outline promising directions for CL in theoretical analysis, efficient computation, empowering large language models, application scenarios, and evaluation frameworks.
The rapid growth of Internet of Things (IoT) devices has increased security risks due to cryptographic misuse in firmware, including vulnerable algorithms and misconfigurations. Accurate identification of cryptographic algorithms in firmware is fundamental for firmware analysis, while existing tools, usually designed for x86 platform, struggle with IoT-specific architectures, file formats, and instruction sets. Currently, it lacks a unified and scalable evaluation framework, and standard datasets. Besides, there are challenges to be addressed: unverified tool applicability, unexplored impacts of instruction sets and compilation optimizations, and insufficient empirical data on cryptographic implementations. To this end, this study proposes a modular framework for IoT firmware cryptographic algorithm identification, which supports plug-and-play integration of tools via standardized interfaces, a three-dimensional evaluation metric (algorithm types, function counts, constant quantities) and a standardized test dataset covering seven cryptographic libraries, six instruction set architectures, and four compilation optimization levels. Through four experimental studies including tool performance comparison, compilation optimization impact analysis, architecture difference evaluation, and real-world firmware cryptographic usage investigation, it demonstrates that constant-based identification techniques achieve optimal performance in IoT scenarios while revealing the impact mechanisms of ISA architectures and compilation optimizations on identification effectiveness. It also provides methodological guidance and empirical data foundations for IoT firmware cryptographic algorithm identification studies in the future.
Generative artificial intelligence is capable of generating high-quality, fine-grained 3D assets with realistic visual effects. These 3D assets are often utilized in various scenarios that demand different levels of security permissions. As such, they need to display tiered visual effects while ensuring that the content remains protected. Recently, several researchers have proposed that traditional security encryption methods might not be sufficient to fulfill these requirements. We conduct an in-depth analysis of the structure of generative 3D assets and their visually salient features. Based on this analysis, we propose an encryption scheme for generative 3D assets that achieves tiered visual effects upon decryption. Specifically, a novel coordinate fine-grained regularization method is employed to partition different sub blocks, and ring encryption is implemented, followed by generating keys at different levels, ultimately constructing an encryption scheme with tiered visual effects. Experimental results demonstrate that the proposed scheme not only meets diverse security requirements but also effectively addresses the complexity issues in processing large-scale 3D assets.
With the rapid growth of Internet of Things (IoT), ensuring the security of devices in resource-constrained environments has become increasingly critical. In this context, the design of lightweight cryptographic algorithms is essential, with a particular emphasis on constructing optimal linear layers to enhance their efficiency and security. An optimal linear layer should simultaneously achieve strong cryptographic properties, while minimizing the number of exclusive OR (XOR) gates required for implementation. Previous research has primarily focused on optimizing existing linear layers. Only a few studies have explored the construction of new linear layers, often employing classical structures such as Feistel and Lai-Massey. However, these studies typically achieve optimality only for specific dimensions or branch numbers. Furthermore, while they aim to construct high-dimensional linear layers, they often result in increased costs for lower-dimensional cases.
In this paper, we present a novel method for constructing optimal linear layers by formulating the problem as a satisfiability (SAT) problem. A major obstacle in previous research was the inability to efficiently search for optimal linear layers as the dimension increased. We overcome this challenge by using our key insight into the relationship between linear layers and the arrangement of XOR gates in their implementation. This understanding allows us to extend the constructible dimension up to 14, significantly beyond what was previously achievable. Moreover, we are able to construct optimal linear layers for arbitrary branch numbers in dimensions ranging from 4 to 12. Finally, we construct linear layers for dimensions ranging from 4 to 14 that match or surpass the best known results in both cryptographic properties and implementation cost. Furthermore, we systematically construct involutory linear layers for dimensions 4 to 14, addressing a gap that has remained open in previous research.
Commit-and-prove succinct non-interactive arguments of knowledge (CP-SNARKs) are an important class of SNARKs that allow proving the knowledge of a witness committed beforehand. They are crucial in proving composite statements that combine algebraic and non-algebraic statements. However, existing CP-SNARKs only support constraint systems with degree-2 gates, limiting their ability to express non-algebraic statements succinctly. We propose a new family of CP-SNARKs for Customizable Constraint Systems. The new family, named CP-SuperSpartan, supports high-degree gates, eliminates expensive fast Fourier transform operations and supports a general commit-and-prove relation including multiple commitments to different slots of the witness. CP-SuperSpartan has several instantiations based on different multilinear polynomial commitment schemes (PCS). 1) When using pairing-based PCS, CP-SuperSpartan provides the same universally updatable setup as LegoSNARK (CCS’19), but it reduces the proof size and verifier complexity from to while maintaining the same prover complexity, where is the circuit size. 2) When using discrete-logarithm-based PCS, CP-SuperSpartan provides a transparent setup and achieves proof size while the smallest proof size of existing transparent CP-SNARKs is . 3) When using PCS based on interactive oracle proof of proximity, CP-SuperSpartan provides a transparent setup and firstly achieves prover complexity, proof size and verifier complexity while the number of public-key operations for both the prover and verifier is independent of .
Decentralized data sovereignty and secure data exchange are regarded as foundational pillars of the new era. Attribute-based encryption (ABE) is a promising solution that enables fine-grained access control in data sharing. Recently, Hohenberger et al. (Eurocrypt 2023) introduced registered ABE (RABE) to eliminate trusted authority and gain decentralization. Users generate their own public and secret keys and then register their keys and attributes with a transparent key curator. However, RABE still suffers from heavy decryption overhead. A natural approach to address this issue is to outsource decryption to a decryption cloud server (DCS). In this work, we propose the first auditable RABE scheme with reliable outsourced decryption (ORABE) based on blockchain. First, we achieve verifiability of transform ciphertext via a verifiable tag mechanism. Then, the exemptibility, which ensures that the DCS escapes false accusations, is guaranteed by zero knowledge fraud proof under the optimistic assumption. Additionally, our system achieves fairness and auditability to protect the interests of all parties through blockchain. Finally, we give concrete security and theoretical analysis and evaluate our scheme on Ethereum to demonstrate feasibility and efficiency.
The original Grover’s algorithm suffers from the souffle problem, which means that the success probability of quantum search decreases dramatically if the iteration time is too small or too large from the right time. To overcome the souffle problem, the fixed-point quantum search with an optimal number of queries was proposed [Phys. Rev. Lett. 113, 210501 (2014)], which always finds a marked state with a high probability when a lower bound of the proportion of marked states is given. The fixed-point quantum search relies on a key lemma regarding the explicit formula of recursive quasi-Chebyshev polynomials, but its proof is not given explicitly. In this work, we give a detailed proof of this lemma, thus providing a sound foundation for the correctness of the fixed-point quantum search. This lemma may be of independent interest as well, since it expands the mathematical form of the recursive relation of Chebyshev polynomials of the first kind, and it also constitutes a key component in overcoming the souffle problem of quantum walk-based search algorithms, for example, robust quantum walk search on complete bipartite graphs [Phys. Rev. A 106, 052207 (2022)]. The lemma is also central to a recently proposed quantum algorithm named quantum phase discrimination, which has become a fundamental subroutine in quantum search on graphs [arxiv: 2504.15194]. Hopefully, more applications of the lemma will be found in the future.