It is known that various types of location privacy attacks can be carried out using a personalized transition matrix that is learned for each target user, or a population transition matrix that is common to all target users. However, since many users disclose only a small amount of location information in their daily lives, the training data can be extremely sparse. The aim of this paper is to clarify the risk of location privacy attacks in this realistic situation. To achieve this aim, we propose a learning method that uses tensor factorization (or matrix factorization) to accurately estimate personalized transition matrices (or a population transition matrix) from a small amount of training data. To avoid the difficulty in directly factorizing the personalized transition matrices (or population transition matrix), our learning method first factorizes a transition count tensor (or matrix), whose elements are the number of transition counts that the user has made, and then normalizes counts to probabilities. We focus on a localization attack, which derives an actual location of a user at a given time instant from an obfuscated trace, and compare our learning method with the maximum likelihood (ML) estimation method in both the personalized matrix mode and the population matrix mode. The experimental results using four real data sets show that the ML estimation method performs only as well as a random guess in many cases, while our learning method significantly outperforms the ML estimation method in all of the four data sets.

Recent studies have proposed various attacks against location privacy using a Markov Chain transition matrix trained for each user. However, when a user has disclosed only a small amount of location information in the past, the training data can be extremely sparse. In this paper, we show how the attacker can solve this sparse data problem, and how the defender can defend against this type of attack. Our proposal is twofold: 1) We propose a training method that regards a set of transition matrices as a “tensor”, and adopt tensor factorization to robustly estimate transition matrices from a small amount of training data. 2) We then focus on a location prediction attack, which predicts a location of a target user from a past location that he/she disclosed, and propose a region merging method to minimize the region size as an optimal defense. The experimental results using the dataset of taxi traces show the effectiveness of our proposals. We also point out that our region merging method is effective especially when the defender has Big Data to train transition matrices.

Many people with visual impairments complain about the poor accessibility of conventional CAPTCHA systems because the audio-style test is too difficult for humans. Even a U.S. governmental site, the “We the People” public website, was criticized for the same reason, and thus it implemented a more accessible quiz-based CAPTCHA system. However, this system is vulnerable to simple heuristics. In this study, we demonstrate the insecurity of this type of CAPTCHA system. We demonstrate that our solver program can beat the CAPTCHA with a success rate of over 99%. In addition, we propose a new verbal-style system to replace the quiz-based CAPTCHA. Our system synthesizes several sentences, which have different degrees of naturalness in terms of their contextual meaning, from a set of source documents using a flexible-order Markov chain. Only human users can perceive the difference in the semantics and select the most (or the least) meaningful option correctly. This test is implemented in a verbal style, which means that it is universally suitable for any type of perceptual channel. We implemented our proposed scheme and analyzed its security based on experiments.

An authentication protocol is proposed which originates from the elements of the authentication protocols belonging to the HB-family and the protocols based on employment of pseudorandom number generators. Desired features of the proposed protocol have been achieved via combining the pseudorandomnes generated by a compact keystream generator, randomness and dedicated homophonic and error-correction coding. It is shown that implementation complexity of the protocol is low. Security of the proposed protocol is considered from an information-theoretic and a computational-complexity points of view assuming the passive attacking The performed security evaluation yields an indication for a conjecture on the security within certain active attacking scenarios as well.

We developed a new Web authentication protocol with password-based mutual authentication which prevents various kinds of phishing attacks. This protocol provides a protection of user's passwords against any phishers even if a dictionary attack is employed, and prevents phishers from imitating a false sense of successful authentication to users. The protocol is designed considering interoperability with many recent Web applications which requires many features which current HTTP authentication does not provide. The protocol is proposed as an Internet Draft submitted to IETF, and implemented in both server side (as an Apache extension) and client side (as a Mozilla-based browser and an IE-based one).

We give a tracing algorithm for 2-secure probabilis- tic fingerprinting codes with the property that it never accuses innocent users when there are up to 2 attackers. Moreover, by using our code and tracing algorithm, innocent users are also unlikely to be accused even if either the number of attackers or attackers' abilities exceed our assumption. Our code is the first example of collusion-secure fingerprinting codes with both of these two properties. Furthermore, our code has shorter length among the preceding 2-secure codes, and possesses further properties desirable in a practical use.