Secure Computing (SC)

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

Privacy-Preserving Query Response System

In this research, we are working on constructing the privacy-preserving query response system combining homomorphic encryption and differential privacy. Our proposed system protects data owned by Data Providers against both Cloud Servers and Data Analyst by applying differential privacy over ciphertext data using homomorphic operations. In addition, by decrypting differentially private ciphertext data and constructing Differentially Private Database represented in plaintext in advance, our proposed system speeds up the response time to Data Analyst’s queries.

DAMCREM (Dynamic Allocation Method of Computation REsource to Macro-Task)

This is a method named DAMCREM whose goal is decreasing latency of jobs for FHE application over Client-Server model. In DAMCREM, an application is made of macro-tasks which consists of one or more homomorphic operations. DAMCREM aims decreasing latency of jobs by deciding execution order and the number of allocated threads for each macro-task. Detail algorithm of DAMCREM is that application is made of macro-tasks based on types of homomorphic operation. After that, each priority of the number of allocated threads and candidates for each macro-task is made based on measured execution time of each macro-task and each number of threads in advance. During executing the application, DAMCREM schedules execution order of waiting macro-tasks, then decide the number of allocated threads from the candidates for each of the macro-tasks. After that DAMCREM executes the macro-tasks. Previous methods allocates the fix number of threads to each homomorphic operation. Therefore, latency of jobs depends on load of the computation server. DAMCREM decides the number of allocated threads based on the load of the computation server. Thus, DAMCREM can keep low latency of jobs for several load of the computation server.

Large / small comparison operation on ciphertext with reusability

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.

Aprili using fully homomorphic encryption (frequent item set mining)

A study that calculates frequently occurring items from a certain item list while keeping them encrypted.
For example, when a pharmaceutical company wants to investigate drugs with frequent side effects from a large number of drug groups, it wants to outsource the calculation, but because the frequency of side effects for each drug is a company secret, it wants to avoid information leakage. The point is how to build a protocol while maintaining the consistency of the decryption result within various restrictions.

Confidential genome search using fully homomorphic encryption

DNA sequence retrieval is effective for obtaining biological and medical knowledge. However, DNA sequences can not only reflect an individual’s characteristics, but can also be an individual’s identifier (ID). Against this background, in order to utilize DNA sequences that exist across multiple sites, it is desirable to search for DNA sequences that remain encrypted. The point is how to build the algorithm in the encrypted search.

Outsourced private set intersection cardinality using fully homomorphic encryption

This is a study to find the number of elements of the intersection of personal data sets owned by two different institutions while being encrypted on the cloud. For example, researchers can use databases owned by hospitals and airlines to combine databases needed to identify areas infected with a disease. In the process of this processing, a protocol that can perform calculation processing while hiding the data information in the database from the cloud is constructed.

Optimization of bootstrapping placement on the compute circuit

Leveled homomorphic encryption, which is a type of fully homomorphic encryption, requires a time-consuming process called bootstrapping each time a certain number of operations between ciphertexts are performed. Here, when the operation you want to calculate in advance is expressed in the form of a circuit, you can reduce the number of times bootstrapping is required for the entire calculation by properly selecting when to execute bootstrapping on the circuit. You need to find the right placement within multiple constraints.

Scalable memory allocator on manycore / shared machines

When a large number of threads are executed simultaneously on a multi-core system (eg fully homomorphic encryption processing), memory allocation may become a bottleneck in processing time and reduce scalability. This is because system calls are called at the same time in multithreading and lock contention occurs. Therefore, the number of lock conflicts is reduced and the speed is increased. Specifically, the policy is to reduce the frequency of system calls and manage memory in the user area as much as possible.