ABSTRACT. Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modelled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ci- phers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offers a lower security level against TMTO attacks than expected from the key sizes. We provide detailed analyses of the key update mechanisms in TLS 1.3 and Signal, illustrate the importance of ephemeral key exchange, and show that the process that DTLS 1.3 and QUIC use to calculate AEAD limits is flawed. We provide many concrete recommendations for the analyzed protocols.

ABSTRACT. SAT, SMT, MILP, and CP, have become prominent in the differential cryptanalysis of cryptographic primitives. In this paper, we review the techniques for constructing differential characteristic search models in these four formalisms. Additionally, we perform a systematic comparison encompassing over 20 cryptographic primitives and 16 solvers, on both easy and hard instances of optimisation, enumeration and differential probability estimation problems.

ABSTRACT. In cube attacks, key filtering is a basic step of identifying the correct key candidates by referring to the truth tables of superpolies. When terms of superpolies get massive, the truth table lookup complexity of key filtering increases significantly. In this paper, we propose the concept of implementation dependency dividing all cube attacks into two categories: implementation dependent and implementation independent. The implementation dependent cube attacks can only be feasible when the assumption that one encryption oracle query is more complicated than one table lookup holds. On the contrary, implementation independent cube attacks remain feasible in the extreme case where encryption oracles are implemented in the full codebook manner making one encryption query equivalent to one table lookup. From this point of view, we scrutinize existing cube attack results of stream ciphers Trivium, Grain128AEAD, Acorn and Kreyvium. As a result, many of them turn out to be implementation dependent. Combining with the degree evaluation and divide-and-conquer techniques used for superpoly recovery, we further propose new cube attack results on Kreyvium reduced to 898, 899 and 900 rounds. Such new results not only mount to the maximal number of rounds so far but also are implementation independent.

ABSTRACT. Mixed Integer Linear Programming (MILP) is a well-known approach for the cryptanalysis of a symmetric cipher. A number of MILP-based security analyses have been reported for non-linear (SBoxes) and linear layers. Researchers proposed word- and bit-wise SBox modeling techniques using a set of inequalities which helps in searching differential trails for a cipher. In this paper, we propose two new techniques to reduce the number of inequalities to represent the valid differential transitions for SBoxes. Our first technique chooses the best greedy solution with a random tiebreaker and achieves improved results for the 4-bit SBoxes of MIBS, LBlock, and Serpent over the existing results of Sun et al. [26]. Subset addition, our second approach, is an improvement over the algorithm proposed by Boura and Coggia. Subset addition technique is faster than Boura and Coggia [10] and also improves the count of inequalities. Our algorithm emulates the existing results for the 4-bit SBoxes of Minalpher, LBlock, Serpent, Prince, and Rectangle. The subset addition method also works for 5-bit and 6-bit SBoxes. We improve the boundary of minimum number inequalities from the existing results for 5-bit SBoxes of ASCON and SC2000. Application of subset addition technique for 6-bit SBoxes of APN, FIDES, and SC2000 enhances the existing results. By applying multithreading, we reduced the execution time needed to find the minimum inequality set over the existing techniques.

ABSTRACT. Motivated by recent advances in exploring the power of hybridized TEE-blockchain systems, we present LucidiTEE, a unified framework for confidential, policy-compliant computing that guarantees fair output delivery. For context: - Kaptchuk et al. (NDSS’19) showed that enclave-ledger interactions can enable applications such as one-time programs and rate limited logging. We generalize their ideas to enforcing arbitrary history-based policies within and across several multi-step computations. Towards this, we define a new ideal functionality for policy-compliant computing FPCC, and then show how LucidiTEE implements FPCC. - Chaudhuri et al.(CCS’17) showed that enclave-ledger interactions enable fair exchange, contract signing, and more generally, fair secure multiparty computation. In a setting with n processors each of which possesses a TEE, they show how to realize fair secure computation tolerating up to t corrupt parties for any t < n. We improve upon their result by showing a novel protocol which requires only t out of the n processors to possess a TEE. When n = 2 and t = 1, this provides practical fair computation in client server settings, where clients may not possess a TEE. - Ekiden (EuroS&P’19) and FastKitten (Sec’19) use enclave-ledger interactions to enable practical, privacy-preserving smart contracts. However, Ekiden and FastKitten store the contract’s inputs on-chain (during malicious behavior in the latter’s case). In contrast, LucidiTEE implements privacy-preserving stateful computation while storing inputs, outputs, and state off-chain, using the ledger only to enforce history-based policies.

Summarizing, LucidiTEE enables multiple parties to jointly compute on private data, while enforcing history-based policies even when input providers are offline, and fairness to all output recipients, in a malicious setting. LucidiTEE uses the ledger only to enforce policies; i.e., it does not store inputs, outputs, or state on the ledger, letting it scale to big data computation. We show novel applications including a personal finance app, collaborative machine learning, and policy-based surveys amongst an apriori-unknown set of participants.

ABSTRACT. The proof of stake (PoS) mechanism, which allows stakeholders to issue a block with a probability proportional to their wealth instead of computational power, is believed to be an energy-efficient alternative to the proof of work (PoW). The privacy concern of PoS, however, is more subtle than that of PoW. Recent research has shown that current anonymous PoS (APoS) protocols do not suffice to protect the stakeholder's identity and stake, and the loss of privacy is theoretically inherent for any (deterministic) PoS protocol that provides liveness guarantees. In this paper, we consider the concrete stake privacy of PoS when considering the limitations of attacks in practice. To quantify the concrete stake privacy of PoS, we introduce the notion of $(T, \delta, \epsilon)$-privacy. Our analysis of $(T, \delta, \epsilon)$-privacy on Cardano shows to what extent the stake privacy can be broken in practice, which also implies possible parameters setting of rational $(T, \delta, \epsilon)$-privacy for PoS in the real world. The data analysis of Cardano demonstrates that the $(T, \delta, \epsilon)$-privacy of current APoS is not satisfactory, mainly due to the deterministic leader election predicate in current PoS constructions. Inspired by the differential privacy technique, we propose an efficient non-deterministic leader election predicate, which can be used as a plugin to APoS protocols to protect stakes against frequency analysis. Based on our leader election predicate, we construct anonymous PoS with noise (APoS-N), which can offer better $(T, \delta, \epsilon)$-privacy than state-of-the-art works. Furthermore, we propose a method of proving the basic security properties of PoS in the noise setting, which can minimize the impact of the noise on the security threshold. This method can also be applied to the setting of PoS with variable stakes, which is of independent interest.

ABSTRACT. Deterministic wallets are promising cryptographic primitives that are employed in cryptocurrencies to safeguard user’s fund. In CCS’19, a generic construction of deterministic wallets was proposed by Das et al. leveraging signature schemes with rerandomizable keys. This is an advanced form of signatures that enables separate but consistent rerandomization of secret and public keys. Das et al. instantiated their deterministic wallet construction from rerandomizable signatures based on BLS and ECDSA. However, these wallets are not quantum-resistant. In this work, we offer a strategy for post-quantum migration of secure deterministic wallets based on isogenies. Rerandomizable signatures being at the center of the wallet construction, we initially propose ways to design such signature schemes from isogenies. Employing the signature schemes CSI-FiSh and CSI-SharK, we present two quantum-resistant signature schemes with rerandomizable keys. We provide rigorous security proof showing our constructions are secure against existential unforgeability under chosen-message attacks with honestly rerandomized keys. Our rerandomized signature from CSI-SharK gives the most compact post-quantum secure rerandomized signature. Finally, we integrate our rerandomized signature scheme from CSI-FiSh to design the first isogeny-based deterministic wallet with compact key sizes. We present a detailed security analysis showing our wallet is secure against wallet unlinkability and wallet unforgeability.

ABSTRACT. Considering the increasingly large storage of post-quantum RingCT-like protocols, we construct a blockchain-based confidential transactions protocol with state accumulator (CTA), where each user only needs to store a concise state of the blockchain. More precisely, CTA can compress the historical data of all transactions into a short deterministic state, while preserving privacy and post-quantum security. The key component of our CTA is an efficient zero-knowledge lattice-based accumulator, which is based on Peikert et al.'s vector commitment scheme proposed in TCC 2021. We have modified their construction to ensure that the length of the underlying M-SIS parameters is kept short for the Merkle-tree structure. At a 128-bit security level, the membership proof size for our accumulator with $2^{20}$ members is only $225$ KB under the Module-SIS and Extended-MLWE assumptions.Compared with previous lattice-based works where the time and storage complexity of each user is linear with the number of coins, our CTA is capable of achieving logarithmic storage space and computational time. Specifically, the concrete transaction size of spending a coin in CTA is around $236$ KB, when the size of anonymity set is $2^{20}$.