Improved impossible differential and biclique cryptanalysis of HIGHT

HIGHT is a lightweight block cipher introduced in CHES 2006 by Hong et al as a block cipher suitable for low‐resource applications. In this paper, we propose improved impossible differential and biclique attacks on HIGHT block cipher both exploiting the permutation‐based property of the cipher's key schedule algorithm as well as its low diffusion. For impossible differential attack, we found a new 17‐round impossible differential characteristic that enables us to propose a new 27‐round impossible differential attack. The total time complexity of the attack is 2^120.4 where an amount of 2^59.3 chosen plaintext‐ciphertext pairs and 2^107.4 memory are required. We also instantiate a new biclique cryptanalysis of HIGHT, which is based on the new idea of splitting each of the forward and backward keys into 2 parts where the computations associated to each one are performed independently. The time complexity and data complexity of this attack are 2^125.7 and 2⁴², respectively. To the best of our knowledge, this is the fastest biclique attack on full‐round HIGHT.     

分组密码AES的非平衡Biclique结构性质

Biclique攻击是目前唯一能将对AES全轮攻击降至穷举攻击之下的密钥恢复攻击,Biclique结构决定着攻击算法的复杂性,为了提高对全轮AES 的Biclique攻击的效率,研究了AES的非平衡Biclique结构性质。通过分析AES编码环节对Biclique结构的影响,给出了寻找AES非平衡Biclique结构的算法思路及其相关性质,对于AES-128、AES-192、AES-256三种密码模型,分别给出了其非平衡Biclique结构的分布特征,具体列出了初始差分活动字节个数达到最小或最大的非平衡Biclique结构。     

Using underapproximations for sparse nonnegative matrix factorization

Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc.We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs.We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is ₂ ^P-complete, answering a question posed by Kleine Büning and Zhao.     

Linear-time algorithm for generating c-isolated bicliques

Bicliques are widely used to solve various real-world problems encountered in bio-informatics, data mining and networks. We consider c-isolated bicliques, a variation of bicliques. The c-isolated bicliques can model communities in social and biological networks. We propose an efficient algorithm to generate all c-isolated maximal bicliques in a given bipartite graph. Our algorithm exploits underlying properties of an isolated biclique to trim the input graph. Furthermore, the algorithm deploys the vertex cover enumeration algorithm based on fixed parameter tractability and lists all maximal c-isolated bicliques in linear time (in terms of graph size), for constant c.     

基于二部图的概念聚类研究

传统概念聚类算法中簇的更新和存储不仅依赖于对象数目和属性数目,而且依赖于属性值的数目,这种局限性使其不适用于大型数据集。提出一种新的基于二部图的概念聚类算法（BGBCC）,该算法通过获得二部图的近似极大ε二元组集,有效地进行数据与属性的关联聚类。实验表明,该算法能得到较好的聚类结果,且能在较短的时间内进行大型数据集的概念聚类。     

Biclique cryptanalysis on lightweight block cipher: HIGHT and Piccolo

Biclique cryptanalysis is an attack that improves the computational complexity by finding a biclique which is a kind of bipartite graph. We present a single-key full-round attack of lightweight block ciphers, HIGHT and Piccolo by using biclique cryptanalysis. In this paper, a 9-round biclique is constructed for HIGHT and a 4-round biclique for Piccolo. These new bicliques are used to recover secret keys for the full rounds of HIGHT, Piccolo-80 and Piccolo-128, the computational complexity of 2^125.93, 2^79.34 and 2^127.36, respectively. The computational complexity of attacking HIGHT by a biclique cryptanalysis is reduced from 2^126.4. This is the first full-round attack on both Piccolo-80 and Piccolo-128.     

Algorithms for induced biclique optimization problems

We present polynomial time algorithms for induced biclique optimization problems in the following families of graphs: polygon-circle graphs, 4-hole-free graphs, complements of interval-filament graphs and complements of subtree-filament graphs. Such problems are to find maximum: induced bicliques, induced balanced bicliques and induced edge bicliques. These problems have applications for biclique clustering of proteins by PPI criteria, of documents, and of web pages.     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is _P ² P-complete, answering a question posed by Kleine Büning and Zhao.     

Biclique cryptanalysis on lightweight block ciphers I-PRESENT-80 and I-PRESENT-128

I-PRESENT was a lightweight SPN block cipher for resource-constraint environments such as RFID tags and sensor networks.The biclique structures of I-PRESENT with sieve-in-the-middle technique was an constracted.The biclique cryptanalysis schemes on full-round I-PRESENT-80 and I-PRESENT-128 were proposed for the first time.The results show that the data complexity of the biclique cryptanalysis on I-PRESENT-80 and I-PRESENT-128 is 2 ²⁶ and 2³⁶ chosen ciphertexts respectively,and the time complexity on them is 2 ^79.48 and 2 ^127.33 encryptions respectively.The time and data complexity are better than that of the exhaustive attack.In addition,the time complexity on them can be reduced to 2 ^78.61 and 2^126.48 encryptions by using related-key technology of I-PRESENT.