Secure Computing (SC) Group

In the Secure Computing (SC) group, we conduct research on technologies that allows secure computation over encrypted data without decryption.

For example, consider a scenario where a company wants to analyze their data to extract information, but does not have the technology or the computational resource to do so. In such scenario, the company can outsource such computation to a third-party such as cloud. However, such data contain information that is important to the company as well as personal information of their customers. Therefore, it is insecure to simply outsource the data and computation to a third-party as they may be malicious.
In secure computing, the client can encrypt their data then outsource it to a third-party for analysis and obtain its result, but without disclosing any information. By doing so, the aforementioned risk of disclosing important data to a malicious third-party can be evaded.

The existing cryptographic schemes that enables secure computation still has a challenge in its computation speed. Thus, in SC group, we focus on improving the computation speed of the cryptographic scheme. Devising algorithms and protocols for improving the computation speed is similar to solving a puzzle.

The objective of this project is to improve the computation time by more than 1000 times from aspects of both computer architecture and cryptographic theories. In collaboration with other organizations, we aim to develop an open-source library that is practical.

Click here for details on the project

Research Introduction

再利用性を備えた暗号文上での大小比較演算

Comparing two homomorphically encrypted integers and its subsequent computation typically require bitwise encryption as it supports arbitrary computation. However, bitwise evaluations for arithmetic circuits such as addition and multiplication over integer are expensive. In this study, we proposed a construction without using bitwise encryption scheme, that is compatible with addition and multiplication of polynomial ring over the encrypted comparison result. We also showed that the depth required for our comparison circuit is the lowest among the previous methods.


Relinearize Problem

Ring-LWE-based FHE schemes have a problematic feature: ciphertext size increases with every homomorphic multiplication. Furthermore, the computation cost of homomorphic multiplication linearly increases with increasing input sizes. To overcome this, these FHE schemes support a special operation called relinearization, which can reduce the ciphertext size. Relinearization requires almost the same amount of computation cost as that of the homomorphic multiplication, which takes a few to hundreds of milliseconds. Thus, determining when and the number of times to relinearize a ciphertext in a given arithmetic circuit to evaluate in order to minimize the total computation cost is an important task. This problem has been proved to be an NP-hard problem and is called the relinearize problem. In this study, we design an approximation algorithm to address the relinearize problem. The algorithm runs in polynomial time, and we experimentally confirmed that the output of the algorithm is nearly the same as the optimal solution. We also show that the output is exactly equal to the optimal one in a specific case.


Privacy-Preserving Data Classification

Machine learning classification has wide range of applications. In the big data era, a client may need to classify a large amount of data with many features, resulting in heavy computation at the client. Using a cloud server to outsource such classification tasks, we can reduce this computational burden. By applying FHE to classification, the client can outsource classification tasks to a cloud server without revealing any data. In this work, focus on devising a secure classification protocol in which we preserve the privacy of the classification model, the client’s data, and the result while outsourcing computation to a cloud server. In our scenario, the cloud does not learn anything about the classification model, client’s data or result, and the client learns only the result.


Fully Homomorphic Encryption with Table Lookup for Privacy-Preserving Smart Grid

Smart grid is one of application in smart connected communities (SCC). In order to construct privacy-preserving anomaly detection system on smart grid, we adopt fully homomorphic encryption (FHE) to protect users’ sensitive data. FHE is an encryption scheme that allows a third party to evaluate arbitrary functions using modular arithmetic over encrypted data without decryption. To evaluate any function with FHE, we implemented a protocol replace the calculation to table lookup with FHE. Store the computed function lookup table in cloud server, by searching the input value and select the output value from lookup table with homomorphic encryption, we can decrease the computation cost and run time.


Privacy-Preserving Recommendation for Location-Based Service

Extracting useful information by big data analytics such as artificial intelligence technology is receiving a lot of attention from the world. The world is not fully aware of the importance of security, except for banks and hospitals which need high-security assurance levels. Currently, the location-based services such as google map and tabelog hold huge amount of users’ private information. If such huge amount of data are stored and analyzed without encryption, it could lead to critical social problems in the near future. Therefore, this research is about a new mechanism that enables service providers to provide high-quality recommendations without knowing users’ location information and search contents.


完全準同型暗号を用いた Apriori(頻出アイテムセットマイニング)

あるアイテムリストの中から、頻出して出現するアイテムを暗号化したまま計算する研究。
例えば製薬企業が、大量の種類の薬品群の中から副作用の頻繁におこる薬品を調査したいとき、計算委託はしたいが、薬品ごとの副作用の頻度は企業秘密のため情報流出は避けたいと考える。様々な制約の中で、いかに復号結果の整合性をたもったままプロトコルを構築できるかがポイント。


完全準同型暗号を用いた秘匿ゲノム検索

DNA配列検索は生物学的・医学的知見取得のために、有効である。しかしながら、DNA配列は個人の特徴を反映するだけでなく、個人の識別子(ID)ともなりうる。そのような背景から複数拠点にまたがって存在するDNA配列を活用するためには、暗号化したままのDNA配列検索が望まれる。暗号化したままの検索でどのようにアルゴリズムを構築するかがポイント。

完全準同型暗号を用いたoutsourced private set intersection cardinality

2つの異なる機関が所有するパーソナルデータ集合の共通部分集合の要素数を、クラウド上で暗号化したまま求める研究である。例えば、研究者が病院と航空会社の所有するデータベースを用いて、ある病気の感染地域を特定する際に必要なデータベースの結合処理に応用できる。この処理の過程で、データベースのデータの情報を、クラウドから隠したまま計算処理が可能なプロトコルを構築する。

計算回路上でのbootstrapping配置の最適化

完全準同型暗号の一種であるleveled完全準同型暗号では、一定回数の暗号文同士の演算を行うたびにbootstrappingと呼ばれる時間のかかる処理が必要になります。ここで、事前に計算したい演算が回路の形で表現されているとき、回路上のどのタイミングでbootstrappingを実行するかを適切に選択すると、計算全体でみてbootstrappingの必要回数を減らすことが可能です。複数の制約条件の中で適切な配置を探す必要があります。

メニーコア・共有マシンにおけるスケーラブルなメモリアロケータ

マルチコアシステム上で多数のスレッドが同時に実行される場合(e.g. 完全準同型暗号の演算処理),メモリアロケーションが処理時間のボトルネックになり,スケーラビリティが低下する場合がある.これはマルチスレッドでシステムコールが同時に呼ばれ,ロック競合が発生することに起因する.そこで,そのロック競合の回数を削減し,高速化を実現する.具体的には,システムコールの頻度を下げ,極力ユーザ領域でメモリを管理する方針をとる.