Skip to main content

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 *).

Filter by
Sorted by
Tagged with
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 ...
sashank's user avatar
  • 6,194
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. ...
mikeazo's user avatar
  • 38.7k
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 ...
typos's user avatar
  • 809
19 votes
3 answers
55k 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 ...
Mihai Todor's user avatar
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 ...
robertkin's user avatar
  • 428
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,...
Binou's user avatar
  • 408
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-...
Nazmul's user avatar
  • 153
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 ...
1010101's user avatar
  • 365
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 ...
Misty's user avatar
  • 133
12 votes
5 answers
799 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, ...
Cedric Martin's user avatar
12 votes
3 answers
11k 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 ...
John Smith's user avatar
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 ...
Boyu Fang's user avatar
  • 447
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?
user2771151's user avatar
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$ ?
user996522's user avatar
11 votes
1 answer
6k 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 ...
user153465's user avatar
  • 1,583
11 votes
3 answers
4k 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, ...
asdf's user avatar
  • 324
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 ...
Richi W's user avatar
  • 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 ...
Dave's user avatar
  • 385
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 ...
AleksanderCH's user avatar
  • 6,462
10 votes
2 answers
1k 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: $...
Alan Wolfe's user avatar
10 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 ...
Cedric Martin's user avatar
10 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 ...
satya's user avatar
  • 1,414
10 votes
1 answer
614 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 ...
SEJPM's user avatar
  • 46.1k
10 votes
1 answer
630 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 ...
Younes's user avatar
  • 111
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 ...
Paradox's user avatar
  • 487
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 ...
fallere456's user avatar
9 votes
1 answer
4k 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?
Nathan Aw's user avatar
  • 2,277
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 ...
zakum1's user avatar
  • 193
9 votes
2 answers
996 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 ...
Jan Leo's user avatar
  • 915
9 votes
1 answer
508 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 ...
Anthony Kraft's user avatar
9 votes
4 answers
566 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 ...
Anon Coward's user avatar
9 votes
0 answers
2k 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:...
Habib's user avatar
  • 951
9 votes
0 answers
689 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/...
user794034's user avatar
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 ...
NT3RP's user avatar
  • 183
8 votes
3 answers
315 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 ...
curious's user avatar
  • 6,180
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 ...
SomekidwithHTML's user avatar
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?
Daniel's user avatar
  • 3,972
8 votes
1 answer
608 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 ...
hdu's user avatar
  • 93
8 votes
1 answer
599 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, $\...
D.W.'s user avatar
  • 36.5k
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 ...
sashank's user avatar
  • 6,194
8 votes
2 answers
3k 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 ...
Tushar Saha's user avatar
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 ...
mikeazo's user avatar
  • 38.7k
8 votes
1 answer
634 views

Difference between a circuit and a normal function

I've seen the word circuit used in many crypto contexts (for example, regarding FHE in this pdf). I've always thought of a circuit as another word for a program or function. But is there a difference -...
Tatiana's user avatar
  • 83
8 votes
2 answers
511 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, ...
SEJPM's user avatar
  • 46.1k
8 votes
1 answer
740 views

Equality checking using additive homomorphic encryption

Given two ciphertexts $c_1 = enc(p_1)$ and $c_2= enc(p_2)$ using any additive homomorphic encryption scheme (or specifically Paillier). Can we find out whether the underlying plaintexts $p_1,p_2$ ...
sashank's user avatar
  • 6,194
8 votes
2 answers
648 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 ...
phan's user avatar
  • 629
8 votes
1 answer
1k 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 ...
Jimakos's user avatar
  • 755
8 votes
0 answers
156 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 ...
user60935's user avatar
8 votes
1 answer
737 views

Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
Guillem's user avatar
  • 81
7 votes
2 answers
225 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: ...
FrostyStraw's user avatar

1
2 3 4 5
19