Koki Hamada

Koki Hamada

Auto-generated profile, based on publicly available information

Koki Hamada

NTT Social Informatics Laboratories

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2023 in Proceedings on Privacy Enhancing Technologies
Verified
Journal Article
Open access
PDF file
KHKoki Hamada
Koki Hamada
DIDai Ikarashi
Dai Ikarashi
RKRyo Kikuchi
Ryo Kikuchi
KCKoji Chida
Koji Chida
We propose a secure multi-party computation (MPC) protocol that constructs a secret-shared decision tree for a given secret-shared dataset. The previous MPC-based decision tree training protocol (Abspoel et al. 2021) requires $O(2^hmn log n)$ comparisons, being exponential in the tree height $h$ and with $n$ and $m$ being the number of rows and that of attributes in the dataset, respectively. The cause of the exponential number of comparisons in $h$ is that the decision tree training algorithm is based on the divide-and-conquer paradigm, where rows are padded after each split in order to hide the number of rows in the dataset. We resolve this issue via secure data structure that enables us to compute an aggregate value for every group while hiding the grouping information. By using this data structure, we can train a decision tree without padding to rows while hiding the size of the intermediate data. We specifically describes a decision tree training protocol that requires only $O(hmn log n)$ comparisons when the input attributes are continuous and the output attribute is binary. Note that the order is now linear in the tree height $h$. To demonstrate the practicality of our protocol, we implement it in an MPC framework based on a three-party secret sharing scheme. Our implementation results show that our protocol trains a decision tree with a height of 4 in 404 seconds for a dataset of $2^{20}$ rows and 11 attributes.

29 January 2021 in Proceedings on Privacy Enhancing Technologies
Verified
Journal Article
Open access
TMTakao Murakami
Takao Murakami
KHKoki Hamada
Koki Hamada
YKYusuke Kawamoto
Yusuke Kawamoto
THTakuma Hatano
Takuma Hatano
Sciendo provides publishing services and solutions to academic and professional organizations and individual authors. We publish journals, books, conference proceedings and a variety of other publications.

10 July 2023
Verified
Conference Paper
Open access
KCKoji Chida
Koji Chida
KHKoki Hamada
Koki Hamada
AIAtsunori Ichikawa
Atsunori Ichikawa
MKMasanobu Kii
Masanobu Kii
JTJunichi Tomida
Junichi Tomida
Private join and compute (PJC) is a paradigm where two parties owing their private database securely join their databases and compute a function over the combined database. Inner product PJC, introduced by Lepoint et al. (Asiacrypt’21), is a class of PJC that has a wide range of applications such as secure analysis of advertising campaigns. In this computation, two parties, each of which has a set of identifier-value pairs, compute the inner product of the values after the (inner) join of their databases with respect to the identifiers. They proposed inner product PJC protocols that are specialized for the unbalanced setting where the input sizes of both parties are significantly different and not suitable for the balanced setting where the sizes of two inputs are relatively close. We propose an inner product PJC protocol that is much more efficient than that by Lepoint et al. for balanced inputs in the setting where both parties are allowed to learn the intersection size additionally. Our protocol can be seen as an extension of the private intersection-sum protocol based on the decisional Diffie-Hellman assumption by Ion et al. (EuroS&P’20) and is especially communication-efficient as the private intersection-sum protocol. In the case where both input sizes are 216, the communication cost of our inner-product PJC protocol is 46 × less than that of the inner product PJC protocol by Lepoint et al.

1 August 2014
Verified
Conference Paper
Closed access
TMToru Mano
Toru Mano
TITakeru Inoue
Takeru Inoue
DIDai Ikarashi
Dai Ikarashi
KHKoki Hamada
Koki Hamada
KMKimihiro Mizutani
Kimihiro Mizutani
OAOsamu Akashi
Osamu Akashi
Building optimal virtual networks across multiple domains is an essential technology to offer flexible network services. However, existing research is founded on an unrealistic assumption; providers will share their private information including resource costs. Providers, as is well known, never actually do that to remain competitive. Technically, secure multiparty computation, which is a computational technique based on the cryptography, can be used to secure optimization, but it is too time-consuming. This paper presents a novel method to optimize virtual networks built over multiple domains, with great efficiency but without revealing any private information. Our method employs secure multi-party computation but only for masking sensitive values; it can optimize virtual networks under limited information without any time-consuming technique. It is solidly based on the theory of optimality, and is assured of finding reasonably optimal solutions. Experiments show that our method is fast and optimal in practice even concealing private information; it finds nearly optimal solutions in just a few minutes for large virtual networks with tens of nodes. This is the first work that can be implemented in practice for building optimal virtual networks across multiple domains.

30 May 2019
Verified
Book Chapter
Closed access
PDF file
AIAtsunori Ichikawa
Atsunori Ichikawa
WOWakaha Ogata
Wakaha Ogata
KHKoki Hamada
Koki Hamada
RKRyo Kikuchi
Ryo Kikuchi

15 May 2021 in Algorithmica
Verified
Journal Article
Open access
PDF file
KHKoki Hamada
Koki Hamada
SMShuichi Miyazaki
Shuichi Miyazaki
KOKazuya Okamoto
Kazuya Okamoto
In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an $$O(n^{2})$$ O ( n 2 ) -time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomial time if the length of preference lists of one side is bounded by one (but that of the other side is unbounded).