287 research outputs found
Expressive encryption systems from lattices
No full textIn this survey, we review a number of the many “expressive”\ud
encryption systems that have recently appeared from lattices, and explore the innovative techniques that underpin them
Recovering the Tight Security Proof of SPHINCS+
No full textIn 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the SPHINCS+ construction. This work gives a new tight security proof for SPHINCS+. The flaw can be traced back to the security proof for the Winternitz one-time signature scheme (WOTS) used within SPHINCS+. In this work, we give a stand-alone description of the WOTS variant used in SPHINCS+ that we call WOTS-TW. We provide a security proof for WOTS-TW and multi-instance WOTS-TW against non-adaptive chosen message attacks where the adversary only learns the public key after it made its signature query. Afterwards, we show that this is sufficient to give a tight security proof for SPHINCS+. We recover almost the same bound for the security of SPHINCS+, with only a factor w loss compared to the previously claimed bound, where w is the Winternitz parameter that is commonly set to 16. On a more technical level, we introduce new lower bounds on the quantum query complexity for generic attacks against properties of cryptographic hash functions and analyse the constructions of tweakable hash functions used in SPHINCS+ with regard to further security properties
BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications
No full textWe give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the protocol.Using these new primitives and techniques, we give instantiations of the most compact lattice-based ring and group signatures schemes. The improvement in signature sizes over prior works ranges between 25% and 2X. Perhaps of even more significance, the size of the user public keys, which need to be stored somewhere publicly accessible in order for ring signatures to be meaningful, is reduced by factors ranging from 7X to 15X. In what could be of independent interest, we also provide noticeably improved proofs for integer relations which, together with one-out-of-many proofs are key components of confidential payment systems.COMPSE
Failing Gracefully:Decryption Failures and the Fujisaki-Okamoto Transform
No full textIn known security reductions for the Fujisaki-Okamoto transformation, decryption failures are handled via a reduction solving the rather unnatural task of finding failing plaintexts given the private key, resulting in a Grover search bound. Moreover, they require an implicit rejection mechanism for invalid ciphertexts to achieve a reasonable security bound in the QROM. We present a reduction that has neither of these deficiencies: We introduce two security games related to finding decryption failures, one capturing the computationally hard task of using the public key to find a decryption failure, and one capturing the statistically hard task of searching the random oracle for keyindependent failures like, e.g., large randomness. As a result, our security bounds in the QROM are tighter than previous ones with respect to the generic random oracle search attacks: The attacker can only partially compute the search predicate, namely for said key-independent failures. In addition, our entire reduction works for the explicit-reject variant of the transformation and improves significantly over all of its known reductions. Besides being the more natural variant of the transformation, security of the explicit reject mechanism is also relevant for side channel attack resilience of the implicit-rejection variant. Along the way, we prove several technical results characterizing preimage extraction and certain search tasks in the QROM that might be of independent interest.</p
Factoring Products of Braids via Garside Normal Form
No full textBraid groups are infinite non-abelian groups naturally arising from geometric braids. For two decades they have been proposed for cryptographic use. In braid group cryptography public braids often contain secret braids as factors and it is hoped that rewriting the product of braid words hides individual factors. We provide experimental evidence that this is in general not the case and argue that under certain conditions parts of the Garside normal form of factors can be found in the Garside normal form of their product. This observation can be exploited to decompose products of braids of the form ABC when only B is known. Our decomposition algorithm yields a universal forgery attack on WalnutDSA™, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptography. Our attack on WalnutDSA™ can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments. Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.</p
Generic Constructions of RIBE via Subset Difference Method
No full textRevocable identity-based encryption (RIBE) is an extension of IBE which can support a key revocation mechanism, and it is important when deploying an IBE system in practice. Boneh and Franklin (Crypto\u2701) presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key updates is linear in the number of users in the system. The first generic construction of RIBE is presented by Ma and Lin with complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. Recently, Lee proposed a new generic construction using the subset difference (SD) method by combining IBE,identity-based revocation (IBR), and two-level HIBE schemes.
In this paper, we present a new primitive called Identity-Based Encryption with Ciphertext Delegation (CIBE) and propose a generic construction of RIBE scheme via subset difference method using CIBE and HIBE as building blocks. CIBE is a special type of Wildcarded IBE (WIBE) and Identity-Based Broadcast Encryption (IBBE). Furthermore, we show that CIBE can be constructed from IBE in a black-box way. Instantiating the underlying building blocks with different concrete schemes, we can obtain a RIBE scheme with constant-size public parameter, ciphertext, private key and key updates in the selective-ID model. Additionally, our generic RIBE scheme can be easily converted to a sever-aided RIBE scheme which is more suitable for lightweight devices
Safety in Numbers:On the Need for Robust Diffie-Hellman Parameter Validation
No full textISSN:0302-9743ISSN:1611-3349ISSN:1611-334
Decryption Failure Attacks on IND-CCA Secure Lattice-Based Schemes
No full textIn this paper we investigate the impact of decryption failures on the chosen-ciphertext security of lattice-based primitives. We discuss a generic framework for secret key recovery based on decryption failures and present an attack on the NIST Post-Quantum Proposal ss-ntru-pke. Our framework is split in three parts: First, we use a technique to increase the failure rate of lattice-based schemes called failure boosting. Based on this technique we investigate the minimal effort for an adversary to obtain a failure in three cases: when he has access to a quantum computer, when he mounts a multi-target attack or when he can only perform a limited number of oracle queries. Secondly, we examine the amount of information that an adversary can derive from failing ciphertexts. Finally, these techniques are combined in an overall analysis of the security of lattice based schemes under a decryption failure attack. We show that an attacker could significantly reduce the security of lattice based schemes that have a relatively high failure rate. However, for most of the NIST Post-Quantum Proposals, the number of required oracle queries is above practical limits. Furthermore, a new generic weak-key (multi-target) model on lattice-based schemes, which can be viewed as a variant of the previous framework, is proposed. This model further takes into consideration the weak-key phenomenon that a small fraction of keys can have much larger decoding error probability for ciphertexts with certain key-related properties. We apply this model and present an attack in detail on the NIST Post-Quantum Proposal – ss-ntru-pke – with complexity below the claimed security level.sponsorship: The authors would like to thank Tancrede Lepoint and the anonymous reviewers for their helpful comments. They would also like to thank Andreas Hulsing for interesting discussions. This work was supported in part by the Research Council KU Leuven: C16/15/058, by the European Commission through the Horizon 2020 research and innovation programme Cathedral ERC Advanced Grant 695305, by the Research Council KU Leuven grants C14/18/067 and STG/17/019, by the Norwegian Research Council (Grant No. 247742/070), by the Swedish Research Council (Grant No. 2015-04528), by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and by the Swedish Foundation for Strategic Research (SSF) project RIT17-0005. (Research Council KU Leuven|C14/18/067, Research Council KU Leuven|STG/17/019, Research Council KU Leuven|C16/15/058, European Commission through the Horizon 2020 research and innovation programme Cathedral ERC Advanced Grant|695305, Norwegian Research Council|247742/070, Swedish Research Council|2015-04528, Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation, Swedish Foundation for Strategic Research (SSF)|RIT17-0005)status: Publishe
Practical Provably Secure Flooding for Blockchains
No full textISSN:0302-9743ISSN:1611-3349ISSN:1611-334
Analysis of bilinear pairing-based accumulator for identity escrowing
No full textAn accumulator based on bilinear pairings was proposed at CT-RSA'05. Here, it is first demonstrated that the security model proposed by Lan Nguyen does lead to a cryptographic accumulator that is not collision resistant. Secondly, it is shown that collision-resistance can be provided by updating the adversary model appropriately. Finally, an improvement on Nguyen's identity escrow scheme, with membership revocation based on the accumulator, by removing the trusted third party is proposed
- …
