Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
The Large Block Cipher Family Vistrutah
Get PDFVistrutah is a block cipher with block sizes of 256 and 512 bits. It iterates a step function consisting of two AES rounds applied to each 128-bit block of the state, followed by a state-wide cell permutation.
Building upon established design principles from Simpira, Haraka, Pholkos, and ASURA, Vistrutah leverages AES instructions to achieve high performance.
For each component of Vistrutah, we conduct a systematic evaluation of functions that can be efficiently implemented on both Intel and Arm architectures. We therefore expect them to perform efficiently on any recent vector instruction set architecture (ISA) with AES support.
Our evaluation methodology combines, for each combination of the various choices of the cipher\u27s components, a security analysis with a latency estimation on an abstracted ISA. The goal is to maximize the ratio of ``bits of security per unit of time,\u27\u27 i.e., to achieve the highest security for a given performance target, or equivalently, the best performance for a given security level within this class of designs.
Implementations confirm the accuracy of our latency model. Vistrutah even performs significantly better than Rijndael-256-256.
Our security claims are backed by a comprehensive ad-hoc cryptanalysis. An isomorphism between Vistrutah-512, the 512-bit wide variant, and the AES, allows us to also leverage the extensive cryptanalysis of AES and apply it to Vistrutah-512.
A core design principle is the use of an inline key schedule, computed during each encryption or decryption operation without requiring storage in any external memory. In fact, rekeying Vistrutah has no associated overheads. Key schedules like the AES\u27s must precompute and store round keys in memory for acceptable performance. However, in 2010 Kamal and Youssef showed that this makes cold boot attacks significantly more effective. Vistrutah\u27s approach minimizes leakage to at most two byte-permutations of the original key during context switches. Furthermore, expensive key schedules reduce key agility, limiting the design of modes of operation.
Vistrutah is particularly well-suited for Birthday-Bound modes of operation, including Synthetic IV modes and Accordion modes for 256-bit block ciphers. It can serve as a building block for compression functions (such as Matyas-Meyer-Oseas) in wide Merkle–Damgaard hash functions. Additionally, it can implement ``ZIP\u27\u27 wide pseudo-random functions as recently proposed by Florez-Gutierrez et al. in 2024.
Finally, we present short, i.e., reduced-round versions of Vistrutah which are analyzed taking into account the restrictions posed on attackers by specific modes of operation. In particular, we model the use of the block ciphers in HEH constructions such as HCTRtwo as well as in ForkCiphers.
These short versions of Vistrutah can be used to accelerate modes of operation without sacrificing security
Tight Multi-User Security of CCM and Enhancement by Tag-Based Key Derivation Applied to GCM and CCM
Get PDF and are block cipher (BC) based authenticated encryption modes. In multi-user (mu) security, a total number of BC invocations by all users and the maximum number of BC invocations per user are crucial factors. For , the tight mu-security bound has been identified as , where and are respectively the key and block sizes, is the number of users, is the number of offline queries.In contrast, the \u27s mu-security bound is still unclear. Two bounds of and have been derived by Luykx~et~al.~(Asiacrypt~2017) and Zhang~et~al.~(CCS~2024), respectively, but both are not tight and worse than the \u27s bound. Moreover, methods to enhance mu security without disruptive changes in the scheme have been considered for , namely nonce randomization () to improve offline security and nonce-based key derivation () to improve online security, but their applicability to has never been discussed. In this paper, we prove an improved mu-security bound of , which is tight, and reaches the \u27s bound. We then prove that and applied to result in the same bounds for the case to . An important takeaway is that is now proved to be as secure as . Moreover, we argue that and can be insufficient for some applications with massive data, and propose a new enhancement method called nonce-based and tag-based key derivation () that is applied to and . We prove that the resulting schemes meet such real-world needs
On the security of one certificateless aggregate signature scheme with dynamic revocation in vehicular ad-hoc networks
Get PDFWe show that the certificateless signature scheme [Veh. Commun. 47: 100763 (2024)] is insecure, because an adversary can launch forgery attack for any message. The signer\u27s certificateless public key is not tightly bound to the system public key. The inherent flaw results in that the adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm. The findings in this note could be helpful for newcomers who are not familiar with the designing techniques for certificateless signatures
SPECK: Signatures from Permutation Equivalence of Codes and Kernels
Get PDFThe ongoing search for secure post-quantum cryptographic primitives has led to the development of numerous novel digital signature schemes. In this paper we introduce , a new signature protocol based on the similarities between the Permuted Kernel Problem () and the Permutation Code Equivalence Problem (). At its core, is built on the permutation version of LESS, but introduces a key modification to the commitment step. Indeed, instead of committing to an entire permuted code, the prover commits to a random relaxed (that we call , Permutation Equivalence of Codes and Kernel) instance by randomly choosing a codeword from a random permutation of the initial code. In this sense, the secret key is used as a trapdoor to solve the committed instance. The new approach allows for a faster verification that does not involve gaussian elimination, while maintains roughly the same signature size as LESS. We present the protocol in detail and provide a deep analysis of the security of the new introduced assumptions
New Framework for Structure-Aware PSI From Distributed Function Secret Sharing
Get PDFPrivate set intersection (PSI) allows two parties to jointly compute the intersection of their private sets without revealing any additional information. Structure-aware PSI (sa-PSI), introduced by Garimella et al. (Crypto\u2722), is a variant where Alice\u27s input set has a publicly known structure and Bob\u27s input set remains unstructured, enabling new applications like fuzzy PSI. Their construction relies solely on lightweight cryptographic primitives such as symmetric-key primitives and oblivious transfer (OT) extension. Since then, there has been active research on sa-PSI based on lightweight cryptography. Notably, recent work by Garimella et al. (Crypto\u2724) achieves sa-PSI with both communication and computation costs only scaling with the description size of Alice\u27s set, rather than its potentially large cardinality. However, this line of work remains largely theoretical, lacking efficient concrete implementations.
In this work, we close this gap by presenting a new framework for sa-PSI that achieves practical efficiency. We identify and eliminate a hidden multiplicative overhead proportional to the security parameter (e.g., 128) in prior symmetric-key-based sa-PSI constructions. A key building block of our new framework is a distributed Function Secret Sharing (dFSS) key generation protocol tailored to the structure of Alice\u27s set, which may be of independent interest. To demonstrate the practicality of our framework, we extend our dFSS protocol to support incremental evaluation, introduce new techniques for spatial hashing, and develop several new optimization techniques, including reducing the exponential dependence on dimension and enabling load balancing between the two parties.
We instantiate our framework for structured sets defined by unions of -dimensional balls, and implement our protocols using only lightweight symmetric-key primitives and OT extension. Our experiments show concrete performance improvements of up to speedup in computation and reduction in communication in low-dimensional, large-radius settings compared to existing public-key-based fuzzy PSI protocols by van Baarsen & Pu (Eurocrypt\u2724) and Gao et al. (Asiacrypt\u2724)
On the Fiat–Shamir Security of Succinct Arguments from Functional Commitments
Get PDFWe study the security of a popular paradigm for constructing SNARGs, closing a key security gap left open by prior work. The paradigm consists of two steps: first, construct a public-coin succinct interactive argument by combining a functional interactive oracle proof (FIOP) and a functional commitment scheme (FC scheme); second, apply the Fiat–Shamir transformation in the random oracle model. Prior work did not consider this generalized setting nor prove the security of this second step (even in special cases).
We prove that the succinct argument obtained in the first step satisfies state-restoration security, thereby ensuring that the second step does in fact yield a succinct non-interactive argument. This is provided the FIOP satisfies state-restoration security and the FC scheme satisfies a natural state-restoration variant of function binding (a generalization of position binding for vector commitment schemes).
Moreover, we prove that notable FC schemes satisfy state-restoration function binding, allowing us to establish, via our main result, the security of several SNARGs of interest (in the random oracle model). This includes a modular security proof of Plonk, in the ROM based on falsifiable Diffie–Hellman assumptions
Exclusive Ownership of Fiat-Shamir Signatures: ML-DSA, SQIsign, LESS, and More
Get PDFExclusive ownership (EO) security is a feature of signature schemes that prevents adversaries from stealing an honestly generated signature by finding a new public key which verifies said signature. It is one of the beyond unforgeability features (BUFF) which were declared to be desirable features by NIST. The BUFF transform allows to generically achieve exclusive ownership (and other properties) at the cost of an increased signature size. In this work, we study the EO security of (different variants of) Fiat-Shamir signatures. As our main result, we show that the commonly used variant of Fiat-Shamir signatures (where signatures consist of challenge-response tuples) with λ-bit challenges, can achieve about λ-bit EO security through its implicit usage of the BUFF transform—this presents a significant improvement to existing results that only provide λ/2-bit of EO security. This benefit of our result comes without an increase in signature size. For other variants of Fiat-Shamir signatures, we show worse bounds, which nevertheless improve upon existing results. Finally, we apply our results to several signature schemes: SQIsign and LESS (both round-2 NIST candidates); ML-DSA (NIST standard); CSI-FiSh; and Schnorr signatures. This shows that all these schemes achieve significantly better bounds regarding their EO security compared to existing results
Papercraft: Lattice-based Verifiable Delay Function Implemented
Get PDFA verifiable delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today\u27s hardware. As an example, our Papercraft implementation can verify a computation of almost 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment
Public-key Cryptography Attacks Using Adiabatic Quantum Computer
Get PDFWe explore the application of the QUBO and Ising models to the integer factorization problem with implications for the security of public-key algorithms such as RSA. A key contribution is a program that applies existing algorithms to parameterize and simulate integer factorization through an Ising model in order to replicate previous works. Due to limited access to quantum hardware, we use classical heuristic methods to approximate solutions
MOCHA: Mixnet Optimization Considering Honest Client Anonymity
Get PDFMix networks (mixnets) safeguard client anonymity by forwarding traffic through multiple intermediary nodes (mixnodes), which reorder and delay messages to obscure communication patterns against a global passive adversary capable of monitoring all network transmissions.
The anonymity provided by mixnets is usually assessed with a discrete-event simulator, gauging a target message\u27s indistinguishability among output messages. While useful for comparative analysis, this approach only approximates the mixnet\u27s anonymity potential. Hence, this paper sheds light on the necessity of considering the client (originator of messages) itself to gauge anonymity accurately. We further provide an algorithm (simulator) to simulate client anonymity for Loopix mixnets. We conduct experiments to optimize general Loopix mixnet parameters, considering both message and client anonymity. Our findings indicate that message anonymity often provides an upper bound and can yield misleading results for mixnet optimization, underscoring the importance of client anonymity. Additionally, we explore scenarios where client anonymity is significantly compromised due to an insufficient number of clients. To address these cases, we propose a multimixing strategy that enhances client anonymity by effectively merging varied traffic types with different mixing characteristics