IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Improved Related-Key Differential Attacks against AES-256
Full text linkIn this paper, we revisit the differential meet-in-the-middle attack and classical differential attack on AES-256 under the related-key setting, as introduced in Boura et al.\u27s ToSC 2023 and Song et al.\u27s Asiacrypt 2024 works. We propose new attacks against 13-round AES-256, all with significantly lower complexities. This is achieved through an efficient method for identifying weak keys, which enables a better utilization of differential propagation. Furthermore, we present multiple attack scenarios and their complexities by considering various weak keys derived from the key generation process. Our attacks have data complexity between and and time complexity between and depending on the proportion of weak keys that varies from to , marking a substantial advance over previous approaches. </p
Better GBFV Bootstrapping and Faster Encrypted Edit Distance Computation
Full text linkWe propose a new iterative method to convert a ciphertext from the Generalized BFV (GBFV) to the regular BFV scheme. In particular, our conversion starts from an encrypted plaintext that lives in a large cyclotomic ring modulo a small-norm polynomial t(x), and gradually changes the encoding to a smaller cyclotomic ring modulo a much larger integer p. Previously, only a trivial conversion method was known, which did not change the underlying cyclotomic ring.Using our improved conversion algorithm, we can bootstrap the GBFV scheme almost natively, in the sense that only a very small fraction of the operations is computed inside regular BFV. Specifically, we evaluate (an adapted version of) the slot-to-coefficient transformation entirely in the GBFV scheme, whereas the previous best method used the BFV scheme for that transformation. This insight allows us to bootstrap either with less noise growth, or much faster than the state-of-the-art.We implement our new bootstrapping in Microsoft SEAL. Our experiments show that, for the same remaining noise budget, our bootstrapping runs in only 800 ms when working with ciphertexts containing 1024 slots over F_p with p = 2^16 + 1. This is 1.6 times faster than the state-of-the-art.Finally, we use our improved GBFV bootstrapping in an application that computes an encrypted edit distance. Compared to the recent TFHE-based Leuvenshtein algorithm, our GBFV version is almost two orders of magnitude faster in the amortized sense. </p
BAKSHEESH: Similar Yet Different From GIFT (and ZORRO)
Full text linkWe propose a lightweight block cipher named BAKSHEESH, which draws inspiration from GIFT (CHES\u2717). BAKSHEESH runs for 35 rounds, which is 12.5 per cent fewer rounds compared to GIFT-128 whilst maintaining the same security claims against classical attacks. However, we also present an alternate (but equivalent) angle of BAKSHEESH that follows the heritage of ZORRO (CHES\u2713).In the GIFT heritage version, BAKSHEESH uses a 4-bit SBox that has a non-trivial Linear Structure (LS). In the alternate ZORRO heritage specification, it employs a 3-bit SBox and realises a partial non-linear layer.BAKSHEESH is suitable for efficient hardware and software implementations, and also offers an edge on side channel countermeasures and other niche applications. For instance, our study on the threshold implementation shows that BAKSHEESH offers a few-fold advantage over other lightweight ciphers.We therefore create a new paradigm of lightweight ciphers through adequate deliberation on the design choice and solidify it with appropriate security analysis and ample implementation/benchmark. </p
Quantum Black-Box Separations: Succinct Non-Interactive Arguments from Falsifiable Assumptions
Full text linkIn their seminal work, Gentry and Wichs (STOC\u2711) established an impossibility result for the task of constructing an adaptively-sound SNARG via black-box reduction from a falsifiable assumption. An exciting set of recent SNARG constructions demonstrated that, if one adopts a weaker but still quite meaningful notion of adaptive soundness, then impossibility no longer holds (Waters-Wu, Waters-Zhandry, Mathialagan-Peters-Vaikunthanathan ePrint\u2724). These fascinating new results raise an intriguing possibility: is there a way to remove this slight weakening of adaptive soundness, thereby completely circumventing the Gentry-Wichs impossibility? A natural route to closing this gap would be to use a quantum black-box reduction, i.e., a reduction that can query the SNARG adversary on superpositions of inputs. This would take advantage of the fact that Gentry-Wichs only consider classical reductions. In this work, we show that this approach cannot succeed. Specifically, we extend the Gentry-Wichs impossibility result to quantum black-box reductions, and thereby establish an important limit on the power of such reductions. </p
Indistinguishability Obfuscation from Ring Key-Homomorphic Weak PRFs
Full text link A weak pseudorandom function is said to be ring key-homomorphic if, given and , there are efficient algorithms to compute and where and are the addition and multiplication operations in the ring , respectively. A recent work by Alamati et al. (CT-RSA\u27 23) initiated the study of ring key-homomorphic weak PRFs (RKHwPRFs) and showed that any RKHwPRF can be used to construct multiparty noninteractive key exchange (NIKE) for an arbitrary number of parties. In this work, we show that any RKHwPRF can, in fact, be used to construct indistinguishability obfuscation (iO) for all circuits in , which in turn can be bootstrapped to all polynomial-size circuits using standard techniques. The proof of security for our iO construction is in the standard model, and our assumptions (including weakenings of RKHwPRFs) are program-independent. We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, notably the first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC\u2718) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it. Our result in a sense completes the work initiated by Alamati et al. (Eurocrypt\u27 19, JoC \u2723) on building cryptosystems from generic Minicrypt primitives with structure. Given our construction of iO from RKHwPRFs, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography. </p
Multi User Security of LightMAC and LightMAC_Plus
Full text link LightMAC is one of the ISO/IEC standardized message authentication codes that provably achieves security roughly in the order of O(q^2/2^n), where q is the total number of queries and n is the block size of the underlying block cipher. In a subsequent work, Naito proposed a beyond-birthday-bound variant of the LightMAC construction, dubbed LightMAC_Plus, and demonstrated that it achieves 2n/3-bit PRF security. Later in EUROCRYPT\u2720, Kim et al. improved the security bound of LighMAC_Plus from 2n/3 bits to 3n/4 bits. However, all these security results have been proven in the single-user setting, where we assume that the adversary has access to a single instance of the construction. In this paper, we investigate, for the first time, the security of the LightMAC and the LightMAC_Plus constructions in the context of the multi-user setting, where we assume that the adversary has access to more than one instance of the construction. In particular, we have shown that LightMAC offers O(qq_maxl k/2^n + up/2^k) multi-user PRF security, where q denotes the total number of construction queries, p denotes the total number of offline primitive queries, q_max denotes the maximum number of queries per user, u denotes the total number of users and l denotes the maximum number of message blocks in a query. We have also shown that LightMAC_Plus maintains security up to approximately 2^2n/3 construction queries and 2^2k/3 ideal-cipher queries in the ideal-cipher model, where n denotes the block size and k denotes the key size of the block cipher. </p
Committing Security Analysis of SMAC
Full text link SMAC is a newly proposed MAC family built based on the finite state machine (FSM) of the SNOW-V series, targeting the high speed requirements in 5G and beyond. In this paper, we study the committing security of the SMAC family. We first theoretically reduce the committing security of SMAC to the properties of the underlying components, including the Davies-Meyer construction and the compress function. We then propose practical key-committing attacks against SMAC-1, SMAC-3/4, and SMAC-, as well as a theoretical attack against SMAC-1/2 with complexity far below the birthday bound. To enhance the committing security of SMAC, we further suggest two variants of SMAC that can resist our attacks. Our results shed some light on how to design highly efficient MACs with robust committing security. </p
Access-Controlled Inner Product Function-Revealing Encryption
Full text linkWe extend the concept of access control for functional encryption, introduced by Abdalla et al. (ASIACRYPT 2020), to function-revealing encryption (Joy and Passelègue, SCN 2018). Here access control means that function evaluation is only possible when a specified access policy is met. Specifically, we introduce access-controlled inner-product function-revealing encryption (AC-IPFRE) and give two applications.On the theoretical side, we use AC-IPFRE to show that function-hiding inner-product functional encryption (FH-IPFE), introduced by Bishop et al. (ASIACRYPT 2015), is equivalent to IPFRE. To show this, we in particular generically construct AC-IPFRE from IPFRE for the non-zero inner-product (NZIP) access policy. This result uses an effective version of Lagrange’s Four Square Theorem. One consequence of this result is that lower bounds by Ünal (EUROCRYPT 2020) suggest that, as for FH-IPFE, bilinear pairings will be needed to build IPFRE.On the practical side, we build an outsourced approximate nearest-neighbor (ANN) search protocol and mitigate its leakage via AC-IPFRE. For this, we construct a practical AC-IPFRE scheme in the generic bilinear group model for a specific access policy for ANN search. To this end, we show that techniques of Wee (TCC 2020) implicitly give the most practical FH-IPFE scheme to date. We implement the resulting outsourced ANN search protocol and report on its performance.Of independent interest, we show AC-IPFRE for NZIP implies attribute-hiding small-universe AC-IPFRE for arbitrary access policies. Previous work on access control for FE did not achieve attribute hiding. Our results demonstrate that AC-IPFRE is of both theoretical and practical interest and set the stage for future work in the area. </p
Strong Multiple-CCA Security in the Quantum Random Oracle Model for an FO-like PKE Combiner
Full text linkCombiners for cryptographic schemes are a common way to increase security using redundancy. The security notions for public key encryption (PKE) combiners can be extended beyond the standard IND-CCA security to achieve even stronger security notions. In the indistinguishability under adaptive strong multiple chosen-ciphertext attack (IND-sMCCA) security notion, the adversary has additional oracle access to the underlying cipher components of the combiner. Recently, combiners have received more attention because of the possibility of combining classical and post-quantum (PQ) cryptography. This allows for the use of novel PQ algorithms while still having the security guarantees of the classical algorithms. In order to examine the security against quantum adversaries, the quantum random oracle model (QROM) has become the most relevant security model. However, there are no PKE combiners that achieve IND-sMCCA security in the QROM, even though this security notion describes much better the current state where classical, PQ, and combined schemes are deployed at the same time.In this paper, we close this gap by providing a new PKE combiner that is IND-sMCCA secure in the QROM. Our construction is more efficient and lean than the existing PKE combiners, considering the primitives used and the ciphertext size. We accomplish this by applying the Fujisaki-Okamoto (FO) transformation to a PKE combiner of Asmuth and Blakley. To achieve IND-sMCCA security for the combiner, the PKE components must be OW-CCA secure. However, when using weaker (OW-CPA secure) PKE components, we still achieve standard IND-CCA security for the combiner. The security reductions are given in the ROM and the QROM, achieving bounds of different tightness. </p
On the Possibility of Malicious Obfuscation
Full text linkWe study a new variant of malicious obfuscation, where untrusted third-party obfuscation tools/platforms covertly insert master backdoor in software programs. We show that such malicious obfuscation could be hard to identify by the software developer who knows the original unobfuscated program. We demonstrate both undetectable and detectable malicious obfuscators for a number of obfuscation schemes in the theoretical literature, in particular conjunction obfuscation, compute-and-compare obfuscation, hamming-distance obfuscation, and point-function obfuscation. </p