IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key, Revisited: Consistency, Outsider Strong Unforgeability, and Generic Construction
Full text linkLiu et al. (EuroS& P 2019) introduced Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS) to enhance the security of stealth address and deterministic wallet. In this paper, we point out that the current security notions are insufficient in practice, and introduce a new security notion which we call consistency. Moreover, we explore the unforgeability to provide strong unforgeability for outsider which captures the situation that nobody, except the payer and the payee, can produce a valid signature. From the viewpoint of cryptocurrency functionality, it allows us to implement a refund functionality. Currently, basically there is no way to refund a coin when one mistakenly spends a coin to an address. This functionality rescues the case, even in the stealth environment that hides information of the payer. Note that the refund functionality only works before the payee transfers a coin to own wallet, and it prevents a double spending issue. Finally, we propose a generic construction of PDPKS that provides consistency and outsider strong unforgeability. The design is conceptually much simpler than known PDPKS constructions. It is particularly note that the underlying strongly unforgeable signature scheme is required to provide the strong conservative exclusive ownership (S-CEO) security (Cremers et al., IEEE S& P 2021). Since we explicitly require the underlying signature scheme to be S-CEO secure, our security proof introduces a new insight of exclusive ownership security which may be of independent interest. </p
Matrix Polynomial Attack on the Megrelishvili Key Exchange Protocol
Full text linkIn this article we explain what the Megrelishvili Key Exchange Protocol (MKE) is and compare it briefly to the older Diffie-Hellman Key Exchange Protocol. We clarify how the security of the MKE relates to the hardness of the Megrelishvili Vector-Matrix Problem (MVMP) and also to a generalization of this problem, introduced by us, which we call the Matrix Polynomial Problem (MPP). There were previous sub-exponential time attacks on the MKE [AW16, AMP18], the first applying to arbitrary instances and the latter requiring the public matrix to be diagonalizable — as well as an attack on the one-way function used in the MKE [Meg14] that required special conditions, but when applicable would allow to break the protocol in polynomial time according to our running-time analysis. Here we adopt a bottom-up approach to construct for the first time, as far as our review of the relevant literature reveals, a polynomial time algorithm that solves any instance of the MKE through its reduction to a MPP. We also introduce some key concepts from linear algebra and Krylov subspace theory into the context of the MKE, allowing for a clearer understanding of our attack. </p
Algebraic Side-Channel Attacks against ISAP\u27s Re-Keying: one Ascon Round May not be Enough for Serial Implementations
Full text linkWe investigate the side-channel security of ISAP against Algebraic Side-Channel Attacks (ASCA) in a simulated setting where the Hamming weight leakages of its intermediate computations can be recovered. For this purpose, we first describe how these attacks, so far only used to target 8-bit implementations, can be applied to 16-bit or 32-bit implementations. We then use ASCA to discuss the side-channel security claims of ISAP\u27s re-keying, where a single bit of nonce is absorbed per permutation call. Theoretically, this re-keying aims to ensure that attacking more than one permutation call jointly does not improve over attacking the same number of permutation calls independently. Yet, while this expectation is expected to be met for ISAP\u27s conservative parameters (where permutation calls are made of 12 Ascon rounds), the extent to which it does (not) hold for ISAP\u27s aggressive parameters (where permutation calls are made of a single Ascon round) remains an open question. We contribute to this question by showing that for 16-bit implementations, combining the leakages of multiple permutation calls can improve over attacking the same number of permutation calls independently, which contradicts ISAP\u27s (theoretical) leakage-resistance claims. By contrast, for 32-bit leakages, we only show similar weaknesses by guessing a large part of the target state (i.e., more than 128 bits), which only impacts the initialization of ISAP\u27s re-keying and does not contradict its security reduction. These results confirm that for hardware implementations with a sufficient level of parallelism, ISAP\u27s aggressive parameters are probably sufficient, but that for more serial (e.g., software) implementations, slightly more conservative parameters, or the addition of implementation-level countermeasures, are needed. </p
Fully Collusion Resistant Traceable Identity-Based Inner Product Functional Encryption
Full text link We present the first fully collusion resistant traceable functional encryption (TFE) scheme for identity-based inner product FE (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity TIBIPFE (EI-TIBIPFE) where secret keys and ciphertexts are computed for vectors, and decryption recovers the inner product between the vectors given the key and ciphertext are associated with the same group identity. Additionally, a secret key corresponds to a user identity for the purpose of tracing. Suppose some of the users linked to a particular group team up and create a pirate decoder that is capable of decrypting the content of the group, then the tracing algorithm extracts the identities of the dishonest users\u27 given black-box access to the decoder. Previously, such schemes were designed for usual public key encryptions. In this work, we construct a fully collusion resistant EI-TIBIPFE scheme from pairings in the standard model. The ciphertext size of our scheme grows sub-linearly with the number of users in the system. We achieve many-target security of tracing, namely the adversary is allowed to ask for multiple secret keys corresponding to many functions, which notably solves an open problem raised by Do, Phan, and Pointcheval [CT-RSA\u272020]. </p
A divide-and-conquer sumcheck protocol
Full text link We present a new sumcheck protocol called Fold-DCS (Fold-Divide-and-Conquer-Sumcheck) for multivariate polynomials based on a divide-and-conquer strategy. Its round complexity and soundness error are logarithmic in the number of variables, whereas they are linear in the classical sumcheck protocol. This drastic improvement in number of rounds and soundness comes at the expense of exchanging multivariate polynomials, which can be alleviated using polynomial commitment schemes. We first present Fold-DCS in the PIOP model, where the prover provides oracle access to a multivariate polynomial at each round. We then replace this oracle access in practice with a multivariate polynomial commitment scheme; we illustrate this with an adapted version of the recent commitment scheme Zeromorph, which allows us to replace most of the queries made by the verifier with a single batched evaluation check. </p
Simplified Meet-in-the-middle Preimage Attacks on AES-based Hashing
Full text linkoai:cic.iacr.org:2/4/9The meet-in-the-middle (MITM) attack is a powerful cryptanalytic technique leveraging time-memory tradeoffs to break cryptographic primitives. Initially introduced for block cipher cryptanalysis, it has since been extended to hash functions, particularly preimage attacks on AES-based compression functions. Over the years, various enhancements such as superposition MITM (Bao et al., CRYPTO 2022) and bidirectional propagations have significantly improved MITM attacks, but at the cost of increasing complexity of automated search models. In this work, we propose a unified mixed integer linear programming (MILP) model designed to improve the search for optimal pre-image MITM attacks against AES-based compression functions. Our model generalizes previous approaches by simplifying both the modeling and the corresponding attack algorithm. In particular, it ensures that all identified attacks are valid. The results demonstrate that our framework not only recovers known attacks on AES and Whirlpool but also discovers new attacks with lower memory complexities, and new quantum attacks. </p
I Know What Your Layers Did: Layer-wise Explainability of Deep Learning Side-channel Analysis
Full text link Deep neural networks have proven effective for second-order profiling side-channel attacks, even in a black-box setting with no prior knowledge of masks and implementation details. While such attacks have been successful, no explanations were provided for understanding why a variety of deep neural networks can (or cannot) learn high-order leakages and what the limitations are. In other words, we lack the explainability on neural network layers combining (or not) unknown and random secret shares, which is a necessary step to defeat, e.g., Boolean masking countermeasures.In this paper, we use information-theoretic metrics to explain the internal activities of deep neural network layers. We propose a novel methodology for the explainability of deep learning-based profiling side-channel analysis (denoted ExDL-SCA) to understand the processing of secret masks. Inspired by the Information Bottleneck theory, our explainability methodology uses perceived information to explain and detect the different phenomena that occur in deep neural networks, such as fitting, compression, and generalization. We provide experimental results on masked AES datasets showing what relevant features deep neural networks use, and where in the networks relevant features are learned and irrelevant features are compressed. Using our method, evaluators can determine what secret masks are being exploited by the network, which allows for more detailed feedback on the implementations. This paper opens new perspectives for understanding the role of different neural network layers in profiling side-channel attacks</p
Running Standard Block Ciphers Beyond AES with TFHE: Experiments and Lessons Learnt
Full text link The dream of achieving data privacy during external computations has become increasingly concrete in recent years. Indeed, since the early days of Fully Homomorphic Encryption (FHE) more than a decade ago, new cryptosystems and techniques have constantly optimized the efficiency of computation on encrypted data. However, one of the main disadvantages of FHE, namely its significant ciphertext expansion factor, remains at the center of the efficiency bottleneck of FHE schemes.To tackle the issue of slow uplink FHE data transmission, we use transciphering. With transciphering, the client naturally encrypts its data under a symmetric scheme and sends them to the server with (once and for all) an FHE encryption of the symmetric scheme\u27s key. With its larger computing power, the server then evaluates the symmetric scheme\u27s decryption algorithm within the homomorphic domain to obtain homomorphic ciphertexts that allow it to perform the requested calculations. Since the first use of this method a bit more than ten years ago, papers on the homomorphic evaluation of AES have been numerous. And as the AES execution is the application chosen by NIST in the FHE part of its recent call for proposals on threshold encryption, the stakes of such work go up another level. But what about other standardized block ciphers? Is the AES the more efficient option? In this work, we leverage on two methods which have successfully been applied to the homomorphic evaluation of AES to study several state-of-the-art symmetric block ciphers (namely CLEFIA, PRESENT, PRINCE, SIMON, SKINNY). That is to say, we implement a representative set of symmetric block ciphers using TFHE. These implementations allow us to compare the efficiency of this set of symmetric schemes and to categorize them. We highlight the characteristics of block ciphers that are fast to execute in the homomorphic domain and those that are particularly costly. Finally, this classification of operation types enables us to sketch out what the ideal block cipher for transciphering homomorphic data in integer mode might look like. </p
E-cclesia: Universally Composable Self-Tallying Elections over Anonymous Broadcast
Full text linkThe technological advancements of the digital era have paved the way for the facilitation of electronic voting (e-voting) with promises of increased efficiency and enhanced security. In standard e-voting designs, the tally process is assigned to a committee of designated entities called talliers. Naturally, the security analysis of any e-voting system with designated talliers hinges on the assumption that a subset of the talliers follows the execution guidelines and does not attempt to breach privacy. As an alternative approach, Kiayias and Yung [PKC \u2702] pioneered the self-tallying elections (STE) paradigm, where the post-ballot-casting (tally) phase can be performed by any interested party, removing the need for designated talliers.In this work, we explore the prospect of decentralized e-voting where security is preserved under concurrent protocol executions. In particular, we provide the first comprehensive formalization of STE in the universal composability (UC) framework introduced by Canetti [FOCS \u2701] via an ideal functionality that captures required security properties such as voter privacy, eligibility, fairness, one-voter one-vote, and verifiability. We present a concrete instantiation, called E-cclesia, that UC-realizes our functionality. The design of E-cclesia integrates several cryptographic primitives such as signatures of knowledge for anonymous eligibility checks, dynamic accumulators for scalability, time-lock encryption for fairness, and anonymous broadcast channels for voter privacy. For the latter primitive, we provide the first UC formalization along with a novel construction based on mix-nets that utilizes layered encryption, threshold secret sharing, and equivocation techniques. Additionally, we provide the first UC formalization of dynamic accumulators without a trusted setup, along with a UC realization based on existing constructions.Finally, we discuss the deployment and scalability of E-cclesia. We present preliminary benchmarks of the key operations of the voting client and demonstrate the feasibility of our proposal with readily available cryptographic tools for mid-sized elections. </p
A Note on the Walsh Spectrum of Power Residue S-Boxes
Full text link Let F_q be a prime field with q >= 3, and let d, m >= 1 be integers such that gcd (d, q) = 1 and m | (q - 1). In this paper we bound the absolute values of the Walsh spectrum of S-Boxes of the form S (x) = x^d * T (x^((q - 1) / m)), where T is a function with T (x) != 0 if x != 0. Such S-Boxes have been proposed for the Zero-Knowledge-friendly hash functions Grendel and Polocolo. In particular, we prove the conjectured correlation of the Polocolo S-Box. </p