Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
37 views

Bitwise homomorphic encryption

I am fairly new to HE and would like a short clarification on how exactly integers are securely encrypted using bits. The main idea is that one encrypts each bit value and represents the n bit number ...
0
votes
0answers
15 views

Fiat-Shamir identification protocol how work with prpoabilty for following case study?

Consider a Fiat-Shamir identification protocol run between a prover and a verifier. To start, the prover selects a secret s(1 ≤ s ≤ n) co-prime to a RSA like modulus n, and computes v = s^2 mod n and ...
0
votes
2answers
86 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
3
votes
1answer
78 views

Is there any way to check hash of homomorphic encrypted data?

I need some algorithm that satisfies: H - hash function Enc - encryption function (using public key) M - secret data $Enc(H(M)) = H(Enc(M))$ Let this system exist: the First person has a secret ...
2
votes
0answers
37 views

Chinese Remainder Theorem and Elgamal

I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way. I have a cyclic ...
4
votes
1answer
74 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 ...
7
votes
1answer
171 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 ...
1
vote
2answers
78 views

Oblivious Decryption: Decrypting with a private key, without knowing the message

I’m trying to devise a protocol, complimentary to a private-set-intersection, involving three parties, namely Alice, Bob and Charlie. Alice has a public and a private key. And receives website logs ...
1
vote
0answers
41 views

Cryptographic Counter

Good morning, I state that I am not an expert in cryptography. I'm studying the feasibility of a project which looks like requires a kind of cryptographic counter that behave similarly to the one in ...
0
votes
1answer
32 views

In Multi-party communication, how can I find that one encrypted value is negative or not?

I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob. Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key ...
4
votes
3answers
447 views

What is the purpose of Homomorphic encryption? [closed]

Homomorphic cryptography is a kind of cryptography that allows you to do special math operations on the ciphertext, and the maths performed are identical to the obvious ones. For example, one person ...
2
votes
1answer
35 views

Paillier encryption problem when q or p divides r

I am having a problem with Paillier encryption as described on Wikipedia. It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$. However, I've been testing ...
2
votes
2answers
58 views

Bijective encryption function in Paillier cryptoststem

In Paillier cryptoststem many ciphertexts can correspond to the same plaintext. How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece? ...
1
vote
0answers
14 views

Legendre conditions on the factors of the fundamental negative discriminant to minimize the 2-Sylow subgroup of the class group

If we know the prime factorisation of the fundamental negative discriminant $\Delta_K$, say $\Delta_K=p_1\cdot p_2 \cdots p_n$, then we are guaranteed that at least $2^{n-1}\mid h_K$, the class number ...
4
votes
0answers
42 views

Threshold homomorphic

Quite a specific question, but are there any threshold signatures that are also homomorphic? Preferably ones that work in the discrete log setting and don't require any pairings.
1
vote
1answer
38 views

Additive homomorphic encryption: strict equality - handling congruence

Is there an additive homomorphic encryption scheme which guarantees that if provided with $E(v)$, $E(m_1)$ and $E(m_2)$ and $E(v)=E(m_1).E(m_2)$ then $v=m_1+m_2$ Please note this is not $v \equiv ...
1
vote
1answer
47 views

For ElGamal-based key encapsulation, is it necessary to hash before using as AES key?

I'm working with SJCL, specifically using ElGamal to encrypt messages. Behind the scenes, this is doing something similar to what's described in this SO post (emphasis mine): Regardless how big ...
2
votes
1answer
44 views

Bitwise operation on secret values revealing the result only to the participants

Given the following situation, what sort of cryptographic construction am I looking for? Alice has a bitfield (vector, polynomial representation, etc.) Bob has a different bitfield of the same length ...
5
votes
1answer
119 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 ...
1
vote
0answers
36 views

Turn a homomorphic encryption scheme into one that doesn't have the homomorphic property

Homomorphic encryption is a form of encryption that allows computation on cipher-texts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been ...
4
votes
1answer
74 views

How can one turn a malleable encryption to not malleable

An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext m, it is ...
1
vote
0answers
36 views

Are software solutions such as FHE, PHE, Garbled Circuits used in practice?

Is Fully Homomorphic Encryption or Partially Homomorphic Encryption or Garbled Circuits used in practice? Or is an alternative used instead (I don't mean encryption just for storage here)?
1
vote
0answers
33 views

Example of an attack on a message exchange which uses the homomorphic property

Can someone give me an example of an attack on a message exchange using this encryption scheme, that uses the homomorphic property? In my opinion, Existential forgery under directed message attack ...
3
votes
2answers
136 views

How to use Homomorphic encryption for secure computing Arctan() function?

In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their ...
8
votes
0answers
99 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 ...
1
vote
1answer
63 views

Can homomorphic encryption achieve program integrity (verification) in the cloud?

As I understand it, homomorphic encryption can be used to keep data confidential while still allowing computations over the data. From another question, I found out that one can also verify the ...
3
votes
3answers
2k views

Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
0
votes
1answer
60 views

How can a fully encrypted homomorphic program resist copying?

Let's say that we have an original homomorphically encrypted program with any possible code inside. What methods can it use to ensure that it is impossible to create an exact copy of it? Are there ...
1
vote
1answer
56 views

Limiting how many key pairs someone can generate without compromising their keys

Is there any way to assign someone a limited quota for how many cryptographic key pairs they can generate (ECC, RSA, any algorithm), and preferably non-interactively? By non-interactively I mean there ...
1
vote
0answers
40 views

Is there a hash function h(M + t1) = c1 that relates to h(M + t2) = c2 in a way that can be verified without knowing M? [duplicate]

Is there a hash function h(M + t1) = c1 that relates to h(M + t2) = c2 in a way that, knowing t1, t2, c1, c2, and with no knowledge of M, it can be verified whether both use the same M?
1
vote
2answers
71 views

Can homomorphic encryption offer program integrity and program obfuscation?

By program integrity, I mean the (encrypted) result I receive is indeed the expected result and not, say, an intermediate result or a result affected by an adversary. Can homomorphic encryption defend ...
5
votes
1answer
144 views

How can homomorphic encryption be probabilistic while allowing for math to be conducted?

I've been playing with some homomorphic encryption libraries. It's given me a greater appreciation for probabilistic encryption. These two answers were instrumental in leading to this question, but ...
4
votes
2answers
77 views

Are there any additively homomorphic encryption schemes over $\Bbb Z_2$ besides Goldwasser-Micali?

I am aware of Goldwasser-Micali cryptosystem, which is additively homomorphic over $\Bbb Z_2$. Are there other schemes that satisfy this property? Note: If one is willing to involve advanced tools ...
4
votes
3answers
139 views

Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data

Let's assume I have datapiece A which, after being put through a model or neural network, has a known output X in the unencrypted space. When I move datapiece A into an encrypted space, and put it ...
1
vote
1answer
33 views

Paillier addition with plain text

$A$ sends $B$ the encryption $E_{pkA}(m)$. $B$ computes $R=xE_{pkA}(m) + y$ and sends $R$ back to $A$, but tells him nothing about the parameters $x$ and $y$. $A$ performs $D_{pkA}(R)$ and recovers ...
3
votes
0answers
88 views

How to explain Learning With Errors?

I am trying to understand this concept of Learning With Errors. There does not seem to be a layman explanation of it anywhere. Here I describe layman as someone who understands ML concepts a bit (non ...
2
votes
1answer
81 views

Question about Damgård–Jurik crypto system

I am reading the paper about Damgård–Jurik cryptosystem. In the proof, I found this equation $c^d = (g^mr^{n^s})^d = (\boxed{(1+n)^{j m}x^m}r^{n^s})^d = \boxed{(1+n)^{j md\pmod{n^s}}}(\boxed{...
2
votes
0answers
53 views

A question about fully homomorphic SIMD operations

I'm going through Gentry, Halevi and Smart's paper "Fully Homomorphic Encryption with Polylog Overhead" and have a question about the permutation operations. Background: The cyclotomic polynomial ...
1
vote
1answer
57 views

Anonymity of Paillier cryptosystem in e-voting system

I'm not an expert so at the moment I'm trying to figure out (at high level) how such cryptosystem would exploit it's homomorphic properties to guarantee anonymity in a e-voting system. As far as i ...
0
votes
1answer
77 views

Homomorphism with subtraction for Pedersen Commitment

I was trying to use Pedersen's homomorphic property for some privacy preserving mechanism, and to the best of my knowledge $Com(x1,r1)\cdot Com(x2,r2)^{-1} = g^{x1-x2}h^{r1-r2}$ That is, if we ...
1
vote
1answer
64 views

What is an example of elgamal homomorphic double encryption?

I am looking for such an cipher algorithm that is based on assymetric cryptography where the order of encrypting is irrelevant. For example: There is a message "x", Bob encrypt that message with his ...
2
votes
1answer
98 views

Is there any way to prove two numbers that are equal after Paillier encryptions?

I have two numbers $x_1$ and $x_2$, and there are two Paillier homomorphic encryption (public, private) key pairs $(p_1,r_1)$ and $(p_2, r_2)$. I only know $p_1, r_1$ and $p_2$. Suppose $C_1=E_{p_1}(...
3
votes
1answer
72 views

Can any one explain why circuit privacy is needed on homomorphic encryption?

I know some works have been done in the context of cirrcuit privacy on homomorphic encryption, where from an output ciphertext it does not allow someone to distinguish what function is computed. I ...
1
vote
1answer
71 views

Is there any additively homomorphic schemes that can make range proof?

I want to know whether there is any additively homomorphic schemes that can make a non-interactive range proof. For example, I have a pair of public and private key pairs $(K_p,K_v)$ that satisfying ...
3
votes
1answer
69 views

What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption?

In Brakerski and Vaikuntanathan's homomorphic encryption scheme, the relinearization function turns a 3-element cipher back to a 2-element cipher by using a set of public homomorphism keys (https://...
1
vote
1answer
105 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 ...
2
votes
1answer
86 views

How can I construct a proof that the decryption of a certain encrypted file matches a hash?

Let's say Alice has file $F$ and she generates key $K$. She widely publishes the $hash(F)$ for identification. She wants to sell the file to Bob. She encrypts the file with $K$ and sends both $E_f = E(...
5
votes
1answer
141 views

What are the leading FHE schemes?

I'm trying to understand the current context for fully homomorphic encryption. What are the most influential papers that are the basis for the most close-to-practical techniques today? Of course ...
1
vote
1answer
79 views

How to define a FHE scheme whose plaintext space is infinite using boolean circuits?

There are many kinds of fully homomorphic encryption scheme by using boolean circuits. And the plaintext space $\mathcal{P} = \{ 0,1 \}$. If there is a -bit FHE scheme, we can construct a FHE scheme ...
0
votes
1answer
38 views

Is it possible to manage an encrypted dataset for face recognition?

Im in my final year of PhD in computer vision and my supervisor has given me a task that I am not very familiar with. So I am teaching myself homomorphic encryption everyday. This question is mostly ...