Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Revisiting Beimel-Weinreb Weighted Threshold Secret Sharing Schemes
Get PDFA secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In a weighted threshold secret sharing scheme, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value.
For these access structures, the best general constructions were presented by Beimel and Weinreb [IPL 2006]: The scheme with perfect security has share size , while the scheme with computational security has share size polynomial in . However, these constructions require the use of shallow monotone sorting networks, which limits their practical use.
In this context, we revisit this work and provide variants of these constructions that are feasible in practice. This is done by considering alternative circuits and formulas for weighted threshold functions that do not require monotone sorting networks. We show that, under the assumption that subexponentially secure one-way functions exist, any WTAS over parties and threshold admits a computational secret sharing scheme where the size of the shares is and the size of the public information is . Moreover, we show that any authorized subset only needs to download bits of public information to recover the secret
Secure Showing of Partial Attributes
Get PDFAnonymous Attribute-Based Credentials (ABCs) allow users to prove possession of attributes while adhering to various authentication policies and without revealing unnecessary information. Single-use ABCs are particularly appealing for their lightweight nature and practical efficiency. These credentials are typically built using blind signatures, with Anonymous Credentials Light (ACL) being one of the most prominent schemes in the literature. However, the security properties of single-use ABCs, especially their secure showing property, have not been fully explored, and prior definitions and corresponding security proofs fail to address scenarios involving partial attribute disclosure effectively. In this work, we propose a stronger secure showing definition that ensures robust security even under selective attribute revelation. Our definition extends the winning condition of the existing secure showing experiment by adding various constraints on the subsets of opened attributes. We show how to represent this winning condition as a matching problem in a suitable bipartite graph, thus allowing for it to be verified efficiently. We then prove that ACL satisfies our strong secure showing notion without any modification. Finally, we define double-spending prevention for single-use ABCs, and show how ACL satisfies the definition
A Holistic Framework for Impossible Boomerang Attacks
Get PDFIn 2011, Lu introduced the impossible boomerang attack at DCC. This powerful cryptanalysis technique combines the strengths of the impossible differential and boomerang attacks, thereby inheriting the advantages of both cryptographic techniques. In this paper, we propose a holistic framework comprising two generic and effective algorithms and a MILP-based model to search for the optimal impossible boomerang attack systematically. The first algorithm incorporates any key guessing strategy, while the second integrates the meet-in-the-middle (MITM) attack into the key recovery process. Our framework is highly flexible, accommodating any set of attack parameters and returning the optimal attack complexity. When applying our framework to Deoxys-BC-256, Deoxys-BC-384, Joltik-BC-128, Joltik-BC-192, and SKINNYe v2, we achieve several significant improvements. We achieve the first 11-round impossible boomerang attacks on Deoxys-BC-256\ and Joltik-BC-128. For SKINNYe v2, we achieve the first 33-round impossible boomerang attack, then using the MITM approach in the key recovery attack, the time complexity is significantly reduced. Additionally, for the 14-round Deoxys-BC-384 and Joltik-BC-192, the time complexity of the impossible boomerang attack is reduced by factors exceeding 2^{27} and 2^{12}, respectively
Unleashing the Power of Differential Fault Attacks on QARMAv2
Get PDFQARMAv2 represents a family of lightweight block ciphers introduced in
ToSC 2023. This new iteration, QARMAv2, is an evolution of the original QARMA
design, specifically constructed to accommodate more extended tweak values while
simultaneously enhancing security measures. This family of ciphers is available in
two distinct versions, referred to as QARMAv2--, where ‘’ signifies the block
length, with options for both 64-bit and 128-bit blocks, and ‘’ signifies the key
length. In this paper, for the first time, we present differential fault analysis (DFA)
of all the QARMAv2 variants- QARMAv2-64, and QARMAv2-128 by introducing
an approach to utilize the fault propagation patterns at the nibble level, with the
goal of identifying relevant faulty ciphertexts and vulnerable fault positions. This
technique highlights a substantial security risk for the practical implementation of
QARMAv2. By strategically introducing six random nibble faults into the input of
the -th and -th backward rounds within the -round QARMAv2-64,
our attack achieves a significant reduction in the secret key space, diminishing it
from the expansive to a significantly more smaller set of size . Additionally,
when targeting QARMAv2-128-128, it demands the introduction of six random nibble
faults to effectively reduce the secret key space from to a remarkably reduced
. To conclude, we also explore the potential extension of our methods to conduct
DFA on various other iterations and adaptations of the QARMAv2 cryptographic
scheme. To the best of our knowledge, this marks the first instance of a differential
fault attack targeting the QARMAv2 tweakable block cipher family, signifying an
important direction in cryptographic analysis
Adaptor Signatures: New Security Definition and A Generic Construction for NP Relations
Get PDFAn adaptor signatures (AS) scheme is an extension of digital signatures that allows the signer to generate a pre-signature for an instance of a hard relation. This pre-signature can later be adapted to a full signature with a corresponding witness. Meanwhile, the signer can extract a witness from both the pre-signature and the signature. AS have recently garnered more attention due to its scalability and interoperability. Dai et al. [INDOCRYPT 2022] proved that AS can be constructed for any NP relation using a generic construction. However, their construction has a shortcoming: the associated witness is exposed by the adapted signature. This flaw poses limits the applications of AS, even in its motivating setting, i.e., blockchain, where the adapted signature is typically uploaded to the blockchain and is public to everyone.
To address this issue, in this work we augment the security definition of AS by a natural property which we call witness hiding. We then prove the existence of AS for any NP relation, assuming the existence of one-way functions. Concretely, we propose a generic construction of witness-hiding AS from signatures and a weak variant of trapdoor commitments, which we term trapdoor commitments with a specific adaptable message. We instantiate the latter based on the Hamiltonian cycle problem. Since the Hamiltonian cycle problem is NP-complete, we can obtain witness hiding adaptor signatures for any NP relation
Impossible Boomerang Distinguishers Revisited
Get PDFThe Impossible Boomerang Attack (IBA) has shown significant power in evaluating the security of block ciphers, such as AES. However, current studies still lack foundational theory, user guild and universal method for constructing IBDs. This paper addresses these gaps through comprehensive research. Theoretically, we establish a new framework for constructing a series of IBDs by differential propagation, state propagation, and generalized boomerang tables. We rigorously prove their inclusion relations, resulting in a complete theory and hierarchical apply strategy for both single-key and related-key settings. We further analyze IBD constructions in two types of related-key settings: two-related-keys with arbitrary schedules and four-related-keys with linear schedules, structurally in a unified way. Technically, we develop a scheduling algorithm and a general SAT-based method to search for IBDs across various block cipher designs, including SPN, Feistel, and ARX. Additionally, we propose several strategies to enhance the search process. As applications, we derive (RK-)IBDs for 10 block ciphers, almost for the first time. Compared to impossible differentials, our IBDs are at least as effective, such as DES and PRESENT. Notably, we achieve 1 more round on PRINTcipher48 in single-key setting; 2 more rounds on AES-128, and 1 or 2 more rounds on SPECK variants in two-related-keys settings; 1, 4, 2 more rounds on GIFT-64, CHAM-64/128 and CHAM-128/256 in four-related-keys settings. We also obtain full-round RK-IBDs on GOST. Compared to current IBDs, we achieve 1, 1 more rounds on SKINNY-64/192 and SKINNYee. Furthermore, as an applied case of derived IBDs, we present a 31-round IBA on SKINNYee, which is the first 31-round attack on SKINNYee and the best result to date
Guidance for Efficient Selection of Secure Parameters for Fully Homomorphic Encryption
Get PDFThe field of Fully Homomorphic Encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners from neighbouring fields such as machine learning have sought to understand FHE to provide privacy to their work. Unfortunately, selecting secure and efficient parameters in FHE is a daunting task due to the many interdependencies between the parameters involved. In this work, we solve this problem by moving away from the standard parameter selection procedure, introducing formulas which provide secure and optimal parameters for any lattice-based scheme. We build our formulas from a strong theoretical foundation based on cryptanalysis against LWE
ProxCode: Efficient Biometric Proximity Searchable Encryption from Error Correcting Codes
Get PDFThis work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and secure multimaps. The multimap associates LSH outputs as keywords to biometrics as values.
When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode that inserts shares of a linear secret sharing into the map instead of the full biometric. Instead of choosing shares independently, shares are correlated so exactly one share is associated with each keyword/LSH output. As a result, one can rely on a map instead of a multimap. Secure maps are easier to construct with low leakage than multimaps.
This approach reduces the required number of LSHs for a fixed accuracy for many parameters. Our scheme improves most when combining a high accuracy requirement with a biometric with large underlying noise. Our approach builds on any secure map. To benchmark, we implement the scheme using the tree based oblivious map of Wang et al. (CCS, 2014) and evaluate efficiency and accuracy for iris, synthetic, and random data.
In comparison to the recent work of Ha et al. (Codaspy 2025), for the largest tested parameters and comparable true accept rate, our work reduces the number of LSHs by a factor of 4.3. This reduction impacts all efficiency, our rounds are smaller by 2, storage by a factor of 6.5, and parallel time by a factor of 8
A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
Get PDFWe construct an adaptively-sound succinct non-interactive argument (SNARG) for NP in the CRS model from sub-exponentially-secure indistinguishability obfuscation () and sub-exponentially-secure one-way functions. Previously, Waters and Wu (STOC 2024), and subsequently, Waters and Zhandry (CRYPTO 2024) showed how to construct adaptively-sound SNARGs for NP by relying on sub-exponentially-secure indistinguishability obfuscation, one-way functions, and an additional algebraic assumption (i.e., discrete log, factoring, or learning with errors). In this work, we show that no additional algebraic assumption is needed and vanilla (sub-exponentially-secure) one-way functions already suffice in combination with
A Note on Zero-Knowledge for NP and One-Way Functions
Get PDFWe present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be useful for didactic purposes. We also remark that the same result hold for (imperfect) iO for 3CNF, or Witness Encryption for NP