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
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
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
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
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
6 votes
5 answers
6k 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 ...
Thomas Lieven's user avatar
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 ...
Andrei Petrenko's user avatar
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
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
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
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
6 votes
1 answer
690 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 ...
Papa Delta's user avatar
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 ...
LRM's user avatar
  • 1,376
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 ...
vince.h.c's user avatar
  • 137
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 ...
user2511133's user avatar
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 ...
pAkY88's user avatar
  • 163
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
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
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
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
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: ...
Karen 's user avatar
  • 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)...
Heo's user avatar
  • 61
1 vote
1 answer
356 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 ...
Alvai's user avatar
  • 63
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
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
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
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
6 votes
1 answer
617 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: ...
Lumlum's user avatar
  • 61
5 votes
1 answer
880 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 ...
sashank's user avatar
  • 6,194
5 votes
1 answer
414 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 ...
zetaprime's user avatar
  • 591
5 votes
2 answers
479 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 ...
Robin's user avatar
  • 103
3 votes
1 answer
513 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)$$
user11706's user avatar
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 ...
kawsaw's user avatar
  • 115
3 votes
1 answer
576 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 ...
user41864's user avatar
3 votes
2 answers
510 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 ...
irakliy's user avatar
  • 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}$ ...
Tyler D Law's user avatar
2 votes
1 answer
455 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?
fallere456's user avatar
2 votes
1 answer
532 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(...
mip's user avatar
  • 327
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 ...
Umer's user avatar
  • 73
1 vote
2 answers
839 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?
Happy Coco's user avatar
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?
user375868's user avatar
1 vote
1 answer
244 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 ...
Jason Kleban's user avatar
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
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
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
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
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
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
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
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
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