Abstract At CRYPTO 2021, Dong et al. proposed an automatic method of Meet-in-the-Middle (MITM) key-recovery attacks. In this paper, we further extend it to a new automatic model which can be used to find low-data complexity attacks. With the help of the automatic model, we propose MITM attacks against reduced-round versions of all the six members of the SKINNY family with extremely low-data complexity. More precisely, we present MITM attacks against 19-round SKINNY-$n$-$3n$, 15-round SKINNY-$n$-$2n$, 11-round SKINNY-$n$-$n$ with three, two, one plaintext-ciphertext pairs, separately. In addition, we can attack two more rounds and three more rounds with no more than $2^8$ and $2^{32}$ data complexity, respectively.

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of the objects in a given dataset. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, etc. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for supporting it. Our methods utilize some novel techniques, such as upper bound score pruning and bitmap binning strategy, to boost query efficiency. Extensive experiments with both real and synthetic data sets demonstrate the efficiency of our presented algorithms.

The incomplete data is universal in many real-life applications due to data integration, the limitation of devices, etc. In this demonstration, we present S i 2 p , a restaurant recommendation System with Preference queries on Incomplete Information. S i 2 p is capable of friendly recommending desirable restaurants based on preference queries that take the incomplete ratings information into consideration. It adopts the browser-server model, and incorporates three functionality modules including friendly and convenient query submission , flexible and useful result explanation , timely and incremental dataset interaction. S i 2 p provides the server side based on an extended PostgreSQL database that integrates two types of preference queries, namely, skyline and top- k dominating queries over incomplete data. It also offers the browser-based interface for the users to interact with the system. Using a real restaurant dataset from TripAdvisor, we demonstrate S i 2 p can recommend and explore the restaurants in a friendly way.

Given a setS of multidimensional objects and a query object q, a k nearest neighbor (kNN) query finds from S the k closest objects to q. This query is a fundamental problem in database, data mining, and information retrieval research. It plays an important role in a wide spectrum of real applications such as image recognition and location-based services. However, due to the failure of data transmission devices, improper storage, and accidental loss, incomplete data exist widely in those applications, where some dimensional values of data items are missing. In this paper, we systematically study incomplete k nearest neighbor (IkNN) search, which aims at the kNN query for incomplete data. We formalize this problem and propose an efficient lattice partition algorithm using our newly developed LαB index to support exact IkNN retrieval, with the help of two pruning heuristics, i.e., α value pruning and partial distance pruning. Furthermore, we propose an approximate algorithm, namely histogram approximate, to support approximate IkNN search with improved search efficiency and guaranteed error bound. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of newly designed indexes and pruning heuristics, as well as the performance of our presented algorithms under a variety of experimental settings.

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of objects in a given dataset. It combines the advantages of skyline and top-k queries, and plays an important role in many decision support applications. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, and so on. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for answering TKD queries over incomplete data. Our methods employ some noveltechniques, such as upper bound score pruning, bitmap pruning, and partial score pruning, to boost query efficiency. Extensive experimental evaluation using both real and synthetic datasets demonstrates the effectiveness of our developed pruning heuristics and the performance of our presented algorithms.