The shuffle model of DP (Differential Privacy) provides high utility by introducing a shuffler that randomly shuffles noisy data sent from users. However, recent studies show that existing shuffle protocols suffer from the following two major drawbacks. First, they are vulnerable to local data poisoning attacks, which manipulate the statistics about input data by sending crafted data, especially when the privacy budget$\varepsilon$is small. Second, the actual value of$\varepsilon$is increased by collusion attacks by the data collector and users. In this paper, we address these two issues by thoroughly exploring the potential of the augmented shuffle model, which allows the shuffler to perform additional operations, such as random sampling and dummy data addition. Specifically, we propose a generalized framework for local-noise-free protocols in which users send (encrypted) input data to the shuffler without adding noise. We show that this generalized protocol provides DP and is robust to the above two attacks if a simpler mechanism that performs the same process on binary input data provides DP. Based on this framework, we propose three concrete protocols providing DP and robustness against the two attacks. Our first protocol generates the number of dummy values for each item from a binomial distribution and provides higher utility than several state-of-the-art existing shuffle protocols. Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution: asymmetric two-sided geometric distribution. Our third protocol is a special case of our second protocol and provides pure ∊-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.

Differentially private triangle counting in graphs is essential for analyzing connection patterns and calculating clustering coefficients while protecting sensitive individual information. Previous works have relied on either central or local models to enforce differential privacy. However, a significant utility gap exists between the central and local models of differentially private triangle counting, depending on whether or not a trusted server is needed. In particular, the central model provides a high accuracy but necessitates a trusted server. The local model does not require a trusted server but suffers from limited accuracy. Our paper introduces a crypto-assisted differentially private triangle counting system, named CARGO, leveraging cryptographic building blocks to improve the effectiveness of differentially private triangle counting without assumption of trusted servers. It achieves high utility similar to the central model but without the need for a trusted server like the local model. CARGO consists of three main components. First, we introduce a similarity-based projection method that reduces the global sensitivity while preserving more triangles via triangle homogeneity. Second, we present a triangle counting scheme based on the additive secret sharing that securely and accurately computes the triangles while protecting sensitive information. Third, we design a distributed perturbation algorithm that perturbs the triangle count with minimal but sufficient noise. We also provide a comprehensive theoretical and empirical analysis of our proposed methods. Extensive experiments demonstrate that our CARGO significantly outperforms the local model in terms of utility and achieves high-utility triangle counting comparable to the central model.

Continuous authentication has been widely studied to provide high security and usability for mobile devices by continuously monitoring and authenticating users. Recent studies adopt multibiometric fusion for continuous authentication to provide high accuracy even when some of captured biometric data are of a low quality. However, existing continuous fusion approaches are resource-heavy as they rely on all classifiers being activated all the time and may not be suitable for mobile devices.In this paper, we propose a new approach to multibiometric continuous authentication: two-dimensional dynamic fusion. Our key insight is that multibiometric continuous authentication calculates two-dimensional matching scores over classifiers and over time. Based on this, we dynamically select a set of classifiers based on the context in which authentication is taking place, and fuse matching scores by multi-classifier fusion and multi-sample fusion. Through experimental evaluation, we show that our approach provides a better balance between resource usage and accuracy than the existing fusion methods. In particular, we show that our approach provides higher accuracy than the existing methods with the same number of score calculations by adopting multi-sample fusion.

LDP (Local Differential Privacy) and its variants have been recently studied to analyze personal data collected from IoT (Internet of Things) devices while strongly protecting user privacy. In particular, a recent study proposes a general privacy notion called ID-LDP (Input-Discriminative LDP), which introduces a privacy budget for each input value to deal with different levels of sensitivity. However, it is unclear how to set an appropriate privacy budget for each input value, especially in current situations where re-identification is considered a major risk, e.g., in GDPR. Moreover, the possible number of input values can be very large in IoT. Consequently, it is also extremely difficult to manually check whether a privacy budget for each input value is appropriate. In this paper, we propose algorithms to automatically tune privacy budgets in ID-LDP so that obfuscated data strongly prevent re-identification. We also propose a new instance of ID-LDP called OneID-LDP (One-Budget Input-Discriminative LDP) to prevent re-identification with high utility. Through comprehensive experiments using four real datasets, we show that existing instances of ID-LDP lack either utility or privacy – they overprotect personal data or are vulnerable to re-identification attacks. Then we show that our OneID-LDP mechanisms with our privacy budget tuning algorithm provide much higher utility than LDP mechanisms while strongly preventing re-identification.

For a better understanding of anonymization methods for location traces, we have designed and held a location trace anonymization contest that deals with a long trace (400 events per user) and fine-grained locations (1024 regions). In our contest, each team anonymizes her original traces, and then the other teams perform privacy attacks against the anonymized traces. In other words, both defense and attack compete together, which is close to what happens in real life. Prior to our contest, we show that re-identification alone is insufficient as a privacy risk and that trace inference should be added as an additional risk. Specifically, we show an example of anonymization that is perfectly secure against re-identification and is not secure against trace inference. Based on this, our contest evaluates both the re-identification risk and trace inference risk and analyzes their relationship. Through our contest, we show several findings in a situation where both defense and attack compete together. In particular, we show that an anonymization method secure against trace inference is also secure against re-identification under the presence of appropriate pseudonymization. We also report defense and attack algorithms that won first place, and analyze the utility of anonymized traces submitted by teams in various applications such as POI recommendation and geo-data analysis.

Publishing graph statistics under node differential privacy has attracted much attention since it provides a stronger privacy guarantee than edge differential privacy. Existing works related to node differential privacy assume a trusted data curator who holds the whole graph. However, in many applications, a trusted curator is usually not available due to privacy and security issues. In this paper, for the first time, we investigate the problem of publishing graph statistics under Node Local Differential privacy (Node-LDP), which does not rely on a trusted server. We propose an algorithm to publish the degree distribution with Node-LDP by exploring how to select the graph projection parameter in the local setting and how to execute the graph projection locally. Specifically, we propose a crypto-assisted local projection method based on cryptographic primitives, achieving the higher accuracy than our baseline pureLDP local projection method. Furthermore, we improve our baseline graph projection method from node-level to edge-level that preserves more neighboring information, owning better utility. Finally, extensive experiments on real-world graphs show that crypto-assisted parameter selection owns better utility than pureLDP parameter selection, and edge-level local projection provides higher accuracy than node-level local projection, improving by up to 57.2% and 79.8%, respectively.

Subgraph counting is fundamental for analyzing connection patterns or clustering tendencies in graph data. Recent studies have applied LDP (Local Differential Privacy) to subgraph counting to protect user privacy even against a data collector in social networks. However, existing local algorithms suffer from extremely large estimation errors or assume multi-round interaction between users and the data collector, which requires a lot of user effort and synchronization.

Transfer learning has been widely studied and gained increasing popularity to improve the accuracy of machine learning models by transferring some knowledge acquired in different training. However, no prior work has pointed out that transfer learning can strengthen privacy attacks on machine learning models. In this paper, we propose TransMIA (Transfer learning-based Membership Inference Attacks), which use transfer learning to perform membership inference attacks on the source model when the adversary is able to access the parameters of the transferred model. In particular, we propose a transfer shadow training technique, where an adversary employs the parameters of the transferred model to construct shadow models, to significantly improve the performance of membership inference when a limited amount of shadow training data is available to the adversary. We evaluate our attacks using two real datasets, and show that our attacks outperform the state-of-the-art that does not use our transfer shadow training technique. We also compare four combinations of the learning-based/entropy-based approach and the fine-tuning/freezing approach, all of which employ our transfer shadow training technique. Then we examine the performance of these four approaches based on the distributions of confidence values, and discuss possible countermeasures against our attacks.

Abstract With the widespread use of LBSs (Location-based Services), synthesizing location traces plays an increasingly important role in analyzing spatial big data while protecting user privacy. In particular, a synthetic trace that preserves a feature specific to a cluster of users (e.g., those who commute by train, those who go shopping) is important for various geo-data analysis tasks and for providing a synthetic location dataset. Although location synthesizers have been widely studied, existing synthesizers do not provide su˚cient utility, privacy, or scalability, hence are not practical for large-scale location traces. To overcome this issue, we propose a novel location synthesizer calledPPMTF (Privacy-Preserving Multiple Tensor Factorization). We model various statistical features of the original traces by a transition-count tensor and a visit-count tensor. We factorize these two tensors simultaneously via multiple tensor factorization, and train factor matrices via posterior sampling. Then we synthesize traces from reconstructed tensors, and perform a plausible deniability test for a synthetic trace. We comprehensively evaluate PPMTF using two datasets. Our experimental results show that PPMTF preserves various statistical features including cluster-specific features, protects user privacy, and synthesizes large-scale location traces in practical time. PPMTF also significantly outperforms the state-of-theart methods in terms of utility and scalability at the same level of privacy.

Abstract Privacy risks of collaborative filtering (CF) have been widely studied. The current state-of-theart inference attack on user behaviors (e.g., ratings/purchases on sensitive items) for CF is by Calandrino et al. (S&P, 2011). They showed that if an adversary obtained a moderate amount of user’s public behavior before some timeT, she can infer user’s private behavioraftertimeT. However, the existence of an attack that infers user’s private behaviorbefore Tremains open. In this paper, we propose the first inference attack that reveals past private user behaviors. Our attack departs from previous techniques and is based onmodel inversion(MI). In particular, we propose the first MI attack on factorization-based CF systems by leveraging data poisoning by Li et al. (NIPS, 2016) in a novel way. We inject malicious users into the CF system so that adversarialy chosen “decoy” items are linked with user’s private behaviors. We also show how to weaken the assumption made by Li et al. on the information available to the adversary from the whole rating matrix to only the item profile and how to create malicious ratings effectively. We validate the effectiveness of our inference algorithm using two real-world datasets.

A cancelable biometric scheme called correlation-invariant random filtering (CIRF) is known as a promising template protection scheme. This scheme transforms a biometric feature represented as an image via the 2D number theoretic transform (NTT) and random filtering. CIRF has perfect secrecy in that the transformed feature leaks no information about the original feature. However, CIRF cannot be applied to large-scale biometric identification, since the 2D inverse NTT in the matching phase requires high computational time. Furthermore, existing biometric indexing schemes cannot be used in conjunction with template protection schemes to speed up biometric identification, since a biometric index leaks some information about the original feature. In this paper, we propose a novel indexing scheme called “cancelable indexing” to speed up CIRF without losing its security properties. The proposed scheme is based on fast computation of CIRF via low-rank approximation of biometric images and via a minimum spanning tree representation of low-rank matrices in the Fourier domain. We prove that the transformed index leaks no information about the original index and the original biometric feature (i.e., perfect secrecy), and thoroughly discuss the security of the proposed scheme. We also demonstrate that it significantly reduces the one-to-many matching time using a finger-vein dataset that includes six fingers from 505 subjects.

Obfuscation techniques in location-based services (LBSs) have been shown useful to hide the concrete locations of service users, whereas they do not necessarily provide the anonymity. We quantify the anonymity of the location data obfuscated by the planar Laplacian mechanism and that by the optimal geo-indistinguishable mechanism of Bordenabe et al. We empirically show that the latter provides stronger anonymity than the former in the sense that more users in the database satisfy k-anonymity. To formalize and analyze such approximate anonymity we introduce the notion of asymptotic anonymity. Then we show that the location data obfuscated by the optimal geo-indistinguishable mechanism can be anonymized by removing a smaller number of users from the database. Furthermore, we demonstrate that the optimal geo-indistinguishable mechanism has better utility both for users and for data analysts.

Re-identification of mobility traces based on the Markov chain model has been widely studied to understand the risk of location privacy. It is well known that this model can re-identify the traces with very high accuracy when the amount of training data is large. However, the amount of training data can be very small in practice, since a user generally discloses only a small number of locations to the public. A state-of-the-art method in this scenario is to train the Markov chain model (transition matrices) via tensor factorization. The previous work has shown that this method outperforms a random guess even when the amount of training data is very small.In this paper, we propose a succinct model for re-identification that outperforms the state-of-the-art method explained above. Our proposed method does not model a transition pattern (unlike the Markov chain model) but models a probability of being located in each region via matrix factorization. Then it re-identifies traces based on the JS (Jensen-Shannon) divergence between two probability distributions. We evaluate the proposed method using the Gowalla dataset, and demonstrate that the proposed method significantly outperforms the tensor factorization-based Markov chain model. We also demonstrate that the proposed method significantly outperforms a random guess even when only one single location is available per user as training data.

Abstract A number of studies have recently been made on discrete distribution estimation in the local model, in which users obfuscate their personal data (e.g., location, response in a survey) by themselves and a data collector estimates a distribution of the original personal data from the obfuscated data. Unlike the centralized model, in which a trusted database administrator can access all users’ personal data, the local model does not suffer from the risk of data leakage. A representative privacy metric in this model is LDP (Local Differential Privacy), which controls the amount of information leakage by a parameter ∈ called privacy budget. When ∈ is small, a large amount of noise is added to the personal data, and therefore users’ privacy is strongly protected. However, when the number of users ℕ is small (e.g., a small-scale enterprise may not be able to collect large samples) or when most users adopt a small value of ∈, the estimation of the distribution becomes a very challenging task. The goal of this paper is to accurately estimate the distribution in the cases explained above. To achieve this goal, we focus on the EM (Expectation-Maximization) reconstruction method, which is a state-of-the-art statistical inference method, and propose a method to correct its estimation error (i.e., difference between the estimate and the true value) using the theory of Rilstone et al. We prove that the proposed method reduces the MSE (Mean Square Error) under some assumptions.We also evaluate the proposed method using three largescale datasets, two of which contain location data while the other contains census data. The results show that the proposed method significantly outperforms the EM reconstruction method in all of the datasets when ℕ or ∈ is small.

While online services based on machine learning (ML) have been attracting considerable attention in both academic and business, privacy issues are becoming a threat that cannot be ignored. Recently, Fredrikson et al. [USENIX 2014] proposed a new paradigm of model inversion attacks, which allows an adversary to expose the sensitive information of users by using an ML system for an unintended purpose. In particular, the attack reveals the sensitive attribute values of the target user by using their non-sensitive attributes and the output of the ML model. Here, for the attack to succeed, the adversary needs to possess the non-sensitive attribute values of the target user prior to the attack. However, in reality, even if this information (i.e., non-sensitive attributes) is not necessarily information the user regards as sensitive, it may be difficult for the adversary to actually acquire it. In this paper, we propose a general model inversion (GMI) framework to capture the above scenario where knowledge of the non-sensitive attributes is not necessarily provided. Here, our framework also captures the scenario of Fredrikson et al. Notably, we generalize the paradigm of Fredrikson et al. by additionally modeling the amount of auxiliary information the adversary possesses at the time of the attack. Our proposed GMI framework enables a new type of model inversion attack for prediction systems, which can be carried out without knowledge of the non-sensitive attributes. At a high level, we use the paradigm of data poisoning in a novel way and inject malicious data into the set of training data to modify the ML model into a target ML model, which we can attack without having to have knowledge of the non-sensitive attributes. Our new attack enables the inference of sensitive attributes in the user input from only the output of the ML model, even when the non-sensitive attributes of the user are not available to the adversary. Finally, we provide a concrete algorithm of our model inversion attack on prediction systems based on linear regression models, and give a detailed description of how the data poisoning algorithm is constructed.We evaluate the performance of our new model inversion attack without the knowledge of non-sensitive attributes through experiments with actual data sets.

Abstract Location privacy attacks based on a Markov chain model have been widely studied to de-anonymize or de-obfuscate mobility traces. An adversary can perform various kinds of location privacy attacks using a personalized transition matrix, which is trained for each target user. However, the amount of training data available to the adversary can be very small, since many users do not disclose much location information in their daily lives. In addition, many locations can be missing from the training traces, since many users do not disclose their locations continuously but rather sporadically. In this paper, we show that the Markov chain model can be a threat even in this realistic situation. Specifically, we focus on a training phase (i.e. mobility profile building phase) and propose Expectation-Maximization Tensor Factorization (EMTF), which alternates between computing a distribution of missing locations (E-step) and computing personalized transition matrices via tensor factorization (M-step). Since the time complexity of EMTF is exponential in the number of missing locations, we propose two approximate learning methods, one of which uses the Viterbi algorithm while the other uses the Forward Filtering Backward Sampling (FFBS) algorithm. We apply our learning methods to a de-anonymization attack and a localization attack, and evaluate them using three real datasets. The results show that our learning methods significantly outperform a random guess, even when there is only one training trace composed of 10 locations per user, and each location is missing with probability 80% (i.e. even when users hardly disclose two temporally-continuous locations).

Re-identification attacks based on a Markov chain model have been widely studied to understand how anonymized traces are linked to users. This approach is known to enable users to be re-identified with high accuracy when an adversary trains a personalized transition matrix for each target user using a large amount of training data, and when all of the anonymized traces are from the target users. In reality, however, the amount of training data for each target user can be very small, since many users disclose only a small amount of their location information to the public. In addition, many of the anonymized traces are from “non-target” users, whose personalized transition matrices cannot be trained in advance. This paper aims to quantify the risk of re-identification in the realistic situation explained earlier. We first utilize the fact that spatial data can form a group structure, and propose group sparsity tensor factorization to effectively train the personalized transition matrices from a small number of training traces. We second formulate a re-identification attack in an “open” scenario, where many of the anonymized traces are from non-target users. Specifically, we regard this type of attack as a biometric verification (or identification) task, and propose a framework and an algorithm for performing this task using a population transition matrix, which is computed from personalized transition matrices. Our experimental results using three real data sets show that a training method using tensor factorization significantly outperforms the maximum likelihood estimation method, and is further improved by incorporating group sparsity regularization.

Likelihood-ratio based biometric score fusion (LR fusion) has attracted attention since it maximizes accuracy if a log-likelihood ratio (LLR) is accurately estimated. It can also allow a user to select a subset of modalities at the authentication phase by setting LLRs corresponding to missing query samples to 0 (we refer to LR fusion with/without this mode as selective/non-selective LR fusion). However, a recent study proposed a modality selection attack, in which an impostor inputs only query samples whose LLRs are larger than 0 (i.e. takes an optimal strategy), against selective LR fusion, and showed that it degrades overall accuracy even if a genuine user also takes this optimal strategy. In this paper, we investigate the impact of the modality selection attack in more details. Specifically, we study whether the overall accuracy is improved by eliminating “goat” templates, whose LLRs tend to be less than or equal to 0 for genuine users. We investigate, both theoretically and experimentally, whether this restriction of modalities (i.e. elimination of goat templates) increases the KL (Kullback-Leibler) divergence between a genuine score distribution and an impostor's one, which can be compared with password entropy. We first show a negative result that the restriction of modalities hardly increases the KL divergence in selective LR fusion. We then show that it can increase the KL divergence in non-selective LR fusion.

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.

It is known that different users have different degrees of accuracy in biometric authentication, and claimants and enrollees who cause false accepts against many others are referred to as wolves and lambs, respectively. The aim of this paper is to develop a fusion algorithm, which has security against both of the animals while minimizing the number of query samples a genuine claimant has to input. To achieve our aim, we first introduce a taxonomy of wolves and lambs, and propose a minimum log-likelihood ratio-based sequential fusion scheme (MLR scheme). We prove that this scheme keeps wolf attack probability and lamb accept probability, the maximum of the claimant-specific false accept probability (FAP), and the enrollee-specific FAP, less than a desired value if log-likelihood ratios are perfectly estimated, except in the case of adaptive spoofing wolves. We also prove that this scheme is optimal with regard to false reject probability (FRP), and asymptotically optimal with respect to the average number of inputs (ANIs) under some conditions. We further propose an input order decision scheme based on the Kullback-Leibler (KL) divergence, which maximizes the expectation of a genuine log-likelihood ratio, to further reduce ANI of the MLR scheme in the case where the KL divergence differs from one modality to another. The results of the experimental evaluation using a virtual multimodal (one face and eight fingerprints) data set showed the effectiveness of our schemes.

Biometric identification provides a very convenient way to authenticate a user because it does not require the user to claim an identity. However, both the identification error rates and the response time increase almost in proportion to the number of enrollees. A technique which decreases both of them using only scores has the advantage that it can be applied to any kind of biometric system that out- puts scores. In this paper, we propose such a technique by combining score level fusion and distance-based indexing. In order to reduce the retrieval error rate in multibiometric identification, our technique takes a strategy to select the template of the enrollee whose posterior probability of be- ing identical to the claimant is the highest as a next to be matched. The experimental evaluation using the Biosecure DS2 dataset and the CASIA-FingerprintV5 showed that our technique significantly reduced the identification error rates while keeping down or even reducing the number of score calculations, compared to the unimodal biometrics.

We aim at reducing the number of distance computations as much as possible in the inexact indexing schemes which sort the objects according to some promise values. To achieve this aim, we propose a new probability-based indexing scheme which can be applied to any inexact indexing scheme that uses the promise values. Our scheme (1) uses the promise values obtained from any inexact scheme to compute the new probability-based promise values. In order to estimate the new promise values, we (2) use the object-specific parameters in logistic regression and learn the parameters using MAP (Maximum a Posteriori) estimation. We also propose a technique which (3) speeds up learning the parameters using the promise values. We applied our scheme to the standard pivot-based scheme and the permutation-based scheme, and evaluated them using various kinds of datasets from the Metric Space Library. The results showed that our scheme improved the conventional schemes, in all cases.

Speech acoustics varies from speaker to speaker, microphone to microphone, room to room, line to line, etc. Physically speaking, every speech sample is distorted. Socially speaking, however, speech is the easiest communication media for humans. In order to cope with the inevitable distortions, speech engineers have built HMMs with speech data of hundreds or thousands of speakers and the models are called speaker-independent models. But they often need to be adapted to the input speaker or environment and this fact claims that the speaker-independent models are not really speaker-independent. Recently, a novel acoustic representation of speech was proposed, where dimensions of the above distortions can hardly be seen. It discards every acoustic substance of speech and captures only their interrelations to represent speech acoustics structurally. The new representation can be interpreted linguistically as physical implementation of structural phonology and also psychologically as speech Gestalt. In this paper, the first recognition experiment was carried out to investigate the performance of the new representation. The results showed that the new models trained from a single speaker with no normalization can outperform the conventional models trained from 4,130 speakers with CMN.