TMTakao Murakami

Takao Murakami

*This is an algorithmically generated author record based on publicly available information.

Takao Murakami has a total of 20 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data

    by Takao Murakami, Yuichi Sei, Reo Eriguchi

    Shuffle DP (Differential Privacy) protocols provide high accuracy and privacy by introducing a shuffler who randomly shuffles data in a distributed system. However, most shuffle DP protocols are vulnerable to two attacks: collusion attacks by the data collector and users and data poisoning attacks. A recent study addresses this issue by introducing an augmented shuffle DP protocol, where users do not add noise and the shuffler performs random sampling and dummy data addition. However, it focuses on frequency estimation over categorical data with a small domain and cannot be applied to a large domain due to prohibitively high communication and computational costs. In this paper, we fill this gap by introducing a novel augmented shuffle DP protocol called the FME (Filtering-with-Multiple-Encryption) protocol. Our FME protocol uses a hash function to filter out unpopular items and then accurately calculates frequencies for popular items. To perform this within one round of interaction between users and the shuffler, our protocol carefully communicates within a system using multiple encryption. We also apply our FME protocol to more advanced KV (Key-Value) statistics estimation with an additional technique to reduce bias. For both categorical and KV data, we prove that our protocol provides computational DP, high robustness to the above two attacks, accuracy, and efficiency. We show the effectiveness of our proposals through comparisons with twelve existing protocols.

  • Open Access

    Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy

    by Takao Murakami, Yuichi Sei, Reo Eriguchi

    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 epsilon is small. Second, the actual value of epsilon 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 epsilon-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.

  • Open Access

    CARGO: Crypto-Assisted Differentially Private Triangle Counting without Trusted Servers

    by Shang Liu, Yang Cao, Takao Murakami, Jinfei Liu, Masatoshi Yoshikawa

    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.

  • Open Access

    Two-Dimensional Dynamic Fusion for Continuous Authentication

    by Nuttapong Attrapadung, Goichiro Hanaoka, Haochen M. Kotoi-Xie, Takahiro Matsuda, Takumi Moriyama, Takao Murakami, Hidenori Nakamura, Jacob C. N. Schuldt, Masaaki Tokuyama, Jing Zhang

    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.

  • Open Access

    Synthesizing differentially private location traces including co-locations

    by Jun Narita, Takao Murakami, Hideitsu Hino, Masakatsu Nishigaki, Tetsushi Ohki

    Privacy-preserving location synthesizers have been widely studied to perform private geo-data analysis. They have also been used for generating datasets for research or competitions. However, existing location synthesizers do not take into account the friendship information of users. Because friends tend to visit the same place at the same time in practice, a location synthesizer should consider such co-locations of friends to generate a more realistic dataset. In this paper, we propose a novel location synthesizer that generates location traces including co-locations of friends. Our location synthesizer models the information about the co-locations with two parameters:friendship probabilityandco-location count matrix. Our synthesizer generates a synthetic graph based on the friendship probability and then generates synthetic co-locations using the synthetic graph and the co-location count matrix. The two parameters in our synthesizer provide strong privacy guarantees—the friendship probability provides node differential privacy (DP) and the co-location count matrix provides user-level DP. We evaluate our synthesizer using two real datasets. Our experimental results show that our synthesizer preserves co-locations and other statistical features while providing DP with reasonable privacy budgets, e.g., 0.2-node DP and 2-user-level DP.