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 *).
834
questions
93
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,084
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.2k
17
votes
3
answers
49k
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 ...
- 483
17
votes
1
answer
8k
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 ...
- 759
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
14
votes
1
answer
2k
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,...
- 398
13
votes
5
answers
760
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
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
12
votes
3
answers
10k
views
What are some disadvantages of homomorphic encryption schemes?
I'm doing some self-teaching / research for my own benefit in homomorphic cryptography.
I've studied both additive and multiplicative schemes (Paillier and RSA respectively), but all I can seem to ...
- 121
12
votes
1
answer
3k
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 ...
- 355
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 ...
- 437
11
votes
1
answer
8k
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-...
- 133
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
11
votes
3
answers
3k
views
difference between leveled FHE and normal FHE scheme
What is/are difference/s between leveled Fully Homomorphic Encryption
and normal Fully Homomorphic Encryption?
- 307
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, ...
- 305
11
votes
1
answer
3k
views
Applying machine learning algorithms to homomorphic encrypted data
I have a basic understanding of encryption and I got back to the topic because of an interesting site that encrypts financial data using homomorphic encryption (HE) and I would be happy for any input ...
- 163
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 ...
- 375
10
votes
3
answers
2k
views
Homomorphic encryption - Why does addition not imply multiplication?
As far as I know:
There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.
A fully homomorphic encryption (FHE) system can do addition as well as ...
- 6,366
10
votes
2
answers
995
views
Key Size for Symmetric Homomorphic Encryption Over the Integers
In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2.
Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$
Encrypt A Bit m: $...
- 510
10
votes
1
answer
562
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 ...
- 45.3k
10
votes
1
answer
521
views
Computing Logarithm using homomorphic encryption
Let's say we have $Enc_{pub}(a)$, the encryption of an integer $a \in \mathbb{Z}^*$ under the public key pub with a Homomorphic encryption scheme that supports both ...
- 111
9
votes
3
answers
2k
views
Re-encrypting a message and proving that the message has not changed
Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each?
More ...
- 193
9
votes
2
answers
902
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 ...
- 905
9
votes
1
answer
1k
views
Difference between somewhat homomorphic encryption and leveled homomorphic encryption?
Is there any difference between somewhat homomorphic encryption and leveled homomorphic encryption? I heard that leveled homomorphic encryption supports computing circuits of bounded depth on cipher ...
- 1,344
9
votes
1
answer
5k
views
Paillier can add and multiply, why is it only partially homomorphic?
I've seen that it's widely accepted that before Gentry's breakthrough (which is not practical yet) in 2009 there were no known full homomorphic encryption scheme.
I've read here in another answer ...
- 445
9
votes
1
answer
458
views
How do voters verify a Helios (v3) election result?
So from my understanding of verification specification version 3, a Helios election proceeds as follows:
A voter retrieves the system's public key to encrypt their vote & submit it. The voter ...
- 521
9
votes
2
answers
481
views
What math makes it safe to offer a stolen-password check service?
The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to ...
- 55
9
votes
0
answers
1k
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:...
- 941
9
votes
0
answers
637
views
LT codes with Homomorphic hashing
I have been working on a project implementing LT codes with Homomorphic hashing (inspired from http://blog.notdot.net/2012/08/Damn-Cool-Algorithms-Homomorphic-Hashing and http://blog.notdot.net/2012/...
- 91
8
votes
3
answers
2k
views
How is Homomorphic Encryption secure (over integers)?
I have been reading a bit about homomorphic encryption, and have been intrigued by its properties.
If I have some cryptosystem that is homomorphic and supports addition, from my understanding, I can ...
- 183
8
votes
1
answer
5k
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 ...
- 467
8
votes
3
answers
281
views
Homomorphic OR operations
Is there an encryption scheme that provides efficient homomorphic OR operations at the ciphertext space? Of course any fully homomorphic encryption can be used but I do not require or want additional ...
- 6,062
8
votes
2
answers
1k
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 ...
- 315
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,862
8
votes
1
answer
584
views
Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and ...
- 83
8
votes
1
answer
494
views
Obfuscating functions that are mostly zero
Let $f_k(x)$ be a boolean function of two arguments with two properties:
The function $f$ can be efficiently computed.
The output is always 0 or 1, and for any fixed $k$, if we choose $x$ randomly, $\...
- 35.9k
8
votes
2
answers
2k
views
How can we define division operation by using Fully homomorphic encryption
Last fews months, I'm working with homomorphic encryption. Now I am dealing with some computational problems with integers or real-numbers (like arithmetic mean, standard deviation) where division is ...
- 119
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.2k
8
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,543
8
votes
2
answers
455
views
Is there a partially homomorphic quantum secure public key cryptosystem with IND-CCA1 security?
I recentely asked "IND-CCA1 RSA padding?" about whether there is a IND-CCA1 secure variant of RSA. The original version of the question also allowed usage of ECC which would allow usage of ElGamal, ...
- 45.3k
8
votes
2
answers
622
views
Can the Smart-Vercauteren Homomorphic Encryption be implemented as a practical fully homomorphic encryption scheme?
Smart and Vercauteren proposed a homomorphic encryption scheme (PKC 2010) following Gentry's principles. Though their scheme can achieve fully homomorphism theoretically, they admitted that "for ...
- 629
8
votes
1
answer
974
views
Homomorphic decryption circuit in integer-based scheme
I'm reading this excellent paper by Gentry as a smooth introduction to Fully Homomorphic Encryption. Most things are clear to me except from the way the homomorphic evaluation of the decryption ...
- 675
8
votes
0
answers
152
views
Why is fully homomorphic encryption so slow? [duplicate]
What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times ...
- 89
7
votes
2
answers
212
views
Confusion about definition of homomorphic encryption
I am trying to better understand homomorphic encryption, but I feel like I keep getting inconsistent information in the papers that I am reading.
One of the papers I am reading says the following:
...
- 173
7
votes
2
answers
10k
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 ...
- 173
7
votes
1
answer
3k
views
What is the link, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?
What is the link/relation, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?
- 2,197
7
votes
1
answer
721
views
What is scale-invariance notion of a fully homomorphic encryption scheme?
I read this paper https://eprint.iacr.org/2012/078.pdf and I didn't understand what does the author mean with scale-invariance perspective.
The perspective in which we view the ciphertext is ...
- 681
7
votes
3
answers
2k
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,084
7
votes
2
answers
1k
views
Fast attack on approximate GCD problem?
This question is about the approximate GCD problem which is defined as follows: Given any number of the approximate multiples $a_i = p \cdot q_i + r_i$ of $p$, where $p$, $q_i$ and $r_i$ are integers, ...
- 45.3k
7
votes
1
answer
2k
views
FHE Bootstrapping vs. Relinearization
In the context of Fully Homomorphic Encryption, what is the difference between Bootstrapping and Relinearization?
Between two of them, which is the more expensive (computationally) and why?
- 171