Questions tagged [homomorphic-encryption]

Cryptosystems which support computation on encrypted data. They might be partially homomorphic (support for one operation such as + or *) or they might be fully homomorphic (any sequence of + and *).

198 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
150 views

Is there any way to prove two numbers that are equal after Paillier encryptions?

I have two numbers $x_1$ and $x_2$, and there are two Paillier homomorphic encryption (public, private) key pairs $(p_1,r_1)$ and $(p_2, r_2)$. I only know $p_1, r_1$ and $p_2$. Suppose $C_1=E_{p_1}(...
2
votes
0answers
77 views

Dimension involved by tensor product on Ring-LWE based homomorphic encryption

As far as I know, given two $n$-dimensional vectors $\mathbf{a},\mathbf{b} $, tensor product $\mathbf{a} \otimes \mathbf{b} $ produces $n\times n$ matrix. However in Ring-LWE based homomorphic ...
2
votes
0answers
38 views

Encryption design for user data with service access

I'm looking to provide users with a way to give a service sensitive information, which the service can freely use up until the user decides otherwise. I want to encrypt the data at rest (and of course,...
2
votes
0answers
133 views

NTRU-based threshold encryption system?

I want to implement threshold homomorphic encryption for my project. (encrypt a message using one public key, and decrypt a ciphertext using distributed secret keys) I read a paper "Multiparty ...
2
votes
0answers
145 views

Distinguishing advantage in terms of $\Omega(\omega)$

I was going through this paper ("Fully Homomophic Encryption over the Integers Revisited") and the statement written in the first paragraph on page 5 stating $\DeclareMathOperator{\agcd}{AGCD}$ We ...
2
votes
0answers
374 views

Homomorphic set hash with membership proof

I'm trying to solve a problem that goes as follow. There is a set of item and that set is very large. Several actors needs to exchange information about this set, such as adding and removing element ...
2
votes
0answers
346 views

Is modulus switching feasible for plaintext space larger than $\{ 0, 1 \}$?

I read the proof of modulus switching and realised that it can be extended to integers, but do we actually use it for integer encryption in practice? Consider that we are doing additive and ...
2
votes
0answers
93 views

Homomorphic encryption poll for multiple people

I understand for homomorphic encryption, you can perform operations on the ciphertext such that: $E(x_1)+E(x_2)=E(x_1+x_2)$ which can allow you to work out the sum of the plaintext encryption I have ...
2
votes
0answers
280 views

Evaluate similarity between two “encrypted” time series

Can you think of any way to evaluate the similarity between two time series without revealing any information on the time series ? More precisely, considering two time series $x$ and $y$ of length ...
2
votes
0answers
103 views

Additive homomorphic encryption over small fields

Are there encryption schemes that are additively homomorphic with respect to small fields such as $\mathbb{F}_{2^4}$ or $\mathbb{F}_{2^8}$?
2
votes
0answers
549 views

About BGV Scheme Batching Technique

I am reading BGV12 about BGV homomorphic scheme right now.But I am being stuck to understand Batching technique in this paper. In Pack function (page 32),this paper feeds ciphertext $c_i$ and sk $s_1$...
2
votes
0answers
60 views

Quantifying bit security for smart-vercauteren encryption scheme

I am working on project that requires to compare in terms of security between two encryption schemes, one of them is the SV scheme. However, I dont know what are the steps exactly towards quantifying ...
2
votes
0answers
100 views

Security parameter p =O(n)

In many homomorphic encryption scheme, a security parameter is calculated as p =O(n). How to use the complexity order as values? Is there any specific method with an appropriate example?
2
votes
0answers
58 views

Upper bound on r* on page 7 in the Scale Invariant Fully Homomorphic Encryption over the Integers paper

I was hoping to get some clarification on how the bound on r* was calculated (bottom of page #7). I'm trying to reproduce the results that have been shown, however I keep getting a slightly smaller ...
2
votes
0answers
93 views

In FHE over integers is each bit of the cyphertext encrypted under the new key?

In the paper Fully Homomorphic Encryption over the Integers, a method is shown for doing homomorphic encryption using only integers. The basic idea is that a bit m is encoded as a large integer c. ...
2
votes
0answers
313 views

How can I multiply an additively homomorphic encrypted value by a float number?

As we all know, if $E()$ is an additively homomorphic encryption, we can multiply $E(a)$ by an integer $b$, then we will get $E(ab)$. But what if $a$ is a float number? Can we still get $E(ab)$? Which ...
2
votes
0answers
256 views

Scale-Invariant DGHV Scheme - Decryption

I have just started reading the Scale-Invariant Fully Homomorphic Encryption over the Integers paper and I'm a bit confused about something: When decrypting the ciphertext: $c = r + (m+2r^*) \cdot \...
2
votes
0answers
580 views

Performance of Fully homomorphic encryption VS Paillier encryption in Practice

Consider two schemes both have computation complexity linear to the input size (i.e. number of inputs). One scheme is based on Paillier encryption and the other one is based on fully homomorphic ...
2
votes
0answers
134 views

In DGHV FHE, why noise $r$ can be in $(-2^{\rho'}, 0)$?

"Fully Homomorphic Encryption over the Integer" described a simple FHE scheme based on the GACD assumption. Its encryption function (on page 6) has the form $c \leftarrow (m + 2r + 2*\sum_{i \in S} ...
2
votes
0answers
157 views

Question about OR operation in fully homomorphic encryption

This page (which won't let me post a comment, sadly!) describes how the original FHE paper by Craig Gentry describes FHE. (Other references to this stuff can be found on this question.) It mentions ...
2
votes
0answers
121 views

Homomorphic proxy re-signature

Alice has a value $a$ and she signs it using her secret key $d_1$ as: $s_1 = (r_1 * g^a)^{d_1} \bmod p$, and Bob has a value $b$ and he signs it using his secret key $d_2$ as: $s_2 = (r_2 * g^b)^{d_2} ...
2
votes
0answers
174 views

How to compute the decompositions used in fast FHE bootstrapping?

Leo Ducas and Daniele Micciancio's recent paper "FHE Bootstrapping in less than a second" gave an exciting result that one can compute the `atom operation' of Fully Homomorphic Encryption (i.e. NAND-...
2
votes
0answers
217 views

Encrypted database: how to deal with general queries?

My question is quite related to the concept of homomorphic encryption, which is not practical at all nowadays. In short, I would like to know how to query encrypted databases. Simple queries which ...
2
votes
0answers
142 views

See any problems with this search-specific homomorphic encoding strategy?

I'm imagining this for use in the scenario of cloud-stored client-encrypted email, where, when seeking to do a string search across messages, you don't want to have to download every stored message in ...
1
vote
0answers
48 views

How does bootstrapping work?

I have read FHE lately. In Fully Homomorphic encryption using ideal lattice[Gen09], I noticed his recrypt algorithms: We have a ciphertext $\phi_1$ which is encrypted by public key $pk_1$, and can be ...
1
vote
1answer
53 views

SS/HE/GC/OT secure integer comparison

I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in ...
1
vote
0answers
35 views

Homomorphic encryption key switching

I understand the general idea of key switching, but I would like to know when it is used. Sometimes it is referred to as same thing as relinearisation(after multiplication), but is key switching also ...
1
vote
0answers
18 views

Proving the security of the public key BGV scheme

The security proof basically comes down to the following based on this paper. We want to show that two distributions are statistically indistinguishable. Say we have that $a,a′,x,x′$ are drawn from an ...
1
vote
0answers
25 views

CKKS : Ciphertext extension

I have a CKKS ciphertext containing [a, b, c, d] and I want to get these 4 ciphertexts : [a, a, a, a]; [b, b, b, b]; [c, c, c, c]; [d, d, d, d]. Is there a more efficient way than repeating the ...
1
vote
0answers
22 views

Palisade: EvalMult between plaintext and ciphertext resulting in tower size mismatch

I hope someone can help me understand an error I get when using Palisades. I want to only use the first 329 slots of a BGV ciphertext, and zero out the rest (which at some point contains some '...
1
vote
0answers
70 views

Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?

There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...
1
vote
0answers
40 views

Secret key generation in the BGV scheme in HElib

This question is about secret key generation, based on section 4.7 in the design document: https://homenc.github.io/HElib/documentation/Design_Document/HElib-design.pdf It seems that if $m$ is not a ...
1
vote
0answers
46 views

Prove Paillier cryptosystem decryption $M=L(c^{\lambda(n)}\bmod n^2)\,\mu\bmod n$

How can we prove mathematically that in Paillier cryptosystem decryption, our message is equal to the right side of $$M=L(c^{\lambda(n)}\bmod n^2)\,\mu\bmod n$$
1
vote
0answers
57 views

CRT decomposition in NTT for BFV

AS explained in section 4.5, decomposition for relinearization (2nd step of ciphertext multiplication in bfv) can be done using RNS components of ciphertext. In other words, they proposed a way to do ...
1
vote
0answers
35 views

How to generate a collinear point without revealing one of the existed two points?

Assume we have point $A(x_A,y_A)$ and point $B(x_B,y_B)$, and now we want to generate a point $C(x_C,y_C)$ so that $A,B,C$ are on the same straight line. All mod $p$. If $A$ or $B$ could not be ...
1
vote
0answers
36 views

cascade encryption - If I encrypt my data using many different encryption algorithms

If I encrypt my data using many different encryption algorithms (using different passwords) how will an adversary be able to decipher the message?
1
vote
0answers
34 views

Threshold Encryption Scheme for Multiple Messages

In a threshold encryption scheme, a dealer generates $(PK,SK1,…,SKn)$ and distributes the secret keys to users indexed by $1,…,n$, and if a combiner obtains $t+1$ partially-decrypted ciphertexts, it ...
1
vote
1answer
167 views

zeroing out slots in SEAL ciphertext

I've been messing around with SEAL library for a few days and I've got a following question. I've got a bunch of datapoints [x_1, ..., x_n], n < poly_mod_deg of type 'double' and I use batch ...
1
vote
0answers
41 views

How is a non-interactive zero-knowlege proof constructed using homomorphic encryption?

I've been reading too much, and I still haven't found the explaination I so crave. I'm looking specifically at zk-SNARKs, as implemented by ZCash. They say they use homomorphic encryption in their non-...
1
vote
0answers
95 views

Homomorphic Multiplication Operation in BFV Scheme

I am working on BFV scheme and trying to create a very simple Python implementation. I am following the paper by Fan and Vercauteren. Most of the operations are easy to implement but I am having ...
1
vote
0answers
68 views

Homomorphic encrypted streams (Paillier)

Situation: Alice (violin) and Bob (drums) play music together and want to (real-time) stream the concert to Carol. In order for Carol to save bandwidth, the stream is sent through a server which ...
1
vote
0answers
243 views

Bootstrapping vs Recryption

In the context of fully homomorphic encryption, what is the difference between bootstrapping and recryption, since both offer the same result which is trying to eliminate/decrease the noise budget. ...
1
vote
0answers
62 views

Is there a way to perform a one way function on encrypted data?

Does the following scheme exist? Let f be a one-way function (say, an encryption scheme). Let $Enc_{sk}(x)$ be an encryption of x. We then have $Eval_{pk}(f, Enc_{sk}(x)) = f(x)$. Note that this is ...
1
vote
0answers
57 views

Key derivation scheme with shared secrets?

I want to derive a list of sub-keys derived[t] from a master key mk by a key derivation function ...
1
vote
0answers
81 views

Homomorphic Public/Private Key Encryption Scheme for Floating Numbers

Is there any public/private homomorphic encryption scheme that directly works on floating numbers or vectors of floating numbers? In our application, we want to find out if $$v_1 \approx v_2, \qquad\...
1
vote
0answers
41 views

Is there a standard benchmark data set for “Homomorphic Encryption” implementations?

Both in terms of statistical analysis (mean/variance, histograms, contingency tables, etc) and machine learning data sets. The question has also been asked here.
1
vote
0answers
39 views

Are biases narrowed towards the provenance of hard NP complete problems relevant?

I hear of randomized reduction, deterministic reduction and non-deterministic reduction of complexity from A to B problems. This could make things impossible for polynomial time adversary prying into ...
1
vote
1answer
149 views

BGV for three multiplication level/depth

Can BGV homomorphic encryption scheme support three multiplication level/depth with the help of key switching and modulus switching? If Yes, how does one set up the parameter to achieve that?
1
vote
0answers
175 views

How to solve a simple case of a RLWE problem

I've been reading up on the Ring Learning with Errors problem and the proposed attacks, in relation to homomorphic encryption. Some of the literature has been quite difficult to understand - what I ...
1
vote
0answers
177 views

How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?

Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element? In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....