Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
XOCB: Beyond-Birthday-Bound Secure Authenticated Encryption Mode with Rate-One Computation (Full Version)
Get PDFWe present a new block cipher mode of operation for authenticated encryption (AE), dubbed XOCB, that has the following features: (1) beyond-birthday-bound (BBB) security based on the standard pseudorandom assumption of the internal block cipher if the maximum block length is sufficiently smaller than the birthday bound, (2) rate-1 computation, and (3) supporting any block cipher with any key length. Namely, XOCB has effectively the same efficiency as the seminal OCB while having stronger quantitative security without any change in the security model or the required primitive in OCB. Although numerous studies have been conducted in the past, our XOCB is the first mode of operation to achieve these multiple goals simultaneously
Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott
Get PDFIn the isogeny-based track of post-quantum cryptography, optimal instances of the signature scheme SQISign rely on primes such that is smooth. In 2021 a new approach to find those numbers was discovered using solutions to the Prouhet-Tarry-Escott (PTE) problem. With these solutions we can sieve for smooth integers and with a difference of fixed by the solution. Then some and are smooth integers hopefully enclosing a prime. They took many different PTE solutions and combined them into a tree to process them more efficiently. But for larger numbers there are fewer promising PTE solutions so their advantage over the naive approach (checking a single solution at a time) fades.
For a single PTE solution the search can be optimised for the corresponding and allows to check smoothness only for those integers that are divisible by . In this work we investigate such optimisations and show a significant speed-up compared to the naive approach - both heuristically and empirically. Along the way we compute the number of roots of a given polynomial modulo prime powers and give an upper bound for the number of roots modulo a composite number
PassPro: A Secure Password-based Authentication Mechanism using SHF
Get PDFThe password-based authentication system is a widely used authentication mechanism. However, it has several issues, including guessing attacks, dictionary attacks, rainbow table attacks, collision attacks, domino effects, phishing attacks, and database leakage issues. To avoid these attacks, FIDO authentication avoids passwords and uses a public key to implement a challenge-response-based and digital signature-based authentication mechanism. It implements a passwordless authentication mechanism to avoid various attacks that are present in password-based authentication mechanisms. The FIDO authentication mechanism stores the private key in the client\u27s devices. Therefore, FIDO authentication is susceptible to device-specific issues, so cross-platform management becomes a concern. This issue is overcome by passkeys synchronizing with the cloud; however, hardware dependency is still an issue for such a system. The security of such a system is entirely dependent on the security of the hardware.
To address these issues, we present a client-side password hashing method called PassPro. PassPro uses a shuffle and hash function (SHF) to implement PassPro. The SHF is used to create a unique hash value for two publicly known words using a secret context. The SHF is used to create a unique hash value on the client side, preventing the transmission of the raw password to the server. Moreover, PassPro can protect the password database using two different methods: PassPro with encryption (PassProE) and PassPro with SHF (PassProS). PassProE encrypts the password database using mutually reproducible secret keys instead of using hashing, such as Argon2i. PassProS hashes the password database with SHF. In this paper, we exemplify how PassPro can prevent various attacks, including guessing attacks, dictionary attacks, rainbow table attacks, collision attacks, domino effects, phishing attacks, and database leakage issues. Moreover, PassPro users can reuse their password in different or the same domains. Also, PassPro guarantees that adversaries cannot retrieve the user\u27s original password from the leaked password database
Circuit-Succinct Universally-Composable NIZKs with Updatable CRS
Get PDFNon-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (zk-SNARKs) increasingly see real-world adoption in large and complex systems. Many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and for practical use it is desirable to reduce the trust in the CRS generation. The latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large systems is the ability to securely compose them to obtain more complex protocols, e.g., via the Universal Composability (UC) framework. Relying on the UC framework allows arbitrary and secure composition of protocols in a modular way.
In this work, we investigate whether zk-SNARKs can provide updatability and composability simultaneously. This is a challenging task as the UC framework rules out several natural techniques for such a construction. As our main result, we show that it is indeed possible to achieve these properties in a generic and modular way if we relax the succinctness properties of zk-SNARKs slightly to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness . We argue that for various practical applications of zk-SNARKs this overhead is acceptable. Our starting point is the Lamassu framework (ACM CCS\u2720), which we extend in several directions. Our new generic compiler adds only minimal overhead, which we demonstrate by benchmarking its application to the Sonic proof system (ACM CCS\u2719)
Sassafras: Efficient Batch Single Leader Election
Get PDFIn a single secret leader election (SSLE), a set of participants elect exactly one leader, who remains anonymous until they announce themselves by providing a proof. SSLE protocols are used in proof-of-stake blockchains to elect the leader who publishes the next block. Anonymity of the leader is an important security property, as the leader makes for an attractive target and may be subject to denial-of-service (DOS) attacks.
In this work, we propose a novel single leader election protocol, called Sassafras. We depart from the common approach of shuffling for constructing SSLE and instead employ a ring verifiable random function, which hides the identity of the leader within a ring of participants. Moreover, Sassafras is designed for batch leader elections, in which a single leader is selected for several elections at once. This allows the rate of leader election to match the rate of block production, an often-sought property not met by most SSLE protocols in the literature. We characterize single leader election with batching in the form of an ideal functionality in the Universal Composability (UC) framework and prove that Sassafras realizes this functionality. Sassafras is secure against an adaptive adversary, while achieving a slightly relaxed notion of anonymity for leaders. Sassafras features exceptionally low communication and computational complexity, outperforming other SSLE protocols by an order of magnitude or more
Depending on DEEPAND: Cryptanalysis of NLFSR-based Lightweight Ciphers TinyJAMBU, KATAN and KTANTAN
Get PDFAutomated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al., which showcased the power of Mixed Integer Linear Programming (MILP) in solving cryptanalysis problems that otherwise required significant effort. Since the inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as optimization problems to leverage the ease provided by state-of-the-art solvers. The other direction is to improve existing models to make them more efficient and/or accurate. The current work is an attempt to contribute to the latter. In this work, a general model referred to as DEEPAND has been devised to capture the correlation between AND gates in NLFSR-based lightweight block ciphers. DEEPAND builds upon and generalizes the idea of joint propagation of differences through AND gates captured using refined MILP modeling of TinyJAMBU by Saha et al. in FSE 2020. The proposed model has been applied to TinyJAMBU, KATAN, and KTANTAN and can detect correlations that were missed by earlier models. This leads to more accurate differential bounds for both the ciphers.
In particular, a 384-round (full round as per earlier specification) Type-IV trail is found for TinyJAMBU with 14 active AND gates using the new model, while the refined model reported this figure to be 19. This also reaffirms the decision of the designers to increase the number of rounds from 384 to 640. Moreover, the model succeeds in searching a full-round Type-IV trail of TinyJAMBU keyed permutation P_1024 with probability 2^-105 (much greater than 2^-128). This reveals the non-random properties of P_1024, thereby showing it to be non-ideal. Hence, it cannot be expected to provide the same security levels as robust block ciphers. Further, the provable security of the TinyJAMBU AEAD scheme should be carefully revisited.
Similarly, for the variants of KATAN, several previously reported trails are improved upon by employing the DEEPAND model. Moreover, in the related-key setting, the DEEPAND model is able to make a better 140-round boomerang distinguisher (for both the data and time complexity) in comparison to the previous boomerang attack by Isobe et al. in ACISP 2013. Furthermore, for enhanced applicability, we employ the DEEPAND model on another multiple-AND-based cipher, KTANTAN, in the related-key setting. Our analysis reveals practical differential distinguishers with low data and time complexities for all full-round KTANTAN variants. In summary, DEEPAND seems to capture the underlying correlation better when multiple AND gates are at play and can be adapted to other classes of ciphers as well
Computational Robust (Fuzzy) Extractors for CRS-dependent Sources with Minimal Min-entropy
Get PDFRobust (fuzzy) extractors are very useful for, e.g., authenticated exchange from shared weak secret and remote biometric authentication against active adversaries. They enable two parties to extract the same uniform randomness with the ``helper\u27\u27 string. More importantly, they have an authentication mechanism built in that tampering of the ``helper\u27\u27 string will be detected. Unfortunately, as shown by Dodis and Wichs, in the information-theoretic setting, a robust extractor for an -source requires , which is in sharp contrast with randomness extractors which only require . Existing work either relies on random oracles or introduces CRS and works only for CRS-independent sources (even in the computational setting).
In this work, we give a systematic study of robust (fuzzy) extractors for general CRS-dependent sources. We show in the information-theoretic setting, the same entropy lower bound holds even in the CRS model; we then show we can have robust extractors in the computational setting for general CRS-dependent source that is only with minimal entropy. At the heart of our construction lies a new primitive called -MAC that is unforgeable with a weak key and hides all partial information about the key (both against auxiliary input), by which we can compile any conventional randomness extractor into a robust one. We further augment -MAC to defend against ``key manipulation attacks, which yields a robust fuzzy extractor for CRS-dependent sources
Lattice Signature with Efficient Protocols, Application to Anonymous Credentials
Get PDFDigital signature is an essential primitive in cryptography, which can be used as the digital analogue of handwritten signatures but also as a building block for more complex systems. In the latter case, signatures with specific features are needed, so as to smoothly interact with the other components of the systems, such as zero-knowledge proofs. This has given rise to so-called signatures with efficient protocols, a versatile tool that has been used in countless applications. Designing such signatures is however quite difficult, in particular if one wishes to withstand quantum computing. We are indeed aware of only one post-quantum construction, proposed by Libert et al. at Asiacrypt\u2716, yielding very large signatures and proofs.
In this paper, we propose a new construction that can be instantiated in both standard lattices and structured ones, resulting in each case in dramatic performance improvements. In particular, the size of a proof of message-signature possession, which is one of the main metrics for such schemes, can be brought down to less than 650 KB. As our construction retains all the features expected from signatures with efficient protocols, it can be used as a drop-in replacement in all systems using them, which mechanically improves their own performance, and has thus a direct impact on many applications. It can also be used to easily design new privacy-preserving mechanisms. As an example, we provide the first lattice-based anonymous credentials system
Consensus Redux: Distributed Ledgers in the Face of Adversarial Supremacy
Get PDFPermissionless distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints on the resources available to an adversary relative to the resources of the participants that follow the protocol. Given their permissionless participation convention and their intended long-livedness, a critical open security question is their behavior---and potential resilience---to temporary spikes in adversarial resources.
In this work we give the first thorough treatment of the self-healing properties of Nakamoto ledgers, addressing both proof-of-work (PoW) and proof-of-stake (PoS) protocols. First, we present a unified model that allows us to define self-healing for both of these protocol classes. Then we provide a formal analysis establishing self-healing with respect to both consistency and liveness in both classes, quantifying the resulting vulnerability period as a function of the magnitude of the spike. Finally, we provide numerical simulations giving explicit quantitative bounds relevant for practice
Broadcast-Optimal Two-Round MPC
Get PDFAn intensive effort by the cryptographic community to minimize the round complexity of secure multi-party computation (MPC) has recently led to optimal two-round protocols from minimal assumptions. Most of the proposed solutions, however, make use of a broadcast channel in every round, and it is unclear if the broadcast channel can be replaced by standard point-to-point communication in a round-preserving manner, and if so, at what cost on the resulting security.
In this work, we provide a complete characterization of the trade-off between number of broadcast rounds and achievable security level for two-round MPC tolerating arbitrarily many active corruptions. Specifically, we consider all possible combinations of broadcast and point-to-point rounds against the three standard levels of security for maliciously secure MPC protocols, namely, security with identifiable, unanimous, and selective abort. For each of these notions and each combination of broadcast and point-to-point rounds, we provide either a tight feasibility or an infeasibility result of two-round MPC. Our feasibility results hold assuming two-round OT in the CRS model, whereas our impossibility results hold given any correlated randomness