IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
29 June 2022
Hans Heum, Martijn Stam
Public key encryption schemes are increasingly being studied concretely, with an emphasis on tight bounds even in a multi-user setting. Here, two types of formalization have emerged, one with a single challenge bit and one with multiple challenge bits. Another modelling choice is whether to allow key corruptions or not. How tightly the various notions relate to each other has hitherto not been studied in detail. We show that in the absence of corruptions, single-bit left-or-right indistinguishability is the preferred notion, as it tightly implies the other (corruption-less) notions. However, in the presence of corruptions, this implication no longer holds; we suggest the use of a more general notion that tightly implies both existing options. Furthermore, for completeness we study how the relationship between left-or-right versus real-or-random evolves in the multi-user PKE setting.
Cecilia Boschini, Ivan Damgård, Claudio Orlandi
Access Control Encryption (ACE) allows to control information flow between parties by enforcing a policy that specifies which user can send messages to whom. The core of the scheme is a sanitizer, i.e., an entity that ''sanitizes'' all messages by essentially re-encrypting the ciphertexts under its key. In this work we investigate the natural question of whether it is still possible to achieve some meaningful security properties in scenarios when such a sanitization step is not possible.
We answer positively by showing that it is possible to limit corrupted users to communicate only through insecure subliminal channels, under the necessary assumption that parties do not have pre-shared randomness. Moreover, we show that the bandwidth of such channels can be limited to be O(log(n)) by adding public ciphertext verifiability to the scheme under computational assumptions. In particular, we rely on a new security definition for obfuscation, Game Specific Obfuscation (GSO), which is a weaker definition than VBB, as it only requires the obfuscator to obfuscate programs in a specific family of programs, and limited to a fixed security game.
We answer positively by showing that it is possible to limit corrupted users to communicate only through insecure subliminal channels, under the necessary assumption that parties do not have pre-shared randomness. Moreover, we show that the bandwidth of such channels can be limited to be O(log(n)) by adding public ciphertext verifiability to the scheme under computational assumptions. In particular, we rely on a new security definition for obfuscation, Game Specific Obfuscation (GSO), which is a weaker definition than VBB, as it only requires the obfuscator to obfuscate programs in a specific family of programs, and limited to a fixed security game.
Thomas Groß
We establish a set of zero-knowledge arguments that allow for the hashing of a committed secret $a$-bit input $x$ to a committed secret $(k+1)$-bit prime number $p_x$. The zero-knowledge arguments can convince a verifier that a commitment indeed is the correctly generated prime number derived from $x$ with a soundness error probability of at most $2^{-k}+ 2^{-t}$ dependent on the number of zero-knowledge argument rounds $k$ and the number of primality bases $t$ to establish primality. Our constructions offer a range of contributions including enabling dynamic encodings for prime-based accumulator, signature and attribute-based credential schemes allowing to reduce these schemes' public key size and setup requirements considerably and rendering them extensible. While our new primality zero-knowledge arguments are of independent interest, we also show improvements on proving that a secret number is the product of two secret safe primes significantly more efficient than previously known results, with applications to setting up secure special RSA moduli.
Ruize Wang, Kalle Ngo, Elena Dubrova
Creating a good deep learning (DL) model is an art which requires expertise in DL and a large set of labeled data for training neural networks. Neither is readily available. In this paper, we introduce a method which enables us to achieve good results with bad DL models. We use simple multilayer perceptron (MLP) networks, trained on a small dataset, which make strongly biased predictions if used without the proposed method. The core idea is to extend the attack dataset so that at least one of its traces has the ground truth label to which the models are biased towards. The effectiveness of the presented method is demonstrated by attacking an ARM Cortex-M4 CPU implementation of Saber KEM, a finalist of the NIST post-quantum cryptography standardization project, on a nRF52832 system-on-chip supporting Bluetooth 5, using amplitude-modulated EM emanations. Previous amplitude-modulated EM emanation-based attacks on Saber KEM could not recover its messages with a sufficiently high probability. We recover messages with the probability 1 from the profiling device and with the probability 0.74 from a different device. Using messages recovered from chosen ciphertexts, we extract the secret key of Saber KEM.
Chaya Ganesh, Hamidreza Khoshakhlagh, Roberto Parisella
We give an efficient construction of a computational non-interactive witness indistinguishable (NIWI) proof in the plain model, and investigate notions of extraction for NIZKs for algebraic languages. Our starting point is the recent work of Couteau and Hartmann (CRYPTO 2020) who developed a new framework (CH framework) for constructing non-interactive zero-knowledge proofs and arguments under falsifiable assumptions for a large class of languages called algebraic languages. In this paper, we construct an efficient NIWI proof in the plain model for algebraic languages based on the CH framework. In the plain model, our NIWI construction is more efficient for algebraic languages than state-of-the-art Groth-Ostrovsky-Sahai (GOS) NIWI (JACM 2012). Next, we explore knowledge soundness of NIZK systems in the CH framework. We define a notion of strong f-extractability, and show that the CH proof system satisfies this notion.
We then put forth a new definition of knowledge soundness called semantic extraction. We explore the relationship of semantic extraction with existing knowledge soundness definitions and show that it is a general definition that recovers black-box and non-black-box definitions as special cases. Finally, we show that NIZKs for algebraic languages in the CH framework cannot satisfy semantic extraction. We extend this impossibility to a class of NIZK arguments over algebraic languages, namely quasi-adaptive NIZK arguments that are constructed from smooth projective hash functions.
Rabiah Alnashwan, Prosanta Gope, Benjamin Dowling
The 5G mobile communication network provides seamless communications between users and service providers and promises to achieve several stringent requirements, such as seamless mobility and massive connectivity. Although 5G can offer numerous benefits, security and privacy issues still need to be addressed. For example, the inclusion of small cell networks (SCN) into 5G brings the network closer to the connected users, providing a better quality of services (QoS), resulting in a significant increase in the number of Handover procedures (HO), which will affect the security, latency and efficiency of the network. It is then crucial to design a scheme that supports seamless handovers through secure authentication to avoid the consequences of SCN. To address this issue, this article proposes a secure region-based handover scheme with user anonymity and an efficient revocation mechanism that supports seamless connectivity for SCNs in 5G. In this context, we introduce three privacy-preserving authentication protocols, i.e., initial authentication protocol, intra-region handover protocol and inter-region handover protocol, for dealing with three communication scenarios. To the best of our knowledge, this is the first paper to consider the privacy and security in both the intra-region and inter-region handover scenarios in 5G communication. Detailed security and performance analysis of our proposed scheme is presented to show that it is resilient against many security threats, is cost-effective in computation and provides an efficient solution for the 5G enabled mobile communication.
27 June 2022
Barbara Gigerl, Robert Primas, Stefan Mangard
Masking is a popular secret-sharing technique that is used to protect cryptographic implementations against physical attacks like differential power analysis. So far, most research in this direction has focused on finding efficient Boolean masking schemes for well-known symmetric cryptographic algorithms like AES and Keccak. However, especially with the advent of post-quantum cryptography (PQC), arithmetic masking has received increasing attention from the research community. In practice, many PQC algorithms require a combination of arithmetic and Boolean masking, which makes the search for secure and efficient conversion algorithms between these domains (A2B/B2A) an interesting but very challenging research topic. While there already exist lots of tools that can help with the formal verification of Boolean masked implementations, the same cannot be said about arithmetic masking and accompanying mask conversion algorithms.
In this work, we demonstrate the first formal verification approach for (any-order) Boolean and arithmetic masking which can be applied to both hardware and software, while considering side-effects such as glitches and transitions. First, we show how a formal verification approach for Boolean masking can be used in the context of arithmetic masking such that we can verify A2B/B2A conversions for arbitrary masking orders. We investigate various conversion algorithms in hardware and software, and point out several new findings such as glitch-based issues for straightforward implementations of [CGV14]-A2B in hardware, transition-based leakage in Goubin-A2B in software, and more general implementation pitfalls when utilizing common optimization techniques in PQC. We provide the first formal analysis of table-based A2Bs from a probing security perspective and point out that they might not be easy to implement securely on processors that use of memory buffers or caches.
In this work, we demonstrate the first formal verification approach for (any-order) Boolean and arithmetic masking which can be applied to both hardware and software, while considering side-effects such as glitches and transitions. First, we show how a formal verification approach for Boolean masking can be used in the context of arithmetic masking such that we can verify A2B/B2A conversions for arbitrary masking orders. We investigate various conversion algorithms in hardware and software, and point out several new findings such as glitch-based issues for straightforward implementations of [CGV14]-A2B in hardware, transition-based leakage in Goubin-A2B in software, and more general implementation pitfalls when utilizing common optimization techniques in PQC. We provide the first formal analysis of table-based A2Bs from a probing security perspective and point out that they might not be easy to implement securely on processors that use of memory buffers or caches.
Alexandros Bakas, Eugene Frimpong, Antonis Michalas
Homomorphic Encryption (HE) is a modern cryptographic technique that allows direct computations on encrypted data. While relatively new to the mainstream debate, HE has been a solid topic in research for decades. However, despite the technological advances of the past years, HE’s inefficiencies render it impractical for deployment in realistic scenarios. Hence research in the field is still in its initial phase. To overcome certain challenges and bring HE closer to a realization phase, researchers recently introduced the promising concept of Hybrid Homomorphic Encryption (HHE) – a primitive that combines symmetric cryptography with HE. Using HHE, users perform local data encryptions using a symmetric encryption scheme and then outsource them to the cloud. Upon reception, the cloud can transform the symmetrically encrypted data into homomorphic ciphertexts without decrypting them. Such an approach can be seen as an opportunity to build new, privacy-respecting cloud services, as the most expensive operations of HE can be moved to the cloud. In this work, we undertake the task of designing a secure cryptographic protocol based on HHE. In particular, we show how HHE can be used as the main building block of a protocol that allows an analyst to collect data from multiple sources and compute specific functions over them, in a privacy-preserving way. To the best of our knowledge, this is the first work that aims at demonstrating how HHE can be utilized in realistic scenarios, through the design of a secure protocol.
The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Today we are pleased to announce five members that have been elevated to the rank of Fellow for 2022:
- Masayuki Abe, for influential contributions to practical cryptosystems, and for exemplary service to the IACR and the Asia-Pacific cryptography community.
- Christian Cachin, for far-reaching contributions in the fields of cryptography and distributed systems, and for outstanding service to the IACR.
- Claude Carlet, for fundamental contributions to the design and analysis of Boolean functions for cryptographic applications, and for sustained educational leadership.
- Benny Pinkas, for impactful research in the theory and practice of secure multi-party computation, sustained educational leadership, and service to the IACR.
- Yael Tauman Kalai, for foundational contributions in delegated computation and leakage-resilient cryptography, and service to the cryptographic community.
Antonio Sanso
In this short note we explore a particular behaviour of the CSIDH key exchange that leads to a very special form of (shared) key control via the use of the quadratic twists. This peculiarity contained in CSIDH with regard to quadratic twists was already noted in the original CSDIH work and used in several subsequent papers but we believe spelling out this in the form of an attack might be useful to the wider community.
Benoît Cogliati, Jérémy Jean, Thomas Peyrin, Yannick Seurin
We analyze the multi-user (mu) security of a family of nonce-based authentication encryption (nAE) schemes based on a tweakable block cipher (TBC). The starting point of our work is an analysis of the mu security of the SCT-II mode which underlies the nAE scheme Deoxys-II, winner of the CAESAR competition for the defense-in-depth category. We extend this analysis in two directions, as we detail now.
First, we investigate the mu security of several TBC-based variants of the counter encryption mode (including CTRT, the encryption mode used within SCT-II) that differ by the way a nonce, a random value, and a counter are combined as tweak and plaintext inputs to the TBC to produce the keystream blocks that will mask the plaintext blocks. Then, we consider the authentication part of SCT-II and study the mu security of the nonce-based MAC Nonce-as-Tweak (NaT) built from a TBC and an almost universal (AU) hash function. We also observe that the standard construction of an AU hash function from a (T)BC can be proven secure under the assumption that the underlying TBC is unpredictable rather than pseudorandom, allowing much better conjectures on the concrete AU advantage. This allows us to derive the mu security of the family of nAE modes obtained by combining these encryption/MAC building blocks through the NSIV composition method.
Some of these modes require an underlying TBC with a larger tweak length than what is usually available for existing ones. We then show the practicality of our modes by instantiating them with two new TBC constructions, Deoxys-TBC-512 and Deoxys-TBC-640, which can be seen as natural extensions of the Deoxys-TBC family to larger tweak input sizes. Designing such TBCs with unusually large tweaks is prone to pitfalls: Indeed, we show that a large-tweak proposal for SKINNY published at EUROCRYPT 2020 presents an inherent construction flaw. We therefore provide a sound design strategy to construct large-tweak TBCs within the Superposition Tweakey (STK) framework, leading to new Deoxys-TBC and SKINNY variants. We provide software benchmarks indicating that while ensuring a very high security level, the performances of our proposals remain very competitive.
First, we investigate the mu security of several TBC-based variants of the counter encryption mode (including CTRT, the encryption mode used within SCT-II) that differ by the way a nonce, a random value, and a counter are combined as tweak and plaintext inputs to the TBC to produce the keystream blocks that will mask the plaintext blocks. Then, we consider the authentication part of SCT-II and study the mu security of the nonce-based MAC Nonce-as-Tweak (NaT) built from a TBC and an almost universal (AU) hash function. We also observe that the standard construction of an AU hash function from a (T)BC can be proven secure under the assumption that the underlying TBC is unpredictable rather than pseudorandom, allowing much better conjectures on the concrete AU advantage. This allows us to derive the mu security of the family of nAE modes obtained by combining these encryption/MAC building blocks through the NSIV composition method.
Some of these modes require an underlying TBC with a larger tweak length than what is usually available for existing ones. We then show the practicality of our modes by instantiating them with two new TBC constructions, Deoxys-TBC-512 and Deoxys-TBC-640, which can be seen as natural extensions of the Deoxys-TBC family to larger tweak input sizes. Designing such TBCs with unusually large tweaks is prone to pitfalls: Indeed, we show that a large-tweak proposal for SKINNY published at EUROCRYPT 2020 presents an inherent construction flaw. We therefore provide a sound design strategy to construct large-tweak TBCs within the Superposition Tweakey (STK) framework, leading to new Deoxys-TBC and SKINNY variants. We provide software benchmarks indicating that while ensuring a very high security level, the performances of our proposals remain very competitive.
Jian Guo, Ling Song, Haoyang Wang
This paper introduces structure to key, in the related-key attack settings. While the idea of structure has been long used in keyrecovery attacks against block ciphers to enjoy the birthday effect, the same had not been applied to key materials due to the fact that key structure results in uncontrolled differences in key and hence affects the validity or probabilities of the differential trails. We apply this simple idea to improve the related-key boomerang attack against AES-256 by Biryukov and Khovratovich in 2009. Surprisingly, it turns out to be effective, i.e., both data and time complexities are reduced by a factor of about 2^8, to 2^92 and 2^91 respectively, at the cost of the amount of required keys increased from 4 to 2^19. There exist some tradeoffs between the data/time complexity and the number of keys. To the best of our knowledge, this is the first essential improvement of the attack against the full AES-256 since 2009. It will be interesting to see if the structure technique can be applied to other AES-like block ciphers, and to tweaks rather than keys of tweakable block ciphers so the amount of required keys of the attack will not be affected.
Yong-Jin Kim, Dok-Jun An, Kum-Sok Sin, Son-Gyong Kim
In this paper, we proposed some vulnerabilities of a recent pairing-based certificateless authenticated key agreement protocol for blockchain-based wireless body area networks (WBAN). According to our analysis, this protocol is insecure against key offset attack (KOA), basic impersonation attack (BIA), and man-in-the-middle attack (MMA) of the malicious key generation center (KGC) administrators. We also found and pointed out some errors in the description of the protocol.
Martin R. Albrecht, Jianwei Li
Primal attacks against the Learning With Errors (LWE) problem rely on reducing \(q\)-ary lattices. These reduced bases have been observed to exhibit a so-called ``Z-shape'' on their Gram--Schmidt vectors. We propose an efficient simulator to accurately predict this Z-shape behaviour, which we back up with extensive simulations and experiments. We also formalise (under standard heuristics) the intuition that the presence of a Z-shape makes enumeration-based primal lattice attacks faster. Furthermore, we upgrade the LWE or lattice estimator with our simulator to assess and then rule out the impact of the \(q\)-ary Z-shape on solving LWE instances derived from parameter sets for NIST PQC candidates. We consider this improved estimator to be of independent interest.
Justin Holmgren, Minghao Liu, LaKyah Tyner, Daniel Wichs
Property-preserving hashing (PPH) consists of a family of compressing hash functions $h$ such that, for any two inputs $x,y$, we can correctly identify whether some property $P(x,y)$ holds given only the digests $h(x),h(y)$. In a basic PPH, correctness should hold with overwhelming probability over the choice of $h$ when $x,y$ are worst-case values chosen a-priori and independently of $h$. In an adversarially robust PPH (RPPH), correctness must hold even when $x,y$ are chosen adversarially and adaptively depending on $h$. Here, we study (R)PPH for the property that the Hamming distance between $x$ and $y$ is at most $t$.
The notion of (R)PPH was introduced by Boyle, LaVigne and Vaikuntanathan (ITCS '19), and further studied by Fleischhacker, Simkin (Eurocrypt '21) and Fleischhacker, Larsen, Simkin (Eurocrypt '22). In this work, we obtain improved constructions that are conceptually simpler, have nearly optimal parameters, and rely on more general assumptions than prior works. Our results are:
* We construct information-theoretic non-robust PPH for Hamming distance via syndrome list-decoding of linear error-correcting codes. We provide a lower bound showing that this construction is essentially optimal.
* We make the above construction robust with little additional overhead, by relying on homomorphic collision-resistant hash functions, which can be constructed from either the discrete-logarithm or the short-integer-solution assumptions. The resulting RPPH achieves improved compression compared to prior constructions, and is nearly optimal.
* We also show an alternate construction of RPPH for Hamming distance under the minimal assumption that standard collision-resistant hash functions exist. The compression is slightly worse than our optimized construction using homomorphic collision-resistance, but essentially matches the prior state of the art constructions from specific algebraic assumptions.
* Lastly, we study a new notion of randomized robust PPH (R2P2H) for Hamming distance, which relaxes RPPH by allowing the hashing algorithm itself to be randomized. We give an information-theoretic construction with optimal parameters.
The notion of (R)PPH was introduced by Boyle, LaVigne and Vaikuntanathan (ITCS '19), and further studied by Fleischhacker, Simkin (Eurocrypt '21) and Fleischhacker, Larsen, Simkin (Eurocrypt '22). In this work, we obtain improved constructions that are conceptually simpler, have nearly optimal parameters, and rely on more general assumptions than prior works. Our results are:
* We construct information-theoretic non-robust PPH for Hamming distance via syndrome list-decoding of linear error-correcting codes. We provide a lower bound showing that this construction is essentially optimal.
* We make the above construction robust with little additional overhead, by relying on homomorphic collision-resistant hash functions, which can be constructed from either the discrete-logarithm or the short-integer-solution assumptions. The resulting RPPH achieves improved compression compared to prior constructions, and is nearly optimal.
* We also show an alternate construction of RPPH for Hamming distance under the minimal assumption that standard collision-resistant hash functions exist. The compression is slightly worse than our optimized construction using homomorphic collision-resistance, but essentially matches the prior state of the art constructions from specific algebraic assumptions.
* Lastly, we study a new notion of randomized robust PPH (R2P2H) for Hamming distance, which relaxes RPPH by allowing the hashing algorithm itself to be randomized. We give an information-theoretic construction with optimal parameters.
Viet Tung Hoang, Cong Wu, Xin Yuan
System logs are crucial for forensic analysis, but to be useful, they need to be tamper-proof. To protect the logs, a number of secure logging systems have been proposed from both academia and the industry. Unfortunately, except for the recent KennyLoggings construction, all other logging systems are broken by an attack of Paccagnella et al. (CCS 2020). In this work, we build a secure logging system that improves KennyLoggings in several fronts: adoptability, security, and performance. Our key insight for performance gain is to use AES on a fixed, known key. While this trick is widely used in secure distributed computing, this is the first time it has found an application in the area of symmetric-key cryptography.
Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Vesselin Velichkov
Advanced cryptographic protocols such as Zero-knowledge (ZK) proofs of knowledge, widely used in cryptocurrency applications such as Bitcoin, Ethereum and Zcash, demand new cryptographic hash functions that are efficient not only over the binary field $\mathbb{F}_2$, but also over large fields of prime characteristic $\mathbb{F}_p$. This need has been acknowledged by the wider community and new so-called Arithmetization-Oriented (AO) hash functions have been proposed in response, e.g. MiMC-Hash, Rescue and Poseidon to name a few. In this paper we propose Anemoi: a new family of ZK-friendly AO hash functions.
The main features that set Anemoi apart from other such families are that 1) it is designed to be efficient within multiple proof systems (e.g. Groth16, Plonk, etc.), 2) it contains dedicated functions optimised for specific applications (namely Merkle tree hashing and general purpose hashing), 3) has competitive performance e.g. about a factor of 2 improvement over Poseidon and Rescue in terms of R1CS constraints, and a 10%-28% improvement over a highly optimized Poseidon implementation in Plonk constraints. On the theoretical side, Anemoi pushes further the frontier in understating the design principles that are truly entailed by arithmetization-orientation. In particular, we identify and exploit a previously unknown relationship between CCZ-equivalence and arithmetization-orientation. In addition, we propose two new standalone components that can be easily reused in new designs. One is a new S-box called Flystel, based on the well-studied butterfly structure, and the second is Jive -- a new mode of operation, inspired by the "Latin dance'' symmetric algorithms (Salsa, ChaCha and derivatives).
Mahdi Sedaghat, Daniel Slamanig, Markulf Kohlweiss, Bart Preneel
The by now broadly accepted reliance of society on online services, led to a push for decentralization to mitigate the societal and technical risks caused by single points of failure (PoF). One such PoF are cryptographic keys. Thus there is renewed interest in threshold cryptography to distribute the generation and use of such keys. Structure-preserving signatures (SPS) are an important building block for privacy-preserving cryptographic protocols such as electronic cash and (delegatable) anonymous credentials. However, to date, no structure-preserving threshold signatures (SPTS) are available. This is unfortunate, as another PoF is centralized identity management, which could be mitigated by anonymous credentials.
In this work we aim to close this gap by introducing a notion and constructions of (non-) interactive SPTS. While it is relatively easy to devise interactive SPTS supporting static corruptions, e.g., based on the SPS of Ghadafi (CT-RSA'16), constructing non-interactive SPTS is a much more delicate task. Due to their structural properties, starting from existing SPS does not yield secure schemes. Thus, we take a different path and first introduce the notion of message-indexed SPS, a variant of SPS that is parameterized by a message indexing function. Inspired by Pointcheval-Sanders (PS) signatures (CT-RSA'16) and the SPS of Ghadafi, we then present a message-indexed SPS, which is non-interactive threshold-friendly. We prove its security in the random oracle model based on a variant of the generalized PS assumption. Based on our message-indexed SPS we then propose the first non-interactive message-indexed SPTS, which we prove to be secure under adaptive corruption. Finally, we discuss applications of SPTS to privacy-preserving primitives.
In this work we aim to close this gap by introducing a notion and constructions of (non-) interactive SPTS. While it is relatively easy to devise interactive SPTS supporting static corruptions, e.g., based on the SPS of Ghadafi (CT-RSA'16), constructing non-interactive SPTS is a much more delicate task. Due to their structural properties, starting from existing SPS does not yield secure schemes. Thus, we take a different path and first introduce the notion of message-indexed SPS, a variant of SPS that is parameterized by a message indexing function. Inspired by Pointcheval-Sanders (PS) signatures (CT-RSA'16) and the SPS of Ghadafi, we then present a message-indexed SPS, which is non-interactive threshold-friendly. We prove its security in the random oracle model based on a variant of the generalized PS assumption. Based on our message-indexed SPS we then propose the first non-interactive message-indexed SPTS, which we prove to be secure under adaptive corruption. Finally, we discuss applications of SPTS to privacy-preserving primitives.
Francesca Falzon, Kenneth G. Paterson
Ghosh, Kamara and Tamassia (ASIA CCS 2021) presented a Graph Encryption Scheme supporting shortest path queries. We show how to perform a query recovery attack against this GKT scheme when the adversary is given the original graph together with the leakage of certain subsets of queries. Our attack falls within the security model used by Ghosh et al., and is the first targeting schemes supporting shortest path queries. Our attack uses classical graph algorithms to compute the canonical names of the single-destination shortest path spanning trees of the underlying graph and uses these canonical names to pre-compute the set of candidate queries that match each response. Then, when all shortest path queries to a single node have been observed, the canonical names for the corresponding query tree are computed and the responses are matched to the candidate queries from the offline phase. The output is guaranteed to contain the correct query. For a graph on $n$ vertices, our attack runs in time $O(n^3)$ and matches the time complexity of the GKT scheme's setup. We evaluate the attack's performance using the real world datasets used in the original paper and on random graphs, and show that for the real-world datasets as many as 21.9% of the queries can be uniquely recovered and as many as 50% of the queries result in sets of only three candidates.
Tim Beyne, Vincent Rijmen
A systematic approach to the fixed-key analysis of differential probabilities is proposed. It is based on the propagation of 'quasidifferential trails', which keep track of probabilistic linear relations on the values satisfying a differential characteristic in a theoretically sound way. It is shown that the fixed-key probability of a differential can be expressed as the sum of the correlations of its quasidifferential trails.
The theoretical foundations of the method are based on an extension of the difference-distribution table, which we call the quasidifferential transition matrix. The role of these matrices is analogous to that of correlation matrices in linear cryptanalysis. This puts the theory of differential and linear cryptanalysis on an equal footing.
The practical applicability of the proposed methodology is demonstrated by analyzing several differentials for RECTANGLE, KNOT, Speck and Simon. The analysis is automated and applicable to other SPN and ARX designs. Several attacks are shown to be invalid, most others turn out to work only for some keys but can be improved for weak-keys.
The theoretical foundations of the method are based on an extension of the difference-distribution table, which we call the quasidifferential transition matrix. The role of these matrices is analogous to that of correlation matrices in linear cryptanalysis. This puts the theory of differential and linear cryptanalysis on an equal footing.
The practical applicability of the proposed methodology is demonstrated by analyzing several differentials for RECTANGLE, KNOT, Speck and Simon. The analysis is automated and applicable to other SPN and ARX designs. Several attacks are shown to be invalid, most others turn out to work only for some keys but can be improved for weak-keys.