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

learn more… | top users | synonyms (1)

4
votes
2answers
988 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 ...
4
votes
2answers
71 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, ...
4
votes
1answer
409 views

Fully Homomorphic Encryption over the Integers - Runtime Question

I have a question regarding the paper "Fully Homomorphic Encryption over the Integers" (http://eprint.iacr.org/2009/616.pdf): On page 6 after they set their parameters, it says "This setting results ...
4
votes
1answer
42 views

How does order-preserving encryption work on string?

I have read “How does order-preserving encryption work?”. After that, I completed order-preserving encryption on integer data. Now, I have four questions in this subject: Is it possible to apply ...
4
votes
2answers
98 views

Are there simpler FHE methods than Craig Gentry's original paper?

Craig Gentry's 2010 paper on FHE is very cool, and I'm planning on implementing a basic proof of concept FHE. I was wondering though, are there any simpler methods that have been discovered since ...
4
votes
1answer
252 views

“Practical” operations supported by functional encryption?

I'm curious about what operations have been developed into functional encryption schemes. What I mean by that is: what operations can be performed over encrypted ciphertexts? Obviously homomorphic ...
4
votes
1answer
157 views

Multiplication-homomorphic schemes

I'm looking into multiplication-homomorphic schemes now and basically I see that there are 3 options: RSA, Boneh-Goh-Nissim and ElGamal. RSA was proved to be insecure unless message is randomly ...
4
votes
2answers
240 views

Which multiplicatively homomorphic encryption scheme supports encryption of 0?

I want a multiplicatively homomorphic encryption scheme that supports encryption of 0 (e.g. Elgamal doesn't support). I also want the multiplication to be operated on the ciphertext of 0, i.e., if ...
4
votes
1answer
167 views

Public key in fully homomorphic encryption over the integers

I'm reading “Fully Homomorphic Encryption over the Integers” by van Dijk et al. I wonder why $x_0$, which is a component of the public key, should be an odd number?
4
votes
1answer
435 views

Can any one explain Circuit Privacy using fully homomorphic encryption from Gentry's thesis?

Craig Gentry's thesis talks about circuit privacy being straight forward from fully homomorphic encryption in the last chapter. Can somebody explain in simpler terms what that means ? I have read it ...
4
votes
0answers
140 views

Zero-knowledge proof for the product of additive Paillier ciphers

Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key. Alice computes $E(\sum x_i)$ from ...
4
votes
0answers
80 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
4
votes
0answers
44 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?
4
votes
0answers
128 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
4
votes
1answer
69 views

Symmetric key in homomorphic encryption over the integers

Much like this question: Public key in fully homomorphic encryption over the integers I am also reading I'm reading Fully Homomorphic Encryption over the Integers, but I'm working on implementing the ...
4
votes
0answers
61 views

Additive homomorphic encryption scheme without change in operator

I'm looking for an additive homomorphic encryption that the addition operator (+) in its plaintext space be the same as addition operator in its ciphertext space. (Schemes like Paillier do addition in ...
3
votes
5answers
2k 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 ...
3
votes
4answers
551 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 ...
3
votes
2answers
1k views

breaking fully homomorphic encryption schemes

Fully homomorphic encryption schemes allow one to evaluate any arbitrary computation over encrypted data. Intuitively this seems to be too weak, irrespective of how we achieve this. An adversary who ...
3
votes
2answers
120 views

Why is Paillier Cryptosystem called probabilistic?

The definition of Paillier Cryptosystem says that it is a probabilistic asymmetric key algorithm for public key cryptography. Can some body explain why it is called "probabilistic"?
3
votes
1answer
186 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 ...
3
votes
2answers
819 views

Additive ElGamal cryptosystem using a finite field

I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive ...
3
votes
2answers
210 views

Proof that a hash matches an encrypted file

Assume that Alice has a file $F$ which she is going to send, in encrypted form to Bob. Alice possesses $F$ and an encryption key $K$. She sends to Bob the encryption of $F$ using $K$, $E(F,K)$ as ...
3
votes
2answers
128 views

How to find the value of a vector modulo a basis in lattice-based cryptography

In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance: $\psi \leftarrow \psi' \mod B$ Taken from page 69 of ...
3
votes
2answers
110 views

Homomorphic Encryption vs. Garbled circuits

I'm currently trying to understand all the differences between homomorphic encryption and garbeled circuits. As I understood the use of homomorphic encryption hides either the data or the computation ...
3
votes
1answer
202 views

Logical OR operation in a homomorphic additive cryptosystem

Suppose we have a cryptosystem homomorphic for addition (say Paillier's). Is there a way to perform a logical OR operation between two binary values (with a binary result). We can, of course, obtain ...
3
votes
1answer
54 views

Truncating ciphertexts on ring-LWE schemes

On the section 5.4 of the paper Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, the authors explain how to discard some bits of the ciphertexts to get smaller ciphertexts and ...
3
votes
1answer
132 views

Paillier Cryptosystem - Practical applications?

I wonder: are there any real-world practical applications using the Paillier cryptosystem , as introduced in [1], or some derivations of it? I'm aware of quite a few schemes proposed in literature ...
3
votes
2answers
332 views

AES and Homomorphic Encryption

Is it possible to do the following? Input would be to generate a new AES key, encrypt the private data with that key, encrypt the AES key with the FHE key, and send the FHE-encrypted AES key along ...
3
votes
1answer
436 views

FHE over the Integers - reduction to approximate gcd problem

I have three quick questions concerning the reduction of the scheme to the approximate gcd problem: What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step ...
3
votes
1answer
551 views

How to compute the dot product on encrypted values?

Is there a practical homomorphic encryption scheme that can give reasonable execution time results in computing a dot product: $$a_1*b_1 + a_2*b_2 +a_3*b_3 +\ldots+ a_n*b_n$$ I imagine the scheme will ...
3
votes
2answers
188 views

Security model for privacy-preserving aggregation scheme.

Suppose that $S=(E,D)$ is an additively homomorphic encryption scheme. Now I want to design a protocol $P$ such that given inputs $x_1,x_2,..,x_n$, the adversary $A$ (who can decrypt) can only learn ...
3
votes
3answers
299 views

Existing works on pre-computing ElGamal ephermal keys

I was playing around with a problem in e-voting schemes that use additive homomorphic encryption to tally votes, namely that at the end of the day somebody (or somebodies, if the secret material has ...
3
votes
1answer
68 views

How to prove hardness of approximate-GCD problem?

I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker ...
3
votes
1answer
187 views

Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext?

Scenario: Assume I encrypt message $m$ using Paillier encryption, so I would get $c=E(m)$. I give the identical $c$ to two different parties, parties $D$ and $E$. Party $D$ computes: $c_{D}= ...
3
votes
1answer
63 views

What about using only XOR gates in homomorphic encryption?

What if we were substitute the ANDs with XORs in some homomorphic encryption scheme like BGV(https://eprint.iacr.org/2011/277.pdf), LTV ( https://eprint.iacr.org/2013/094.pdf) ? It may be more ...
3
votes
1answer
123 views

Can homomorphic decryption of DES be practical?

I was reading this paper Homomorphic evaluation of the AES Circuit by Gentry et al. when I thought if something similar can be done with DES or 3DES, e.g. it is plausible to decrypt DES ...
3
votes
1answer
319 views

What's efficient MPC protocol for determining if sum's bigger than y?

My secure multi-party computation (MPC) in need is simply to determine if a sum of two private variable is bigger than a given value $y$, as $f(x_0, x_1) = [(x_0 + x_1) > y]$ in which the value ...
3
votes
2answers
171 views

How to compare two datasets „anonymously”?

Ok, I hope this question makes some sense because I am not so sure how to word it any differently… Imagine the following situation: There are 10 defined colors (blue, orange, yellow etc.) There are ...
3
votes
3answers
782 views

Searching over encrypted data [duplicate]

Is there any library/tool available which can allow me to search over encrypted data? I would like to encrypt data on client side, send it to cloud and perform search in cloud. I've been reading ...
3
votes
3answers
244 views

Algorithm to securely exchange identities

Say four people each have a public/private key pair that they can use to encrypt or sign messages. They have an anonymous way to post messages such that the others can see them. Malicious entities can ...
3
votes
1answer
66 views

Why doesn't this operation reveal the voter's message?

I am working my way through this paper. I am trying to figure out the OR zero knowledge proof in figure 2. The prover is verifying that she has correctly voted, and that her input satisfies ...
3
votes
2answers
88 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 ...
3
votes
2answers
161 views

paradox on fully homomorphic equality checking

Imagine, a client encrypts a corpus of data (say documents of text) with the public key of a Fully Homomorphic Encryption scheme (FHE) and outsources the data to an untrusted server.Now the client ...
3
votes
1answer
81 views

Is it possible to encrypt data points but still be able to select the ones “near” a given value?

We have an application where we would like to store "encrypted" data points (as in, not being able to know the original - plaintext - data just by looking at the stored - encrypted - version of it) ...
3
votes
1answer
116 views

Paillier cryptosystem preserve ordering of sums for two integer sequences

According to Paillier cryptosystem the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts. I have two separate integer sequences X and Y that have same number of ...
3
votes
2answers
276 views

Real life systems that use concepts of crypto computing [closed]

Are there any working cloud/internet solutions/products that operates on encrypted data such as systems using homomorphic encryption, secure multiparty computation, electronic voting, private ...
3
votes
2answers
283 views

secure integer comparison

I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of ...
3
votes
2answers
440 views

secure multiparty computation for multiplication

Suppose there are $N$ parties $p_j$, each with a binary $b_j\in{\{0,1\}}$. The problem needs to compute the multiplication of number of ones times that of zeros, that is, ...
3
votes
1answer
73 views

Why is this homomorphic encryption correct?

In LTV-FHE, section 3.3.2 Formal description, a ciphertext looks like this $c=hs+2e+b = (2g/f)s+2e+b$, where $h = 2g/f$ is the public key, $f$ is the secret key, $g, s$ and $e$ are chosen randomly, ...