Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Tightly Secure Inner-Product Functional Encryption Revisited: Compact, Lattice-based, and More
Get PDFCurrently, the only tightly secure inner-product functional encryption (IPFE) schemes in the multi-user and multi-challenge setting are the IPFE scheme due to Tomida (Asiacrypt 2019) and its derivatives. However, these tightly secure schemes have large ciphertext expansion and are all based on the matrix decisional Diffie-Hellman (DDH) assumption.
To improve the efficiency of tightly secure IPFE and enrich the diversity of its underlying assumptions, we construct a set of tightly secure IPFE schemes, with very compact ciphertexts and efficient algorithms, from the matrix DDH, the decisional composite residuosity (DCR), and the learning-with-errors (LWE) assumptions, respectively. In particular,
-- our DDH-based scheme has about 5×~100× shorter public/secret keys, 2×~2.9× shorter ciphertexts and about 5×~100× faster algorithms than all existing tightly secure IPFE schemes, at the price of 3~7 bits of decreased security level, resolving an open problem raised by Tomida (Asiacrypt 2019);
-- our DCR-based scheme constitutes the first tightly secure IPFE scheme from the DCR assumption;
-- our LWE-based scheme is the first almost tightly secure IPFE scheme from lattices, hence achieving post-quantum security.
We obtain our schemes by proposing a generic and flexible construction of IPFE with a core technical tool called two-leveled inner-product hash proof system (TL-IP-HPS). Specifically, our IPFE construction is in a compact design, and to achieve tight security, we propose an economic proof strategy to reuse the spaces in such compact IPFE. Interestingly, our new proof strategy also applies to the loosely secure IPFE schemes proposed by Agrawal, Libert and Stehlé (Crypto 2016), and yields a tighter bound on their security loss
Probabilistic Skipping-Based Data Structures with Robust Efficiency Guarantees
Get PDFProbabilistic data structures like hash tables, skip lists, and treaps support efficient operations through randomized hierarchies that enable skipping elements, achieving sub-linear query complexity on average for perfectly correct responses. They serve as critical components in performance-sensitive systems where correctness is essential and efficiency is highly desirable. While simpler than deterministic alternatives like balanced search trees, these structures traditionally assume that input data are independent of the structure\u27s internal randomness and state - an assumption questionable in malicious environments - potentially leading to a significantly increased query complexity. We present adaptive attacks on all three aforementioned structures that, in the case of hash tables and skip lists, cause exponential degradation compared to the input-independent setting. While efficiency-targeting attacks on hash tables are well-studied, our attacks on skip lists and treaps provide new insights into vulnerabilities of skipping-based probabilistic data structures. Next, we propose simple and efficient modifications to the original designs of these data structures to provide provable security against adaptive adversaries. Our approach is formalized through Adaptive Adversary Property Conservation (AAPC), a general security notion that captures deviation from the expected efficiency guarantees in adversarial scenarios. We use this notion to present rigorous robustness proofs for our versions of the data structures. Lastly, we perform experiments whose empirical results closely agree with our analytical results
Qlapoti: Simple and Efficient Translation of Quaternion Ideals to Isogenies
Get PDFThe main building block in isogeny-based cryptography is an algorithmic
version of the Deuring correspondence, called . This algorithm
takes as input left ideals of the endomorphism ring of a supersingular elliptic
curve and computes the associated isogeny. Building on ideas from , the
framework by Page and Robert reduces this problem to solving a certain
norm equation. The current state of the art is however unable to efficiently
solve this equation, and resorts to a relaxed version of it instead. This
impacts not only the efficiency of the procedure, but also its
success probability. The latter issue has to be mitigated with complex and
memory-heavy rerandomization procedures, but still leaves a
gap between the security analysis and the actual implementation of
cryptographic schemes employing as a subroutine.
For instance, in the failure probability is still which
is not cryptographically negligible.
The main contribution of this paper is a very simple and efficient algorithm
called which approaches the norm equation from directly,
solving all the aforementioned problems at once. First, it makes the
subroutine between and times faster. This
signigicantly improves the speed of schemes using this subroutine, including
notably and \prism. On top of that, has a cryptographically
negligible failure probability. This eliminates the need for rerandomization,
drastically reducing memory consumption, and allows for cleaner security
reductions
Query-Optimal IOPPs for Linear-Time Encodable Codes
Get PDFWe present the first Interactive Oracle Proofs of Proximity (IOPPs) for linear-time encodable codes that achieve -bit security with linear prover time and optimal query complexity. This implies (via standard techniques) the first IOP for NP with prover time and query complexity, and hence also the first SNARK for NP in the random oracle model with linear prover time and proof size.
The technical core of our result is a novel IOPP for tensor codes. Our tensor IOPP leverages error correction in a novel way to reduce checking proximity of a purported codeword to the tensor code to checking the proximity of -many of its columns to the column code. Our key insight is that it in fact suffices to just prove that a constant fraction of these new proximity claims hold (as opposed to all of them). We devise a new lossy batching protocol that provides the foregoing guarantee with just query complexity. By combining this tensor IOPP with prior codeswitching reductions, we obtain IOPPs for a large class of linear-time encodable codes.
We complement our IOPP construction with a lower bound that shows that, when proving proximity to constant-rate codes, one cannot construct IOPPs with query complexity better than . This establishes the optimality of our IOPP\u27s query complexity
Attribute-based Quantum Broadcast Encryption with Composite Policies via Symmetric Unitary t-Designs
Get PDFIn an emerging era of quantum technologies, securing quantum communications is paramount. In this paper, we introduce two frameworks for attribute-based quantum broadcast encryption (AB-QBE), enabling fine-grained access control over sensitive quantum data. The first scheme, Multi-Policy Quantum Private Broadcast Encryption (MP-QPBE), leverages symmetric unitary -designs to construct a protocol where decryption is possible upon satisfying a composite set of access policies simultaneously. This approach ensures that a user can only access the broadcasted quantum state if their attributes fulfill multiple predefined criteria. In our MP-QPBE, we first perform symmetrization of the initial quantum message for the encryption of the tensor product of distinct pure states, a scenario not directly addressed by previous quantum private broadcasting schemes. We demonstrate that this method is information-theoretically secure. The second scheme, Component-wise Independent Quantum Broadcast Encryption (CI-QBE), offers an alternative, lossless approach where each quantum message is encrypted independently using a unitary -design. It provides greater flexibility and is applicable to arbitrary quantum states, including mixed states, without the information loss inherent in symmetrization. We provide a comprehensive security analysis for both constructions, proving their robustness against unauthorized users and adversaries with quantum side information. A comparative analysis highlights the trade-offs between the two schemes in terms of security guarantees, quantum resource requirements, and practical applicability, offering a nuanced perspective on designing secure multi-user quantum communication systems
Multi-Message Quantum Broadcast with Fine-Grained Access Control
Get PDFSeveral subscription-based systems require fine-grained,
dynamic access control, which traditional broadcast
encryption schemes fail to handle efficiently. Attribute-based
and policy-based access structures offer a flexible and scalable
solution by encoding access rules directly into the encryption
mechanism. With the advent and development of quantum
networks, attribute-based and policy-based quantum broadcast
encryption (PBQBE) becomes necessary for enforcing such
controls securely in a post-quantum world. In this paper, we
present a general construction of quantum broadcast encryption
for multiple messages simultaneously, based on routing and
traversing a given attribute-based and, consequently, a policy-based
access tree when a user satisfies a unique policy. Our
scheme can handle dynamic systems with frequently changing
access patterns and can be deployed seamlessly with classical
systems. Compared to existing constructions, our scheme offers
hierarchical access, policy control, scalability, and revocation
while maintaining provable security guarantees
SoK: Blockchain Consensus in the Quantum Age
Get PDFConsensus protocols are an important building block in blockchain and blockchain-based systems. The recent focus in developing practical quantum computers reinforces the importance of designing quantum-resistant cryptographic protocols, and in the context of this paper quantum-resistant consensus protocols. In this paper, we systematically review the extant literature on quantum-resistant consensus protocols published between 2019 and 2024. As part of
the review, we identify a number of limitations and challenges and discuss potential future research directions
Lower Bounding Update Frequency in Short Accumulators and Vector Commitments
Get PDFWe study the inherent limitations of additive accumulators and updatable vector commitments (VCs) with constant-size digest (i.e., independent of the number of committed elements).
Specifically, we prove two lower bounds on the expected number of membership proofs that must be updated when a \emph{single} element is added (or updated) in such data structures. Our results imply that when the digest bit length approaches the concrete security level, then the expected number of proofs invalidated due to an append operation for a digest committing to elements is nearly maximal: in the case of exponential-size universes, and for super-polynomial universes. Our results have significant implications for stateless blockchain designs relying on constant-size VCs, suggesting that the overhead of frequent proof updates may offset the benefits of reducing global state storage
On Achieving ``Best-in-the-Multiverse\u27\u27 MPC
No full textThe notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees: guaranteed output delivery against an honest majority and security with abort against a dishonest majority and provided tight upper and lower bounds in the presence of computationally bounded, i.e., PPT adversaries. Another line of works starting from the work of Chaum (CRYPTO 1989) considered protocols that simultaneously achieved security against an unbounded adversary corrupting a minority of the parties and security against arbitrary corruption by a PPT adversary.
In this work, we generalize previous work to investigate a fundamental challenge of designing an MPC in a multiverse where security is specified with respect to (1) GOD, (2) fairness, (3) security w.r.t. unbounded adversaries, and (4) security with abort. The work of Lucas et al. (PODC 2010) resolved this question when considering threshold adversaries; however, the case of general adversary structures remains open. Our main result completely characterizes when a protocol can simultaneously achieve all properties. Namely, given adversary structures and , we provide tight upper and lower bounds for when an MPC protocol can provide GOD, fairness, and security with abort respectively for unbounded and PPT adversaries w.r.t. these adversary structures
MDS Diffusion Layers for Arithmetization-Oriented Symmetric Ciphers: The Rotational-Add Construction
Get PDFWe introduce the rotational-add diffusion layers aimed for applications in the design of arithmetization-oriented (AO) symmetric ciphers, such as fully homomorphic encryption (FHE)-friendly symmetric ciphers. This generalizes the rotational-XOR diffusion layers which have been utilized in the design of many important conventional symmetric ciphers like SHA-256, SM4, ZUC and Ascon. A rotational-add diffusion layer is defined over the finite field for arbitrary prime , enabling implementations using only rotations and modular additions/subtractions. The advantage of using such diffusion layers in AO ciphers is that, the costs of scalar multiplications can be reduced since the appearing scalars include only , thus the total costs depend on sizes of the rotation offsets. In this paper, we investigate characterizations and constructions of lightest rotational-add diffusion layers over that are maximum distance separable (MDS) with a focus on the case . It turns out that the minimum achievable size of the rotation offsets is 5 subject to the MDS property constraint. We specify a large class of rotational-add diffusion layers with 5 rotations and traverse all possible patterns of appearance of the scalars . In four cases we can derive computationally tractable necessary and sufficient conditions for the rotational-add diffusion layers to attain the MDS property. These conditions enable explicit characterization of suitable primes for given parameters. Leveraging these results, we construct three distinct families of rotational-add MDS diffusion layers applicable to AO ciphers. Although a rotational-add diffusion layer with 7 rotations and only additions has already been used in the design of the FHE-friendly block cipher YuX recently, to our knowledge, our work presents the first systematic theoretical characterization of rotational-add MDS diffusion layers and provides explicit constructions of them