Research Topics

Selected research from our laboratory, featuring recent publications.

View All Publications

Private Discrete Fourier Transform With Applications to Linear Convolution

We study the problem of computing the discrete Fourier transform (DFT) on data secret-shared to two non-colluding cloud servers. While DFT in plaintext is typically computed using floating-point arithmetic, secure computation of DFT requires the use of fixed-point representation. A central challenge in this mode of computation is that fixed-point multiplication causes intermediate values to grow, necessitating secure truncation to ensure that the underlying integer representation remains within the secure computation domain.

While secure truncation typically requires interaction, shares can also be truncated locally when there is a sufficiently large gap between the plaintext input range and the secure computation domain. However, local truncation introduces a probabilistic risk of failure. In this work, we demonstrate a secure DFT protocol based on local truncation and empirically validate the derived truncation-failure bounds. Since local truncation introduces a downward-biased truncation offset, we also evaluate its impact on numerical accuracy by comparing it against two variants: a secure DFT protocol based on interactive truncation and a fixed-point DFT with deterministic rounding.

Our results show that all truncation strategies have similar effects on fixed-point rounding error, as measured by signal-to-noise ratio (SNR) and root-mean-square error (RMSE). Owing to its non-interactive nature, local truncation achieves substantially better performance—up to two orders of magnitude faster in our evaluation of the online phase under the client-aided setup—due to minimal communication.

Extending our DFT protocol, we construct an inverse discrete Fourier transform (IDFT) protocol and leverage these constructions to compose a secure linear convolution protocol for fixed-point arithmetic. Our results show that the DFT-based protocol scales efficiently for large input sizes compared with direct and matrix-based baselines, owing to its superior asymptotic complexity, and is an order of magnitude faster in our online evaluation. We further demonstrate the practical usability of our protocol by applying it to an image-denoising task.

Multidimensional Evaluation of LLM-Generated MPC Programs

Large language models can generate programs that compile and pass functional tests, but these outcomes are insufficient for evaluating code in secure multi-party computation (MPC). MPC programs must also follow the target interface’s programming constraints, implement the requested algorithm, and satisfy the stated secure-operation efficiency criteria.

Using NLMPC, a staged code-generation framework, we conduct an empirical study of 3,600 C++ programs generated by three LLMs for three algorithms under four generation settings that vary API instructions, explicit programming constraints, and iterative repair. We evaluate each program along four dimensions: functional correctness, MPC conformance, algorithmic adherence, and MPC efficiency.

Although 59.2% of the generated programs passed the functional correctness tests, only 31.0% satisfied all four criteria. Functional testing alone did not establish conformance, adherence to the requested algorithm, or compliance with the stated efficiency criteria. Adding MPC-specific constraints revealed trade-offs: aggregate functional correctness and MPC conformance increased, while algorithmic adherence decreased. Validation-guided repair had a higher observed overall pass rate than single-pass generation, but this improvement was not statistically significant after correction. Its recorded token use, including LLM-validator calls, was 1.77×–3.19× that of single-pass generation. These findings show that passing functional tests does not establish the overall quality of LLM-generated MPC code, and that additional constraints and repair do not necessarily improve all evaluation dimensions. They motivate separate checks for functional behavior, MPC programming constraints, algorithmic invariants, and source-level efficiency, rather than relying on compilation or functional testing alone.

Accurate SPARQL generation via in-context learning and schema-based query construction

Motivation

Integrated analysis across biological databases is becoming increasingly important in life science research, leading many public databases to adopt Semantic Web technologies, also known as knowledge graphs. However, biological data possesses inherently complex and diverse structures, which makes the resulting Resource Description Framework (RDF) schemas intricate and difficult for non-expert users to master, preventing them from translating natural language questions into correct SPARQL queries. Although recent large language model (LLM)-based approaches show potential for automatic SPARQL query generation, they often suffer from structural hallucinations and require large-scale training data to capture schema-specific structures. In this study, we propose a novel framework that avoids hallucinations and requires no training data by combining LLM-based word extraction with a schema-based SPARQL query builder.

Results

The LLM extracts variables and parameters from the user’s question based on a predefined schema, and the query builder generates a syntactically correct SPARQL query accordingly. By providing a predefined schema in prompts, our method eliminates the need for training data. Experimental results on UniProt, Rhea, and Bgee demonstrate that our method outperforms baseline LLM-based methods using fine-tuning and prompt-tuning in terms of the similarity between search results obtained from generated and expert-written queries. Furthermore, we developed a proof-of-concept chatbot system that enables users to query RDF databases via natural language input, demonstrating the practical utility of our approach in improving access to biological data resources.

Availability and implementation

Experimental environment: https://github.com/scott2121/sparql_query_generator (DOI: https://doi.org/10.5281/zenodo.18539213). Chatbot: https://github.com/scott2121/sparql_query_chatbot (DOI: https://doi.org/10.5281/zenodo.18539225).

RingOA: Fast Oblivious Access for Large-Scale Privacy-Preserving Structured Data Analysis

Many privacy-preserving data analysis tasks based on multi-party computation require oblivious retrieval of data elements for downstream use. As database sizes grow, this retrieval step becomes a dominant bottleneck, highlighting the need for more efficient oblivious access (OA) primitives that retrieve a database entry without revealing the accessed position.

A common approach uses distributed point functions (DPFs), which reduce communication but still incur local computation that scales linearly with the database size. Early termination (ET) optimization reduces local computation, but applying it yields only Boolean shares that require costly conversion for arithmetic use. This incompatibility between ET and arithmetic outputs makes it difficult for OA to scale efficiently on large databases.

We introduce RingOA, the first three-party OA protocol that supports ET while directly producing arithmetic shares. Our method eliminates the need for share conversion and preserves the computational benefits of ET. RingOA achieves a 13.1–15.7× improvement in runtime on databases exceeding one billion entries compared to a state-of-the-art OA protocol.

Building on RingOA, we construct an oblivious rank query, a core primitive underlying many structured-data analyses. We develop two practical applications: a fully oblivious full-text search protocol for pattern matching over secret-shared string datasets, and a fully oblivious range-search protocol supporting statistical queries over secret-shared numerical sequences. Experiments on real large-scale genomic datasets show that these applications achieve practical performance, demonstrating the utility of our OA protocol and its applications.

Enhancing Privacy Protection for Human Genome Synthesis Using Gradient Clipping

Advances in high-throughput sequencing have produced large-scale human genome datasets, but sharing these datasets raises privacy issues. To tackle the problem, the use of generative models for synthesizing artificial human genome sequences has recently been examined. These synthetic datasets can potentially replace real datasets if the models can accurately capture the distribution of real genome sequences while protecting the privacy of the training samples.

In this study, we enhanced a GAN-based generative model with gradient clipping to improve privacy protection while maintaining its utility. By using the 1000 Genomes Project dataset, we demonstrated that our model preserves the characteristics of the real data as effectively as existing methods. This was confirmed through PCA, allele-frequency association, and linkage disequilibrium analyses. Furthermore, the accuracy of genotype imputation using our synthetic datasets was similar to the baseline, while significantly reducing the risk of membership inference attacks.

Secure Full-Text Search Using Function Secret Sharing

Secure full-text search enables searching for a string within a collection of documents while maintaining privacy. Despite recent studies on secure full-text search having achieved efficient round complexity, searches on large-scale databases remain impractical due to the significant communication overhead.

Function Secret Sharing (FSS) is a recent paradigm that enables efficient secure two-party computations (2PC) in the preprocessing model with low communication overhead. In this study, we developed FssFMI, a communication-efficient full-text search protocol based on FSS.

Compared to the state-of-the-art protocol, which requires $O(\ell N)$ communication at the beginning of the online phase where ℓ is the query length and 𝑁 is the database length, our protocol requires only $O(\ell)$ communication size while maintaining $O(\ell)$ communication round complexity. The low communication overhead of FssFMI is achieved by evaluating functions for a full-text search using an FSS-based 2PC protocol, whereas the previous study computes the functions by referencing a precomputed lookup table based on the use of a large amount of correlated randomness.

The $O(\ell N)$ local computation required in FssFMI is the performance bottleneck, but its parallel-friendly nature easily scales to a large database. Our experimental results demonstrate that in a WAN environment, our protocol can search a database larger than 130 million letters for a query of length 16 in only 55 seconds using a single CPU core, with an online communication size of only 0.49 KB. Compared to the latest method, our protocol reduces communication overhead by more than seven orders of magnitude and achieves search speeds that are more than two orders of magnitude faster.

Efficient privacy preserving range query using segment tree

The range query is a problem to compute a function on a subset of a given data and is used in various real-world setting such that the user inputs a range, and the server computes the function on the range. For many cases using a sensitive data such as a location data, privacy protection is necessary for both query and data.

In this study, we propose a secure range query search protocol based on 2-out-of-2 secret sharing. The key idea of our protocol is to generate the input data’s segment tree, which enables the search in $O(\log N)$ time and deploy the encrypted tree on the server. By using the encrypted tree, our method enables computing a range query in $O(\log N)$ time, communication size, and round of communication after the input of query.

We implemented our protocol and a baseline protocol and compared their performances on two network environments. We observed that the search time of our method after the query input is two orders of magnitude faster than the baseline method when the database length is $10^4$, and the time, the communication size, and the round of communication of our method are well concordant with theoretical complexities.

Efficient Colored de Bruijn Graph for Indexing Reads

The colored de Bruijn graph is a variation of the de Bruijn graph that has recently been utilized for indexing sequencing reads. Although state-of-the-art methods have achieved small index sizes, they produce many read-incoherent paths that tend to cover the same regions in the source genome sequence.

To solve this problem, we propose an accurate coloring method that can reduce the generation of read-incoherent paths by utilizing different colors for a single read depending on the position in the read, which reduces ambiguous coloring in cases where a node has two successors, and both of the successors have the same color. To avoid having to memorize the order of the colors, we utilize a hash function to generate and reproduce the series of colors from the initial color and then apply a Bloom filter for storing the colors to reduce the index size.

Experimental results using simulated data and real data demonstrate that our method reduces the occurrence of read-incoherent paths from 149,556 to only 2 and 5596 to 0 respectively. Moreover, the depths of coverage for the reconstructed reads are equal to those for the input reads for the simulated data, whereas the previous method decreases the depth of coverage at many positions in the source genome.

Our method achieves quite a high accuracy with a comparable construction time, peak memory size, and index size to the previous method.