You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


Background {#Sec1}
==========

The advent of next generation sequencing and the progressive reduction of costs in sequencing processes result in an increasing amount of available genomic data, which is essential for better modeling the relation between genotypic traits, predisposition to diseases, response to treatments, effect of drugs, and, in general, for achieving more accurate models that enable personalized and precision medicine. While machine learning computations on large scale genomic data present obvious outsourcing needs and can benefit from Cloud services, the high sensitivity of genomic data and the impossibility of properly anonymizing it \[[@CR1], [@CR2]\] call for effective protection methods that enable accurate and efficient computation without leaking information about the individual genomic sequences to untrusted cloud service providers. In order to become feasible and usable for the purpose of personalized medicine, these protection mechanisms must optimize the trade-off between the accuracy of the results, the efficiency of the computation, and the security level.

In this context, the iDASH Privacy and Security Workshop has joined together experts on privacy enhancing techniques, applied cryptography and secure computation to design and implement secure and privacy-preserving solutions to fundamental genomics and bioinformatics problems. iDASH has pushed the state of the art on practical secure computation by organizing a world-wide competition to evaluate the most advanced techniques in the field. In particular, in its 2017 and 2018 editions, iDASH featured a track focused on training logistic regression models on encrypted genomic datasets, by relying on Homomorphic Encryption (HE), which enables certain operations (additions and/or multiplications) to be performed on encrypted ciphertexts without the need to decrypt them first.

Linear and logistic regressions are one of the most common and versatile machine learning tools used in genomic studies. These are the core of Genome Wide-Association Studies (GWAS), and its privacy-preserving implementation represents a first step towards effective and efficient outsourced machine learning on genomic data.

During the last years, there have been numerous approaches to implement these operations securely on medical data; these involve, on the one hand, (a) distributed settings where two or more parties collectively compute a function such as a linear or logistic regression, by applying technologies such as garbled circuits \[[@CR3]\], in settings limited to two parties, or secret sharing and multiparty computation \[[@CR4]\], through interactive protocols; these solutions require non-colluding computing parties and heavily rely on communication between them; on the other hand, (b) outsourced scenarios move the bulk of the computation to an untrusted third party in a non-interactive setting, either relying on trusted hardware such as Intel SGX \[[@CR5]--[@CR8]\], therefore requiring some degree of trust on the hardware manufacturer, or homomorphic encryption \[[@CR9]--[@CR14]\]. The latter does not need any assumption on the hardware, as it is solely based on the cryptographic guarantees of the used cryptosystems, so it can be seen as the most promising approach for outsourcing medical computations.

In 2016, Aono et al. \[[@CR9]\] proposed a solution for training a logistic regression based on additive homomorphic encryption, which requires the client to precompute some intermediate values in order to account for the limited range of operations (additions) supported under encryption. Afterwards, most of the finalists of the HE track in iDASH 2017 leveraged input packing and somewhat homomorphic cryptosystems (SHE), enabling both encrypted additions and a limited number of encrypted products, to implement the basic logistic regression block; i.e., a Gradient descent algorithm with an approximated Sigmoid function on an encrypted matrix of input data; the sought output is the vector of regression coefficients. Bonte et al. \[[@CR12]\] implemented one iteration of a simplified fixed Hessian method with the Fan-Vercauteren (FV) SHE cryptosystem; Kim et al. \[[@CR11]\] employed a Nesterov's accelerated Gradient descent algorithm with the *HEAAN* SHE cryptosystem, which supports homomorphic rescaling and approximate arithmetic; Chen et al. \[[@CR13]\] implemented 1-bit Gradient descent with a modified FV cryptosystem featuring rescaling and bootstrapping, but the used bootstrapping introduces a notable performance penalty. In 2018, in parallel with our work, Crawford et al. \[[@CR10]\] introduced a fully homomorphic encryption (FHE)-based method for the same problem that relies on the BGV cryptosystem, and requires to solve a linear system of equations in the client after decryption; despite the many optimizations used in the work, the bootstrapping takes 75% of the computation time, and this is still notably higher than the previous SHE-based solutions.

The HE track in iDASH 2018 has evolved in complexity, targeting a more advanced semi-parallel logistic regression algorithm that outputs the p-values of the trained regression estimates. In this paper, we propose a solution to semi-parallel logistic regression on encrypted genomic data based on fully homomorphic encryption, that leverages on a novel framework, Chimera \[[@CR15]\], to (a) seamlessly switch between different Ring-LWE-based ciphertext forms, therefore combining the advantages of each of the existing Ring-LWE-based cryptosystems to perform each of the steps of the process in a more efficient way, and (b) is generic, in such a way that it can cope with arbitrary input sizes (number of covariates, number of records, and number of genomic variants), and (c) features two configurations depending on the sought trade-off between accuracy and confidentiality.

Methods {#Sec2}
=======

**Notation**

We denote by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}$\end{document}$ the real Torus $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {R}/\mathbb {Z}$\end{document}$, the set of real numbers modulo 1. We denote by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {Z}_{N}[\!X]=\mathbb {Z}[X]/(X^{N}+1)$\end{document}$ the ring of polynomials with integer coefficients modulo *X*^*N*^+1. Respectively, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {R}_{N}[\!X]=\mathbb {R}[\!X]/(X^{N}+1)$\end{document}$ is the ring of real polynomials modulo *X*^*N*^+1. We denote the $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {Z}_{N}[\!X]$\end{document}$-module $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[\!X]= \mathbb {R}_{N}[\!X] / \mathbb {Z}_{N}[\!X] $\end{document}$ (a.k.a $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {R}[\!X] \bmod X^{N}+1 \bmod 1$\end{document}$). We denote also $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {B}_{N}[\!X]$\end{document}$ as the subset of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {Z}_{N}[\!X]$\end{document}$ with binary coefficients.

We provide now a brief description of the two Ring-LWE homomorphic schemes used in this work, namely *TFHE* \[[@CR16], [@CR17]\] and *HEAAN* \[[@CR18]\] (a.k.a CKKS), both enabling error-tolerant decryption functions, and hence approximated arithmetic, and we present then the Chimera framework \[[@CR15]\] unifying both.

*TFHE* (Torus Fully Homomorphic Encryption) \[[@CR16]\] defines messages and ciphertexts over the torus modulo 1 ($\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}=\mathbb {R}/\mathbb {Z})$\end{document}$, and keeps track of the noise standard deviation *α*≪1, a dynamic parameter that changes after each operation. Therefore, plaintexts have *ℓ*=− log2(*α*) fractional bits of precision. *TFHE* can represent three plaintext spaces, with various morphisms or actions to switch between them: *TLWE* encodes individual (continuous) messages over the torus $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}$\end{document}$;*TRLWE* encodes (continuous) messages over $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {R}[X] \bmod (X^{N} + 1) \bmod 1$\end{document}$, which can be viewed as the packing of *N* individual coefficients;*TRGSW* encodes integer polynomials in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {Z}_{N}[X]$\end{document}$ with bounded norm.

We describe below the main algorithms that are used for the *TFHE* with *TRLWE* encryption scheme, considering a security parameter *λ*=128, and a minimal noise standard deviation *α*; these parameters implicitly define a minimal key size *N*≈ max(256,32*α*) (see Section 6 of \[[@CR17]\]). KeyGen/Phase: A uniformly random binary key $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$s\in \mathbb {B}_{N}[X]$\end{document}$, this implicitly defines the secret *phase* function $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\varphi : \mathbb {T}_{N}[\!X]^{2} \to \mathbb {T}_{N}[\!X], (a,b)\mapsto (b-sa)$\end{document}$. Encrypt (*μ*,**s**,*α*): Pick a uniformly random $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$a\in \mathbb {T}_{N}[\!X]$\end{document}$, and a small Gaussian error *e* from $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[\!X]$\end{document}$ with standard deviation *α*, and return (*a*,*s*.*a*+*μ*+*e*). DecryptApprox(*c*,*s*): Return *φ*~*s*~(*c*), which is close to the actual message. The error (the distance between the plaintext and the output of DecryptApprox(*c*,*s*)) has the same order of magnitude as *α*. Decrypt($\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$c, s, \mathcal {M}$\end{document}$): Round *φ*~*s*~(*c*) to the nearest point in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathcal {M}$\end{document}$.

Arithmetic operations supported by *TFHE* are the addition and the multiplication of plaintext messages. We differentiate 2 types of multiplication: (i) internal -- multiply 2 *TRLWE* samples and (ii) external -- multiply a *TRGSW* and a *TRLWE* sample. The external multiplication is faster and the noise increase is smaller. The public key switch operation allows to evaluate a linear function with integer coefficients over *TLWE* or *TRLWE* input samples. A private key switch allows to hide the integer coefficients. The sample extract operation allows to obtain a *TLWE* sample that encodes the *i*-th polynomial coefficient of an input *TRLWE* sample with at most the same noise variance or amplitude.

Bootstrapping traditionally evaluates the rounding function (homomorphic decryption) on the encrypted plaintext, in order to refresh a noisy ciphertext $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathfrak {c}$\end{document}$. The *gate bootstrapping* in *TFHE* can refresh a noisy *TLWE* ciphertext $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathfrak {c}$\end{document}$, but it can be more general, by also changing the plaintext space; i.e., the gate bootstrapping algorithm allows to evaluate any pointwise defined negacyclic function $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$f:\mathbb {T} \rightarrow \mathbb {T}$\end{document}$ to the phase of a *TLWE* sample.

Finally, it is worth noting that any *TLWE*, *TRLWE*, *TRGSW* ciphertext, bootstrapping key or keyswitching key given at a given precision, can always be rounded and truncated to match the current (lower) precision *α*. Whenever *α* varies (e.g. increases after each multiplication, or decreases after a bootstrapping), we always use the last keyswitching and bootstrapping operation to switch to a new encryption key whose entropy is as close as possible to the lower bound *N*≈ max(256,32*α*) from the security estimates.

*HEAAN* \[[@CR18]\] also supports approximate arithmetic; its message space is the set of small-norm polynomials with coefficients in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathcal {R}_{q}$\end{document}$. The least significant bits of a message *μ* are considered as noise, and only its most significant bits are required to have a correct decryption. A *HEAAN* ciphertext is a Ring-LWE tuple $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$(a,b)\in \mathcal {R}^{2}_{q}$\end{document}$, where *a* is uniformly random in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathcal {R}_{q}$\end{document}$, and *b* is close to *a*·*s*+*μ*, up to a Gaussian error of small amplitude. Plaintexts and ciphertexts share the same space, and homomorphic multiplication of two ciphertexts involves a relinearization with a keyswitch operation, followed by a modulus-rescaling operation that rescales both plaintext and ciphertext; this helps managing not only the noise growth but also the plaintext growth, keeping a constant upper bound on the message.

Chimera: unifying *HEAAN* and *TFHE* {#Sec4}
------------------------------------

As shown in \[[@CR15]\], both *HEAAN* and *TFHE* use the same ciphertext space (up to rescaling by a factor *q*), and the *TFHE* notion of phase can be extended to *HEAAN*. The Chimera framework interprets the plaintext spaces as subsets of the same module $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[X]$\end{document}$, and uses the distance function on the torus to quantify the transformation error; then, both schemes use the same ciphertext space $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[X]^{2}$\end{document}$, the same key space $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {B}_{N}[X]$\end{document}$ and the same phase function *φ*~*s*~(*a*,*b*)=*b*−*s*·*a*. In this framework, decryption finds two definitions: the first one, common to *HEAAN* and *TFHE*, considers that the phase is always close (within distance \<*α*) to the actual message and is a good enough approximation thereof. Then, accumulated errors are not corrected by the cryptosystem (but rather by the numerical stability of the homomorphically evaluated algorithm). The second decryption, unique to *TFHE*, restricts the valid message space to a discrete subset of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[X]$\end{document}$ with a packing radius ≥*α*. Then, the exact message is recovered by rounding the phase to the closest valid message.

In this unified plaintext space $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[X]$\end{document}$, it is important to preserve the notion of *user-side slots*, which corresponds to the way the end-user actually employs the schemes. Following *HEAAN* formulation, homomorphic operations are presented as *N*/2 SIMD (Single Instruction Multiple Data) slots containing complex numbers in fixed-point representation with the same public exponent and the same precision. By interpolating the complex roots of *X*^*N*^+1, the native plaintext can be mapped to small polynomials of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbb {T}_{N}[X]$\end{document}$. Hence, it is possible to represent (pack) a plaintext message either with *slot packing* (enabling component-wise products) or with *coefficient packing* (enabling convolution products), and both representations are related to each-other by a homomorphic linear transform.

Finally, Chimera also preserves the notion of levels common to *TFHE* and *HEAAN*: the level *L*≥0 bounds the ratio between the ciphertext modulus and the native plaintext modulus, and therefore the number of homomorphic operations supported by the ciphertext. Each homomorphic product reduces the level of the resulting ciphertext; when the level 0 is reached, the ciphertext must be bootstrapped to continue operating on it.

Semi-parallel logistic regression and our simplification {#Sec5}
--------------------------------------------------------

The HE track in iDASH 2018 consists in executing a semi-parallel logistic regression \[[@CR19]\] with encrypted phenotypic and genotypic features; the former are represented as a covariate matrix *X* (*k*+1 covariates ×*n* patients), and the latter as a binary SNP matrix *S* (*n* patients ×*m* SNPs). The original method in \[[@CR19]\] is sketched in Algorithm 1; it comprises two parts: first, it builds a logistic regression model using only phenotype features (i.e. covariates matrix *X*) through an iterative process (i.e. gradient descent); afterwards, it updates this model with genotype features (matrix *S*). The outputs of the algorithm are the *p*-values of the estimates after training the model. The obtained acceleration factor (compared to doing individual logistic regressions) comes mainly from the fact that the second part is performed once and includes all genotype features *S*.

In this work we have further simplified the approach proposed in \[[@CR19]\], resulting in Algorithm 2. First, let *E* be the subspan generated by the columns of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$X'=\sqrt {W}X$\end{document}$, *z*^′^ be the vector $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sqrt {W}z$\end{document}$, *z*^′∗^ be the vector $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sqrt {W}z^{*}$\end{document}$, *S*^′^ be the matrix $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sqrt {W}S$\end{document}$, and *S*^′∗^ be the matrix $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sqrt {W}S^{*}$\end{document}$. With this change of variable, Line 7 and 9 result: *z*^′∗^=*z*^′^−*X*^′^(*X*^′*T*^*X*^′^)^−1^*X*^′*T*^*z*^′^*S*^′∗^=*S*^′^−*X*^′^(*X*^′*T*^*X*^′^)^−1^*X*^′*T*^*S*^′^.In other words, *z*^′∗^ and *z*^′∗^ are the orthogonal projection of *z*^′^ and *S*^′^ over *E*^⊥^. Note that by definition, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$z^{\prime }=X'\beta + \sqrt {W}^{-1}(y-p)$\end{document}$. In this sum, the first operand is in *E* by construction, and we verify that the second operand is in *E*^⊥^. Indeed, the dot product $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$X^{\prime T}.\sqrt {W}^{-1}(y-p)=X(y-p)$\end{document}$ is the gradient of the cost function of the logistic regression, and is null at the point of convergence. Therefore, the projection *z*^′∗^ is equal to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sqrt {W}^{-1}(y-p)$\end{document}$, and the numerator of the stat (line 11) simplifies to the FHE-friendly expression: *z*^∗*T*^*WS*^∗^=*z*^′∗*T*^*S*^′∗^=(*y*−*p*)^*T*^.*S*

For the denominator of the stat, we note that for all *j*∈\[1,*m*\], $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}_{j}^{*2}=S_{j}^{*T}WS_{j}^{*}=\left \Vert {S_{j}^{\prime *}}\right \Vert ^{2}$\end{document}$ where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$S_{j}^{\prime *}$\end{document}$ is the *j*-th column of *S*^′∗^. By definition of the orthogonal projection, we therefore have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}_{j}^{*2}=\left \Vert {S_{j}^{\prime }}\right \Vert ^{2}-\left \Vert {\pi _{E}(S_{j}^{\prime })}\right \Vert ^{2}$\end{document}$ where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\pi _{E}(S_{j}^{\prime })$\end{document}$ is the orthogonal projection of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$S_{j}^{\prime }$\end{document}$ on *E*. Namely, if we call *A*=*X*^′*T*^*S*^′^=*X*^*T*^*WS*, then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\left \Vert {\pi _{E}(S_{j}^{\prime })}\right \Vert ^{2}=A_{j}^{T} G^{-1} A_{j}$\end{document}$. Therefore, once we have precomputed *A* and *G*^−1^, line 10 can be simplified as: **s**^∗2^=colsums(*W*·(*S*⊙*S*))−colsums(*A*⊙*G*^−1^*A*), and any other intermediate variable that does not appear in this formula can be removed from the pseudocode. As a bonus, for binary valued matrices *S*, (*S*⊙*S*) is equal to *S*, and due to the geometric interpretation of the logistic regression and the projections, the input matrix *X* can be replaced by any basis of the same vector span without affecting the final result.

The algorithm must also be transformed to use fixed-point data type instead of floating-point, due to the homomorphic encryption libraries we use. Hence, input data must be carefully scaled so that no overflow happens during the execution. We have performed simulations with the optimized algorithm in order to determine the ranges of intermediary variables. Table [1](#Tab1){ref-type="table"} depicts the obtained simulation results. These ranges are used for scaling input data. The inverse sigmoid function applied on the probability vector **p** gives us an input range −1.6...1.8 of the sigmoid function; this input corresponds to elements of vector *X*·*β*^*iters*^. This range is extended to −4...4 (*σ*~*min*~...*σ*~*max*~) to allow a margin of error. By mapping this range to the plaintext space of Torus based homomorphic libraries, the scaling factor $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\frac {1}{16}$\end{document}$ of *X*·*β*^*iters*^ is obtained. Note that only the $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$-\frac {1}{4}\ldots \frac {1}{4}$\end{document}$ part of Torus is used in our computations because of the negacyclic property of functions evaluated by the *TFHE* bootstrapping procedure. Propagating the range of *X*·*β*^*iters*^ backward and forward in Algorithm 2 the scaling factors for other variables (including input data) are obtained. An automatic tool, or semi-automatic, for computing fixed-point range and scale for algorithm variables together with respective mapping to encryption scheme parameters would have been very helpful. We leave this research and development issue for a future work. Table 1Data ranges of intermediary variables in the plaintext Algorithm 2Variableavgstdevminmax**p**0.4408160.09757150.1763970.853487*W*0.2369770.02018710.1250470.25**z**\*-3.330927.36068-30.942631.2008G0.05778460.0953495-0.0119970.236977A0.06219650.301255-0.3173122.236s^∗2^2.442434.110850.11196114.5044r~i~0.2000391.84459-13.72074.36158*p*-value0.3102180.2408300.999163The average, standard deviation, minimum and maximum statistics are shown

FHE algorithm {#Sec6}
-------------

The proposed solution is split into 3 sequentially executed parts, which are implemented using different homomorphic encryption techniques and libraries. As shown in Algorithm 2, our solution features two options, depending on the sought trade-off between confidentiality and accuracy. The first solution outputs both numerator and denominator of the stats, while the second solution outputs only the quotient, which is equivalent to the p-value. We explain in detail each part and the encryptions of input data in the next sub-sections.

### Step1 -- logistic regression {#Sec7}

Algorithm 3 illustrates a more explicit version of the implemented logistic regression algorithm. We have used the *TFHE* library \[[@CR16]\] to homomorphically execute this algorithm.

#### Input data encryption. {#Sec8}

Input covariates matrix *X* and outcome vector *y* are encrypted using different encoding and HE scheme types. Each column of the covariate matrix is encrypted in a *TRGSW* ciphertext. A total of *k* ciphertexts are used for matrix *X*. The outcome vector is encrypted in a single *TRLWE* ciphertext. Besides these encryptions we use additional ones used by the bootstrapping procedure. For the sake of simplicity we omit input data scaling factors, mentioned in previous subsection, from our discourse. In what follows we describe the encoding we use: *j*-th column of matrix *X* is coefficient packed into a polynomial $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$P_{X_{.,j}}(Z) = \sum _{i=0}^{n-1} X_{i,j} \cdot Z^{i}$\end{document}$ and encrypted in a *TRGSW* ciphertext (L1 and L2)vector *y* (scaled by step *α*) is coefficient packed in reverse order into a polynomial $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$P_{y}(Z) = \alpha \cdot \sum _{i=0}^{n-1} y_{n-i-1} \cdot Z^{i}$\end{document}$ and encrypted in a L2 *TRLWE* ciphertexttest polynomials for gate bootstrapping encode sigmoid function (defined over the range \[*σ*~min~,*σ*~max~\] and discretized on *d*=⌊*N*/*k*⌋−1 levels) multiplied by matrix *X* rows and encrypted as L2 *TRLWE* ciphertexts: $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}${TP}_{i}(Z) = \sum _{q=0}^{d} \alpha \cdot \sigma \left (\sigma _{min} + \frac {q}{d}\cdot \left (\sigma _{max}-\sigma _{min}\right) \right) \sum _{j=0}^{k-1} X_{i,j} \cdot Z^{q\cdot k + j - N/2} $\end{document}$

#### *TFHE* implementation. {#Sec9}

Subsequently we explain how each operation in Algorithm 3 is performed using the *TFHE* library.

**Line 2.** Firstly, L2 encryptions of matrix *X* column ($\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$P_{X_{.,j}}$\end{document}$) and outcome vector (*P*~*y*~) are multiplied together (external product). This results in an encryption of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sum _{i=0}^{n-1} \alpha \cdot X_{i,j} \cdot y_{i} \cdot Z^{n-1} + \ldots $\end{document}$. The (*n*−1)-th coefficient of this polynomial is the scalar value *e*~*j*~. The coefficient extraction procedure is used to obtain a L2 *TLWE* encryption of *e*~*j*~.

**Line 3.** This operation is similar to the previous one except that: (i) beforehand plaintext $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\alpha \cdot \sum _{i} \frac {1}{2}\cdot Z^{i}$\end{document}$ (note that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$ \frac {1}{2} \equiv \sigma (0)$\end{document}$) is subtracted from the encryption of *P*~*y*~ and (ii) a key-switching procedure is used to obtain a L1 *TRLWE* encrypting $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\beta ^{(0)}_{j}$\end{document}$ from the L2 *TLWE* sample after the coefficient extraction. A copy of L2 *TLWE* encryption of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\beta ^{(0)}_{j}$\end{document}$ is kept for update performed in algorithm line 14.

**Line 7.** L1 *TRLWE* encryption of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\beta ^{(t-1)}_{j}$\end{document}$ (from previous iteration) and L1 *TRGSW* encryption of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$P_{X_{.,j}}$\end{document}$ are multiplied together for all *j*=0...*k*−1. Encryptions of polynomials $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sum _{i} X_{i,j}\cdot \beta ^{(t-1)}_{j} \cdot Z^{i}$\end{document}$ are obtained. These L1 *TRLWE* ciphertexts are summed-up and an encryption of polynomial $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sum _{i} \sum _{j} X_{i,j}\cdot \beta ^{(t-1)}_{j} \cdot Z^{i} \equiv \sum _{i} u_{i}\cdot Z^{i}$\end{document}$ is obtained. Coefficient extraction and key-switching procedures are used afterwards to obtain *n* individual L0 *TLWE* encryptions of *u*~*i*~, *i*=0...*n*−1. These L0 *TLWE* ciphertexts represent logistic regression algorithm outputs over the last iteration.

**Line 13.** The blind rotate procedure (a fundamental building block of the *TFHE* gate bootstrapping) allows to multiply a polynomial *TP*(*Z*) (called test polynomial) by *Z*^*m*^ where *m* is the message encrypted in a *TLWE* ciphertext. Moreover, the resulting *TRLWE* ciphertext noise (encrypting polynomial *TP*(*Z*)·*Z*^*m*^) is independent of the noise of input *TLWE* ciphertext encrypting *m*.

In this step of algorithm we use the blind rotate procedure *n* times to obtain *TRLWE* encryptions of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\phantom {\dot {i}\!}{TP}_{i} \cdot Z^{u_{i}}$\end{document}$ for *i*=0...*n*−1. Observe that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}${TP}_{i} \cdot Z^{u_{i}} \equiv \sum _{j=0}^{k-1} \alpha \cdot \sigma \left (u_{i}\right)\cdot X_{i,j} \cdot Z^{j} + \ldots $\end{document}$ thanks to the special form of test polynomials *TP*~*i*~. Summing up these ciphertexts (i.e. obtaining $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\sum _{i} {TP}_{i} \cdot Z^{u_{i}}$\end{document}$) and extracting the first *k* coefficients from the result we obtain *k* L2 *TLWE* ciphertexts encrypting *Δ*~*j*~, *j*=0...*k*−1.

**Line 14.** Finally, we update the L2 *TLWE* encryptions of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\beta ^{(t-1)}_{j},~j=0\ldots k-1$\end{document}$, by adding *e*~*j*~ and subtracting *Δ*~*j*~ obtained in previous step.

### Step2 -- incorporate *S* into the regression model {#Sec10}

The second part of the Algorithm 2 consists of large-scale linear algebra computation in order to integrate the matrix *S* in the regression model calculated in the previous phase. We use the following input data encryptions with parameters given in Table [2](#Tab2){ref-type="table"}: *X* is encrypted as (*k*+1)∗*n* individual *TRGSW* samples (level L2), Table 2Encryption parameters, also used to encrypt TRLWE or TRGSW ciphertexts**Step**LevelTypen/N**stdv**Security**Sample size**1L0LWE*n*=6122^−15^≈1284.8 KBL1RLWE*N*=20482^−53^≈12832 KBL2RLWE*N*=81922^−53^≈128128 KB2L0LWE*n*=6122^−15^≫1284.8 KBL1RLWE*N*=40962^−32^≫12832 KBL2RLWE*N*=40962^−48^≫12832 KBL3RLWE*N*=40962^−64^≫12864 KBL4RLWE*N*=40962^−80^≫12864 KBL5RLWE*N*=40962^−105^≈13064 KB3L0RLWE*N*=40963.2/*q* with *q*=232≫12832KBL1RLWE*N*=327683.2/*q* with *q*=2581≈1284.5MB*y* is encrypted in *nTRLWE* samples (level L2),*S* is encrypted as *TRGSW* matrix sample packed in slots by line in level L3.

We describe now the homomorphic evaluation of each step of Algorithm 2.

**Line 2.** We first bootstrap the probability vector to a fixed level, and we use Chimera framework described in \[[@CR15]\] to simultaneously change the key size to support lower noise, convert *TFHE* into *HEAAN* ciphertexts, and evaluate the sigmoid function homomorphically. Although this bootstrapping takes more than 90% of the evaluation time, it has the advantage that the encryption of the database *S* is independent from the previous computations: we can iterate the initial logistic regression loop as many times as it is needed for the model to converge, which is required to support a larger number of features. We use a single coefficient per *TRLWE* ciphertext at this step (no packing).

**Line 3.** The coefficients of *S* are packed row-wise to form a matrix of *n*×(⌈*m*/4096⌉) of *TRGSW* ciphertexts. The external homomorphic product between a single-coefficient *TRLWE* ciphertext and a packed *TRGSW* ciphertext provides 4096 slots of *z*^∗^ at once. For *m*=10643 and *n*=245, we need a total of *n*×3 external products. At this depth, the *TRGSW*- *TRLWE* external product is indeed at least twice as fast as its internal *TRLWE*- *TRLWE* equivalent, whenever one of the operand is a fresh ciphertext. At this step, we support either the coefficient packing or the slot packing, depending on the encoding of the needed output.

**Line 4.** The result is a vector of *nTRLWE* ciphertext, each one holds a single coefficient $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$w_{i}=p_{i}-p_{i}^{2}$\end{document}$, each square uses one *TRLWE* internal product.

**Line 5.** We need the matrix *G* and its inverse to fulfill the algorithm. However, inverting *G* is a relatively large depth operation, so we considered two approaches: (1) we note that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$G=\frac {1}{4}I_{k+1}+\varepsilon $\end{document}$ where the norm of *ε* is very small (unless the input dataset is exceptionnaly biased in one direction). Thus, *G*^−1^ can be approximated with its Taylor series: $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$4(I_{k+1}-\varepsilon +\varepsilon ^{2}-\dots)$\end{document}$. On the iDASH dataset, *G*^−1^=4*I*~*k*+1~ already provides a sufficient approximation. (2) the second approach consists in evaluating the Gaussian elimination loop (or better in this case, the Cholesky factorization) using one *TFHE* bootstrapping everytime a coefficient needs to be inverted. Since *G* is a very small matrix (*k*≪*n*), this step remains very fast even if an individual bootstrapping lasts a few seconds. This bootstrapping uses look-up tables to deal with the non-linearity of the inverses and simultaneously refreshes the noise of ciphertexts to the same level throughout the inversion loop. If the required precision is too large for look-up tables, we can switch to binary gates evaluating the IEEE754 floating-point division circuit. The coefficients of *G*^−1^ are computed as individual *TRLWE* ciphertexts.

**Line 6.** As in Step 3, the coefficients of *X* are stored as individual *TRGSW* ciphertexts, and the coefficients of *S* are packed row-wise (using the same ciphertext as in Step 3). The resulting *k*×*m* matrix is row-packed.

**Line 7.** Since *S* has binary entries, the element-wise product *S*⊙*S* is equal to *S*, so only the element-wise product on the right needs to be computed. If *A* is slot-packed, this hadamard product corresponds to the internal product of *TRLWE*. If *A* is coefficient packed, the squaring is merged to the next non-linear function (here, the logarithm), and handled via the *HEAAN* bootstrapping.

Depending on the choice of packing (coefficients or slots), the final output of the second phase is either (a) *z*^∗^ and *s*^∗2^ packed as slots (which can be decrypted and divided as postprocessing to reveal the t-stat), or (b) *z*^∗^ and *A* coefficient-packed, ready to pass to phase 3.

### Step3 -- stats computation in the logarithmic domain {#Sec11}

The target outcome of the protocol is the vector of p-values of the obtained results. It must be noted that the p-values are a monotonic (but non-polynomial) function of the t-stats $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\frac {\mathbf {z}^{*}_{i}}{{\mathbf {s}^{*}_{i}}^{2}}$\end{document}$, so they both convey the exact same information. Therefore, the computation of the p-values themselves under encryption would produce an unjustified overhead, whereas computing the t-stats and releasing them is optimal in terms of security/efficiency. Consequently, depending on the desired trade-off between accuracy and leakage, it is possible to produce the target p-values by computing the t-stats either (a) in the client-side, after decrypting (and leaking) both numerator and denominator separately, or (b) by performing a third homomorphic step that leaks only the t-stats. For option (a), the second phase outputs the slot-packed version of both numerator and denominator. Here, we detail option (b), for which we leverage on SIMD operations on *HEAAN* ciphertexts, taking as input the coefficient-packed (fully packed) versions of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {z}^{*}_{i}$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}^{*}_{i}$\end{document}$ from phase 2.

#### HEAAN-based implementation {#Sec12}

This phase is focused on the computation of line 8 of Solution 2 in Algorithm 2, which takes as inputs the terms $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {z}^{*}_{i}$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}^{*}_{i}$\end{document}$ as fully-packed level 0 RLWE encryptions. There are two options to compute the t-stats: either approximate the inverse of the denominator and multiply numerator and inverted denominator, or apply a logarithm and avoid further homomorphic products that will further reduce the precision of the results due to the approximate arithmetic used in *HEAAN*. Hence, we have chosen the second approach. This phase applies the following operations:

**1.** As the logarithm computation requires more levels than what the input encryptions can withstand, the first step is key-switching both encryptions $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {z}^{*}_{i}$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}^{*}_{i}$\end{document}$ to an expanded key with higher-degree polynomials (from *N*~0~=4096 to *N*~1~=32768), resulting in (sparsely) coefficient-packed ciphertexts. At this stage, the encryptions are completely exhausted, so a bootstrapping is needed to keep computing on them.

**2.***HEAAN* boostrapping is applied to the expanded ciphers, hence achieving level 1 encryptions. After the bootstrapping, we keep slot-packing, in order to perform the coefficient-wise computation of the squaring and logarithm operations.

**3.** The numerator $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {z}^{*}_{i}$\end{document}$ is still a signed number, so we compute the logarithm of the absolute value by resorting to a least-squares symmetric (even-degree) polynomial approximation of the logarithm. In order to improve on the error and due to the fact that most of the relevant inputs should be far from the vertical asymptote, we use as objective function a smoothed version of the logarithm, defined as $$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document} $$ \texttt{smoothed\_logabs}(x)=\left\{\begin{array}{l}log(|x|),\quad\text{if }{|x|>th}\\ax^{2}+b,\quad\text{otherwise},\end{array}\right. $$ \end{document}$$ where *th*\<1 is a pre-calculated threshold adapted to the dataset features, and *a* and *b* are computed to make the function continuous and differentiable at *x*=*th*. For the implementation, we use a degree-8 polynomial approximation of smoothed_logabs in the plausible range for the numerator values.

**4.** The denominator term $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}^{*}_{i}$\end{document}$ is first squared and centered, in order to arrive at an encryption of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$\mathbf {s}^{2*}_{i}$\end{document}$, and then a least-squares degree-8 polynomial approximation of the smoothed logarithm is applied to the result.

**5.** The numerator is rescaled to the same quantization factor as the denominator, and both are homomorphically subtracted, hence achieving the desired encrypted result $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$stat_{i}=\frac {\mathbf {z^{*}}_{i}}{\sqrt {\mathbf {s^{*}}_{i}^{2}}}$\end{document}$, that can be sent to the client for decryption.

Results {#Sec13}
=======

Implementation details {#Sec14}
----------------------

The three parts of the homomorphic algorithm were implemented as separate applications which are executed one after another. The first application performs the logistic regression part and outputs encryptions of *X*·*β*^(*iters*)^. The second one does the generalization of the previous logistic regression model with genotype data *S*. Finally, the last application computes the quotients on the stats, that can be used to obtain the sought p-values. Besides these applications performing homomorphic computation several helper applications were implemented for generating keys, encrypting input data and decrypting the result. Data exchange (ciphertext data) between application executions is done via the file-system. That is, each application reads input data from files and writes the results to files.

C/C++ programming language was used for implementation. Two open-source HE libraries are employed: (i) *TFHE* library (<https://github.com/tfhe/tfhe>), in particular the torus_generic branch, optimized using AVX and FMA instructions, (ii) *HEAAN* library (<https://github.com/snucrypto/HEAAN>). Besides these two HE libraries, a prototype of the Chimera framework \[[@CR15]\] was coded for the purpose of this project.

Benchmarks and dataset details {#Sec15}
------------------------------

The dataset used for the HE Track of iDASH 2018 has the following features: *m*=10643 SNPs, *n*=245 patients, *k*=3 covariates. The test environment is an Amazon T2 Xlarge VM, with 4 vCPU, 16GB memory, and 200GB of disk space. We have also tested on a m5.24xlarge VM with 96 vCPU machines to verify that the execution scales with the number of CPU without increasing the memory.

Table [3](#Tab3){ref-type="table"} shows the running time and the used memory for our solution, broken down in each of the steps. The size of the input encryptions is 5GB, including the encryption of *X*, *y* and *S*. The size of the output is 640KB including the encryption of the numerator and the denominator. The encryption parameters are given in Table [2](#Tab2){ref-type="table"}. The numerical accuracy is depicted in Fig. [1](#Fig1){ref-type="fig"}, that plots the homomorphic versus plaintext computation of the stat coefficients. Fig. 1**Accuracy** Homomorphic versus plaintext computed stat vectorTable 3Timing and memory results**StepsTiming (4 cores)Timing (96 cores)RAM**KeyGen Solution 15.5 mins2.0 mins4.4 GBKeyGen Solution 26.2 mins2.5 mins14 GBEncryption7.2 mins1.3 mins8.6GBStep 16.5 mins0.5 mins5.6 GBStep 2 Bootstrapping164 mins3.2 mins-Step 2 Total180 mins3.5 mins7.9 GBStep 332 mins10 mins15 GBTotal Cloud run time Solution 1186 mins4 mins7.9 GBTotal Cloud run time Solution 2218 mins14 mins15 GB

Discussion {#Sec16}
==========

The main part of the computation is consumed during the bootstrapping at the beginning of step 2 (more that 90% of the total evaluation time). But this bootstrapping allows us to use different values for *k* and for the number of iterations during the logistic regression phase; hence, it makes the solution much more generic than other approaches (as the depth of our circuit does not depend on the these parameters). Additionally, this is the only bootstrapped solution submitted to the iDASH competition that can be applied for different sets of parameters without re-encrypting the genomic database, making it practical for real-world applications.

One possibility to further improve the running time is to use the HEAAN bootstrapping instead of the several TFHE bootstrappings in Step 2 of the solution.

Conclusions {#Sec17}
===========

The HE Track of iDash 2018 competition succeed the improvement of the actual state of art for privacy-preserving computation on genomic data. In this work we proposed fully homomorphic based solution, one of the most generic solution, that can be used with different sets of parameters. This is the first step towards the more general feature selection problem across large encrypted databases.

**Publisher's Note**

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors would like to show gratitude to Malika Izabachène and Rasoul Akhavan Mahdavi for their comments on an earlier stage of this work.

About this supplement {#d30e5177}
=====================

This article has been published as part of *BMC Medical Genomics Volume 13 Supplement 7, 2020: Proceedings of the 7th iDASH Privacy and Security Workshop 2018*. The full contents of the supplement are available online at <https://bmcmedgenomics.biomedcentral.com/articles/supplements/volume-13-supplement-7>.

All authors designed the method, conducted the experiments, analyzed the results and wrote the paper. SC implemented algorithm step 1. NG and MG implemented algorithm step 2 and JTP implemented algorithm step 3. All authors read and approved the final manuscript

This work and its publication costs were funded by the grant \#2017--201 (DPPH) of the Strategic Focal Area "Personalized Health and Related Technologies (PHRT)" of the ETH Domain.

The evaluation data can be found at <http://www.humangenomeprivacy.org/2018/competition-tasks.html>

Not applicable.

Not applicable.

The authors declare that they have no competing interests.