Lei Wei: Analysis of Iterated Block Ciphers
Name: Lei Wei
Topic: Analysis of Iterated Block Ciphers
A block cipher is the foundation stone of symmetric-key cryptography. Due to its simplicity and high performance, it is often the workhorse for providing confidentiality - one of the primary goals of cryptography. Hence the security of a block cipher is of fundamental importance in the entire infrastructure of cryptography, and therefore block ciphers shall be analyzed and evaluated. This practice is called block cipher cryptanalysis. In this thesis, we analyze a few block ciphers in the classic meet-in-the-middle model and in the recently proposed
multidimensional linear cryptanalysis model.
Besides for encryption, block ciphers are also one of the most versatile building blocks used for constructing many other cryptographic primitives. One such example is the compression function of cryptographic hash functions, and there is a close relation between the security analysis of block ciphers and hash functions. In addition, many dedicated cryptographic hash functions are designed with ideas used in block ciphers. Therefore, it is natural that many block cipher
cryptanalysis techniques can be transferred to hash function analysis. In this thesis, we analyze hash functions with differential cryptanalysis and techniques inspired by differential cryptanalysis. On the other hand, recent advances in hash function cryptanalysis contribute to the analysis of block ciphers. We give one such example too.
In total we have four main topics on (or closely related to) the security analysis of block ciphers.
- We study the multidimensional extension to Matsui’s Algorithm 1 and find improvements that lower the attack’s costs. The new attacks are applied to 9-round and 4-round Serpent, with interesting observations on these improvements and the framework.
- We study meet-in-the-middle attacks and their application to the hardware-oriented block cipher Ktantan family and reduced DES. Several recent hash function analysis techniques are used f[...]
Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key, by Alex Biryukov and Charles Bouillaguet and Dmitry Khovratovich
In this paper we pick up an old challenge to design public key or white-box constructions from symmetric cipher components. We design several encryption schemes based on the ASASA structure
ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. While explaining our design process we show several instructive attacks on the
weaker variants of our schemes.
Relaxed Two-to-one Recoding Schemes, by Omkant Pandey and Kim Ramchen and Brent Waters
A two-to-one recoding (TOR) scheme is a new cryptographic primitive, proposed in the recent work of Gorbunov, Vaikuntanathan, and Wee (GVW), as a means to construct attribute-based encryption
(ABE) schemes for all boolean circuits. GVW show that TOR schemes can be constructed assuming the hardness of the learning-with-errors (LWE) problem.
We propose a slightly weaker variant of TOR schemes called correlation-relaxed two-to-one recoding (CR-TOR). Unlike the TOR schemes, our weaker variant does not require an encoding function to
be pseudorandom on correlated inputs. We instead replace it with an indistinguishability property that states a ciphertext is hard to decrypt without access to a certain encoding. The primary benefit of this relaxation is that it allows the construction of ABE for circuits using the TOR paradigm from a broader class of cryptographic assumptions.
We show how to construct a CR-TOR scheme from the noisy cryptographic multilinear maps of Garg, Gentry, and Halevi as well as those of Coron, Lepoint, and Tibouchi. Our framework leads to an instantiation of ABE for circuits that is conceptually different from the existing constructions.
Related-Key Secure Pseudorandom Functions: The Case of Additive Attacks, by Benny Applebaum and Eyal Widder
In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over relatively complicated groups (e.g., $\\Z^*_q$ where $q$ is a large prime) that arise from the algebraic structure of the underlying cryptographic assumption (DDH/DLIN). In contrast, applications typically require RKA-security with respect to simple additive relations such as XOR or addition modulo a power-of-two.
In this paper, we partially fill this gap by showing that it is possible to deal with simple additive relations at the expense of relaxing the model of the attack. We introduce several natural relaxations of RKA-security, study the relations between these notions, and describe efficient constructions either under lattice assumptions or under general assumptions. Our results enrich the landscape of RKA security and suggest useful trade-offs between the attack model and the family of possible relations.