Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
On The Dolev-Yao Model of Symmetric Cascade Protocol
Get PDFSecurity protocols enable authentication, key distribution, and secure information exchange, making them essential for network security, yet flaws in their design can lead to attacks. To prevent this, formal verification methods are vital for analyzing protocol correctness. The Dolev–Yao (DY) \cite{Dy} model introduced formalization for name-stamp and cascade protocols, where users apply public-key operations on messages. Brook and Otto \cite{DY-extension} later distinguished between symmetric and non-symmetric cascade protocols, noting that all DY cases were symmetric and that attacker choices were not fully addressed. They highlighted the incomplete characterization of an attacker’s power as an open problem. In this work, we extend the DY model by systematically analyzing all remaining symmetric two-party cascade protocol cases, aiming to provide a more complete foundation for building formal verification tools
Time Memory Trade-off For Enumeration
Get PDFWe incorporate a meet-in-the-middle strategy into the enumeration algorithm, enabling a tunable time-memory trade-off. The algorithm can achieve a minimum asymptotic time complexity of , which, in return, demands memory of the same order. This represents a square-root improvement over the state-of-the-art enumeration algorithms. More generally, our approach attains a time complexity of~ with memory usage , where is any constant satisfying .
Our approach decouples the head and tail blocks of the lattice basis. For a properly selected parameter, each enumeration space becomes asymptotically the square root of the original search space. Each tail vector is then extended to the head block space to find its closest vectors using an efficient neighboring search algorithm. Among all pairs of neighboring vectors that we iterate through, the shortest difference vector is then the solution to the Shortest Vector Problem (SVP).
Apart from the exact version of the algorithm which is of theoretical interest, we also propose heuristic strategies to improve the practical efficiency. First, we show the adaptation of our algorithm to pruned enumeration. Then we show that with a particularly chosen backbone lattice (rescaled~), we are able to accelerate the neighboring search process to an extremely efficient degree. Finally, we optimize parameters and give a practical cost estimation to show how much acceleration we could bring using this new algorithm
Learning With Physical Rounding for Linear and Quadratic Leakage Functions
Get PDFFresh re-keying is a countermeasure against side-channel analysis where an ephemeral key is derived from a long-term key using a public random value. Popular instances of such schemes rely on key-homomorphic primitives, so that the re-keying process is easy to mask and the rest of the (e.g., block cipher) computations can run with cheaper countermeasures. The main requirement for these schemes to be secure is that the leakages of the ephemeral keys do not allow recovering the long-term key. The Learning with Physical Rounding (LWPR) problem formalizes this security in a practically-relevant model where the adversary can observe noise-free leakages. It can be viewed as a physical version of the Learning With Rounding (LWR) problem, where the rounding is performed by a leakage function and therefore does not have to be computed explicitly. In this paper, we first consolidate the intuition that LWPR cannot be secure in a serial implementation context without additional countermeasures (like shuffling), due to attacks exploiting worst-case leakages that can be mounted with practical data complexity. We then extend the understanding of LWPR in a parallel implementation setting. On the one hand, we generalize its robustness against cryptanalysis taking advantage of any (i.e., not only worst-case) leakage. A previous work claimed security in the specific context of a Hamming weight leakage function. We clarify necessary conditions to maintain this guarantee, based on the degree of the leakage function and the accuracy of its coefficients. On the other hand, we show that parallelism inherently provides good security against attacks exploiting worst-case leakages. We finally confirm the practical relevance of these findings by validating our assumptions experimentally for an exemplary implementation
LifeXP+: Secure, Usable and Reliable Key Recovery for Web3 Applications
Get PDFIn the Web2 world, users control their accounts using credentials such as usernames and passwords, which can be reset or recovered by centralized servers if the user loses them.
In the decentralized Web3 world however, users control their accounts through cryptographic private-public key pairs which are much more complex to manage securely. In addition, the decentralized nature of Web3 makes account recovery impossible in the absence of predetermined recovery mechanisms. With the proliferation of blockchains and cryptocurrencies over the last years, it is crucial to provide users secure, usable and reliable ways to recover their accounts and assets. However, up to this day, no Web3 recovery method has adequately achieved all three of the above required properties. For instance, conventional ``mnemonic backups which can deterministically reconstruct a private key require verbatim recall of a fixed word list, creating an unpleasant usability/security trade-off.
In this work, we present a fully-offline protocol called LifeXP, that allows a user to reconstruct a cryptographically-secure private key from a natural-language story, which a user always remembers, such an memorable life event. To ensure usability of our protocol, key reconstruction can work even when the story is later retold with different wording or grammar, only requiring to preserve the semantics.
The protocol combines pre-trained sentence embeddings to capture semantics, locality-sensitive hashing to quantize embeddings into stable bit strings, a cryptographic fuzzy extractor that corrects bit errors caused by paraphrasing, and a biometric factor that is fused with the linguistic factor to boost entropy and enhance security. In our paper we describe the design, show that the protocol achieves the required properties, and provide an evaluation based on publicly-available datasets
which runs completely offline on commodity hardware, showcasing its feasibility
Disproving the Linearity of the Polynomials after the Pre-image Substitution in the System of the Third Attempt of MAYO
Get PDFIn this work, we analyze the mathematical aspect of the MAYO signature scheme. Following the specification of MAYO, we generate the keys where the secret key is a matrix and the public key is a system of quadratic polynomial of multiple variables; then use them to sign. During the signing procedure, we disprove the claim that the polynomial only has a constant part and a linear part after sampling values for the vinegar variables. Technically, we provide the mathematical expression of an arbitrarily polynomial of the system after substitution and discover that in addition of having a constant part and a linear part, the polynomial also has a quadratic part. The quadratic state of the polynomials after substitution allows us to conclude that signing fails with the third attempt of MAYO
Abuse Resistant Traceability with Minimal Trust for Encrypted Messaging Systems
Get PDFEncrypted messaging systems provide end-to-end security for users but obstruct content moderation, making it difficult to combat online abuses. Traceability offers a promising solution by enabling platforms to identify the originator/spreader of messages, yet this capability can be abused for mass surveillance of innocent messages. To mitigate this risk, existing approaches restrict traceability to (problematic) messages that are reported by multiple users or are on a predefined blocklist. However, these solutions either overtrust a specific entity (e.g., the party defining the blocklist) or rely on the unrealistic assumption of non-collusion between servers run by a single platform.
In this paper, we propose an abuse-resistant source tracing scheme that distributes traceability across distinct real-world entities. Specifically, we formally define its syntax and prove its security properties. Our scheme realizes two essential principles: minimal trust, which ensures that traceability cannot be abused as long as a single participant involved in tracing is honest, even if all others collude; and minimal information disclosure, which prevents participants from acquiring any information (e.g., communication parties\u27 identities) unnecessary for tracing. We implemented our scheme using techniques deployed by Signal, and our evaluation shows it offers comparable performance to state-of-the-art schemes that are vulnerable to abuse
Attacks and Remedies for Randomness in AI: Cryptanalysis of PHILOX and THREEFRY
Get PDFIn this work, we address the critical yet understudied question of the security of the most widely deployed pseudorandom number generators (PRNGs) in AI applications. We show that these generators are vulnerable to practical and low-cost attacks. With this in mind, we conduct an extensive survey of randomness usage in current applications to understand the efficiency requirements imposed in practice. Finally, we present a cryptographically secure and well-understood alternative, which has a negligible effect on the overall AI/ML workloads. More generally, we recommend the use of cryptographically strong PRNGs in all contexts where randomness is required, as past experience has repeatedly shown that security requirements may arise unexpectedly even in applications that appear uncritical at first
Optimal Threshold Traitor Tracing
Get PDFThreshold encryption distributes decryption capability across parties such that any of them can jointly decrypt a ciphertext, while smaller coalitions learn nothing. However, once or more parties collude, traditional threshold schemes provide no accountability: a coalition of or more parties can pool its keys into a pirate decoder that enables unrestricted decryption, all without any risk of being exposed. To address this, Boneh, Partap, and Rotem [CRYPTO \u2724] introduced threshold traitor tracing (TTT), which equips threshold encryption with traceability. Yet, all known TTT schemes either suffer from parameter sizes growing with at least , or rely on indistinguishability obfuscation to achieve optimal parameters.
In this paper, we present the first TTT schemes with optimal parameters, where public keys, secret keys, and ciphertexts are all bounded by , built solely from standard cryptographic tools and assumptions. Our first construction relies on the decisional Bilinear Diffie–Hellman (DBDH) assumption in prime order bilinear groups. Our second construction, based on the Learning with Errors (LWE) assumption, is plausibly post-quantum secure, and supports ramp-thresholds where decryption requires a larger coalition than those tolerated by security. Both of our constructions provide traceability against coalitions of arbitrary sizes.
To achieve these results, we introduce a new primitive, Attribute-Based Threshold Encryption (ABTE), which generalizes both threshold and attribute-based encryption. We then combine ABTE with Mixed Functional Encryption through a new compiler to obtain our TTT schemes. We believe ABTE is a powerful primitive that may have independent applications beyond optimal TTT
Weightwise (almost) perfectly balanced functions: -concatenation and the general Maiorana-McFarland class
Get PDFThe study of cryptographic criteria for Boolean functions with restricted domains has been an important topic over the last 20 years. A revived interest has sparked after the work of Carlet, Méaux and Rotella in 2017, where the authors studied cryptographic properties of restricted-domain functions and introduced the concept of weightwise perfectly balanced functions as part of the analysis of the FLIP stream cipher. Weightwise (almost) perfectly balanced functions are defined as Boolean functions that are (almost) balanced on each of the sets of vectors of the same Hamming weight. Several approaches have been considered to build new families of such functions. In this article, we present some new constructions of weightwise (almost) perfectly balanced functions via two approaches, the first class is constructed using the -concatenation of Boolean functions, whereas the second one draws certain functions from the so-called general Maiorana-McFarland class. A generic analysis of these two classes is given, as well as explicit examples in both classes. Namely, we provide instances of functions in both classes attaining high overall nonlinearities, as well as slice nonlinearities. Notably, we present examples in 16 variables that attain some of the best overall nonlinearities, and more importantly, the highest slice nonlinearities among all of the constructions presented in the literature
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Get PDFTraditional commit-and-reveal mechanisms have been used to realize sealed-bid on-chain auctions. However, these leak timing information, impose inefficient participation costs -- the inclusion fee to be paid for adding the transaction on-chain -- and also require multiple slots to execute the auction. Recent research investigates single-slot auctions; however, it requires a high threshold of honest parties.
We present a protocol that addresses these issues. Our design combines timestamp-based certificates with censorship resistance through inclusion lists. The resulting protocol satisfies four properties, the first being a strong hiding property which consists of Value Indistinguishability, Existential Obfuscation and User Obfuscation. This not only ensures that the adversary cannot differentiate between two value of bids (as the previously defined Hiding property does in Pranav et al. [MCP]), but also that the very existence of a bid and the identity of the bidder remain obfuscated. The second property is Short-Term Censorship Resistance, ensuring that, if the underlying blockchain outputs a block, then the auction would contain bids from all honest users. The third is a new property we introduce, Auction Participation Efficiency (APE), that measures how closely on-chain outcomes resemble classical auctions in terms of costs for participating users. And the fourth property is No Free Bid Withdrawal, which disallows committed bids from being withdrawn in case the bidder changes its mind.
Together, these properties yield a fair, private, and economically robust auction primitive that can be integrated into any blockchain to support secure and efficient auction execution