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 *).
126
questions
15
votes
1
answer
3k
views
Representing a function as FHE circuit
I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit,...
- 408
18
votes
3
answers
54k
views
Chinese Remainder Theorem and RSA
Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption ...
- 493
94
votes
8
answers
27k
views
How is CipherCloud doing homomorphic encryption?
Much of the literature and latest papers suggest that homomorphic encryption is still not practical yet.
How is CipherCloud able to achieve this? Does anyone have an idea? Their website does not ...
- 6,184
13
votes
1
answer
9k
views
Can Elgamal be made additively homomorphic and how could it be used for E-voting?
Elgamal is a cryptosystem that is homomorphic over multiplication.
How can I convert it to an additive homomorphic cryptosystem?
How can I use this additive homomorphic Elgamal cryptosystem for E-...
- 153
6
votes
5
answers
5k
views
Approach towards anonymous e-voting
I want to implement an internet-based e-voting system.
Voters shall be able to cast their vote for one out of n possible candidates. Each candidate has his own ballot-box kept by and at a trustworthy ...
- 370
5
votes
4
answers
1k
views
Verify product without revealing multipliers
Situation:
Several participants contribute encrypted random numbers. These numbers will be used to generate community-agreed random (by simple multiplication).
Question:
Is there any way to detect ...
- 201
21
votes
1
answer
9k
views
What exactly is bootstrapping in FHE?
I have been reading about FHE lately, and it seems that bootstrapping is the core concept in order to develop FHE schemes. But, I don't exactly understand the idea behind it. I know that the schemes ...
- 809
13
votes
1
answer
3k
views
Can a homomorphic encryption scheme be made CCA2 Secure?
Is it possible to modify a homomorphic encryption scheme so that it can be CCA2 secure?
From the definition of a homomorphic scheme, it seems that it is malleable, which would result in lack of CCA2 ...
- 133
8
votes
2
answers
2k
views
What is modulo switching, in a nutshell?
Coupled with the terms bootstrapping and relinearization, the term modulo switching appears a lot in the FHE literature. What is it and how does it relate to the other two?
- 3,952
8
votes
3
answers
3k
views
Can we proxy-re-encrypt using homomorphic encryption schemes?
Homomorphic encryption schemes are PKE schemes with an additional special method Evaluate.
The Evaluate method takes input any function (as boolean circuit) and encrypted inputs of the function and ...
- 6,184
6
votes
1
answer
645
views
"Power of one" as input to functions of a cryptosystem
What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this.
I have been told it signifies the ...
- 273
4
votes
1
answer
1k
views
Proof of correctness of a homomorphic ElGamal sum
Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the ...
- 1,356
3
votes
3
answers
4k
views
additive ElGamal encryption algorithm
I'm performing ElGamal encryption algorithm and using the additive homomorphic property so the product of two ciphertexts is the encryption of the sum of the plaintexts.
The problem is that I need to ...
- 31
3
votes
2
answers
4k
views
Can Fully Homomorphic Encryption do comparisons?
I encountered a simple function that even FHE cannot solve. Here's it:
int f(a,b,c,d){
if(a+b>c+d) return a+c;
else return b+d;
}
Since FHE is not ...
- 137
0
votes
2
answers
1k
views
Homomorphic Encryption: how does the equality test on ciphertexts work?
Let's suppose we have a asymmetric crypto-system $H$ which is homomorphic with respect to some function $F$.
Alice encrypts a message $m$ with her private key $e$ in the crypto-system $H$ and obtains ...
- 163
10
votes
1
answer
613
views
IND-CPA secure RSA padding with a partial homomorphic property
A while ago, I asked for an IND-CCA1 secure padding for RSA that still allows for the multiplicative homomorphic property of RSA and got no answers (yet).
Now I've seen fgrieu's answer about standard ...
- 46k
9
votes
2
answers
984
views
How could Fully Homomorphic Encryption support power operations?
Fully Homomorphic Encryption (FHE) enables arbitrary functions computed on encrypted data, because it supports both addition and multiplication. But I wonder if FHE supports power operations.
For ...
- 915
9
votes
2
answers
2k
views
FHE: What is the difference between multiplicative depth and multiplicative level?
I have seen the terms multiplicative depth and multiplicative level while reading
Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean ...
- 335
8
votes
2
answers
2k
views
How to construct encrypted functions (with either public or private data)?
Homomorphic encryption is often touted for its ability to
Compute on encrypted data with public functions
Compute an encrypted function on public (or private) data
I feel I have a good grasp of #1 ...
- 38.6k
6
votes
2
answers
2k
views
Paillier Homomorphic encryption to calculate the means
Paillier Homomorphic encryption supports addition and multiplication with plaintext value.
Can I use these properties to calculate the means of cipher-text values? I try to use the following steps:
...
- 63
1
vote
2
answers
2k
views
Why are homomorphic algorithms slow?
Why are homomorphic algorithms slower than regular(symmetric and asymmetric) algorithms?
For example RSA in regular asymmetric cryptography uses the same algorithm as in RSA homomorphic (partially HE)...
- 61
12
votes
2
answers
5k
views
What does "circuits" mean in Cryptography?
I am not a hardcore cryptographer so this might be a really stupid question. I am looking through some papers in homomorphic encryption and discovered they describe computation as "circuits", why do ...
- 447
11
votes
3
answers
3k
views
Division in paillier cryptosystem
Is division possible in the Paillier Cryptosystem? i.e. given a the cipher-text $C$ of an integer $M$ the plain-text divisor $D$, and only the public key, can one compute the cipher-text of $M/D$ ?
- 315
9
votes
1
answer
6k
views
Why is "semantically secure" important for cryptosystems?
The first question: what is the exact definition of semantically secure?
Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any ...
- 487
8
votes
2
answers
11k
views
Homomorphic cryptosystems in RSA
Hopefully, Crypto can help me understand homomorphic cryptosystems.
I'm designing a high score server for a game I made, and because of facets in the language I'm using, the player would be able to ...
- 183
6
votes
1
answer
611
views
How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme?
In ElGamal encryption scheme, in order to achieve IND-CPA security, one must use a group where the DDH problem is assumed to be hard. As this answer suggests, one way to achieve that is the following:
...
- 61
5
votes
1
answer
383
views
Random Masking of Padded RSA Ciphertext through homomorphism
I had asked a question related to this before:
Oblivious Decryption: Decrypting with a private key, without knowing the message
@rikhavshah has an answer, which I would like to discuss the security ...
- 591
5
votes
1
answer
850
views
Cipher text only attacks on deterministic fully homomorphic encryption schemes
If we have encryptions of additive and multiplicative identities in the corpus of cipher text of a deterministic fully homomorphic encryption (FHE) scheme, I guess we can break it.
If the FHE scheme ...
- 6,184
5
votes
2
answers
465
views
Does homomorphic encryption hide the algorithm itself?
The question is rather simple, but finding resources and answers quite tricky. Homomorphic encryption should enable us to compute over encrypted data. What if the algorithm for computing should be ...
- 103
3
votes
2
answers
2k
views
What is Homomorphic encryption evaluation key
In some homomorphic encryption schemes (e.g Multi-key fully homomorphic encryption report, Computing Blindfolded: New Developments in
Fully Homomorphic Encryption), it defines an encryption key, a ...
- 115
3
votes
1
answer
571
views
Is an equality test possible when using paillier crypto?
Given two ciphertexts $c_1=Ek_1(p_1)$ and $c_2=Ek_2(p_2)$ encrpted by two different users with two different keys, i.e. $Ek_1$ and $Ek_2$ using a homomorphic crypto such as Paillier. Can a third party ...
- 33
3
votes
2
answers
502
views
Commutative homomorphic encryption for zero-knowledge transfers
I am trying to design a scheme that would allow the following:
Alice has a number $a$ which she wants to keep secret
Bob has a number $b$ which he wants to keep secret
Alice can "transfer" a number ...
- 969
3
votes
1
answer
1k
views
Paillier subtraction for negative result
I am trying to figure out subtraction on Paillier.
From what I read so far, given $m_1$ smaller than $m_2$ ($m_1<m_2$)
I can compute $E(m_2-m_1)$ as $E(m_2)\cdot E(m_1)^{-1}$ where $E(m_1)^{-1}$ ...
- 65
3
votes
1
answer
504
views
ElGamal Homomorphic Encryption Formula Question
With Public Key $(G, q, g, h)$ where $G$ is a group, $q$ prime, $g$ a generator of $G$, Am I right in thinking that:
$$\mathrm{Enc}(m;r) := (g^r, h^r \cdot g^m)$$
- 87
2
votes
2
answers
1k
views
Homomorphic Encryption with Addition and Exponentiation
Is there any homomorphic encryption scheme which supports addition and power over cipher text ? Paillier is close but it supports addition and multiplication with a constant.
I am getting an output ...
- 73
2
votes
1
answer
518
views
Homomorphic modulo
What homomorphic cryptographic scheme should I use to perform modular reduction?
I want an encryption scheme along with an operation $\otimes$ such that
$$c = Enc(m) \otimes Enc(d) \Rightarrow Dec(...
- 327
1
vote
2
answers
794
views
What is batching in homomorphic encryption?
I have been reading journals about FHE schemes and I keep encountering the term "batching". What does it mean to batch in homomorphic encryption in a simple way?
- 21
1
vote
2
answers
5k
views
Is it possible to subtract/multiply numbers using homomorphic encryption?
Most of the libraries I've seen allow you to add encrypted numbers. Is it possible to subtract and multiply them?
- 181
1
vote
1
answer
449
views
Where does bootstrapping occur, client side or server side?
In Fully Homomorphic Encryption, where does the bootstrapping procedure performed, in the client-side or the server-side?
Also, which side holds the secret key and the public key?
- 335
1
vote
1
answer
352
views
Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic
While reading this paper I realized that textbook RSA was the only deterministic PHE scheme mentioned. I did cross-check the ones listed in the Wikipedia article also and, quite on the opposite ...
- 63
1
vote
1
answer
243
views
Addition-only PHE in F#
Using homomorphic encryption, I would like to be able to take an encrypted integer and either add 1 or -1 for a new encrypted value. I do not want the encrypted value to be recoverable - just the ...
- 195
0
votes
1
answer
217
views
In Microsoft Password Monitor implementation using HME how do they perform ComputeMatch Function?
https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/
In this they mention
The server then evaluates a matching function on the encrypted credential,...
- 1
23
votes
2
answers
6k
views
What is the most practical fully homomorphic cryptosystem?
Craig Gentry recently gave the first fully homomorphic cryptosystem. Quite a bit of work has been done since extending his work. It seems, however, that no system is practical for real world use.
...
- 38.6k
17
votes
2
answers
2k
views
Why is Approximate GCD a hard problem?
There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.
The paper Algorithms for the Approximate ...
- 428
13
votes
1
answer
4k
views
Noise in Homomorphic encryption
What is the noise in homomorphic encryption schemes? (or where does the noise come from, I see that its inbuilt in the scheme and is not a side channel or disturbance noise)
Is it also due to the ...
- 365
12
votes
5
answers
797
views
Choose a random number that is different from a bunch of other secret numbers
I'm looking for an algorithm where n participants each have a different secret number between $[0..x]$ (and where $x$ is known) and where the participants then select randomly another, non-secret, ...
- 445
12
votes
3
answers
4k
views
difference between leveled FHE and normal FHE scheme
What is/are difference/s between leveled Fully Homomorphic Encryption
and normal Fully Homomorphic Encryption?
- 317
11
votes
3
answers
3k
views
Is full Homomorphic encryption quantum resistant?
Since most of our asymmetric encryption algorithms are going to be out-of-date in a couple of year due to Shor's algorithm, I was wondering about the future of FHE schemes.
I have found this paper, ...
- 324
11
votes
1
answer
5k
views
Homomorphic (encrypted) comparison to an integer
When working with an additive homomorphic encryption scheme (say Pallier's), is there an efficient way to get the encrypted value of a comparison test to an integer value (I realise that an ...
- 385
11
votes
1
answer
5k
views
Somewhat Homomorphic Encryption versus Fully Homomorphic Encryption?
Is that correct that Somewhat Homomorphic Encryption is more efficient that “Fully Homomorphic Encryption” (FHE) but less efficient than Partially Homomorphic Encryption (e.g Paillier encryption)?
Is ...
- 1,583