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 *).
0
votes
0answers
5 views
Combination of Homomorphic Encryption and Homomorphic Signature
Is there any scheme that can combine homomorphic encryption and homomorphic signatures?
If not, is there any paper shows why they can't be combined together?
And is Homomorphic Signature called a ...
0
votes
1answer
19 views
Refreshing Procedure in FHEW: membership test
I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure.
Especially, they ...
1
vote
1answer
67 views
Comparable or partially homomorphic public key derivation for signatures?
Are there any public key signature schemes that can be compared blindly or partially homomorphically based on the private key without knowing the private key?
Example: let's say I derive a public key ...
2
votes
0answers
41 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?
9
votes
3answers
1k 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 ...
0
votes
1answer
52 views
Are there any practical use cases for performing homomorphic operations on encrypted Strings?
Does anybody know which practical use cases there are to operate on encrypted strings? Even niche problems that can be solved using homomorphic encryption on strings are interesting to me, but not ...
2
votes
1answer
67 views
Can I perform a division of two integers homomorphically using ElGamal?
How can I perform a division of two integers homomorphically?
(Simplifying assumptions can be made if needed, that is, I am fine with dividing numbers that are whole and the result will be whole as ...
2
votes
1answer
64 views
Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?
In ZK Snarks bilinear pairings are used to do "encrypted computation". I was wondering if we can use Partial Homomorphic Encryption or Somewhat Homomorphic Encryption instead of bilinear pairings. Can ...
-1
votes
0answers
48 views
MPC using homomorphic encryption
Is there a way to implement secure square root protocol between two parties (using homomorphic encryption)?
I couldn't find existing solutions in literature.
My desired protocol is as follows:
...
1
vote
1answer
66 views
How does the polynomial modulus work in the Fan-Vercauteren scheme?
I'm reading this introductory blog on the Fan-Vercauteren
scheme and there are a few things I don't understand about polynomial moduli. The author uses practical examples:
Because we are ...
3
votes
0answers
47 views
Using error-correcting codes for the bootstrapping procedure of Fully Homomorphic Schemes
In the context of Fully Homomorphic Schemes, we use a technique called "bootstrapping" to refresh the ciphertext, by evaluating homomorphically the decryption circuit with an encrypted version of the ...
5
votes
1answer
442 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 ...
4
votes
0answers
80 views
Two plaintexts map to the same ciphertext in fully homomorphic encryption?
In standard symmetric encryption, we can create an encryption scheme, in which two plaintexts $x_1, x_2$ map to the same ciphertext $y$, by choosing appropriate keys $k_1,k_2$ (!).
The most simple ...
2
votes
0answers
51 views
Is there a partially homomorphic cryptosystem without an inverse (addition without subtraction, multiplication without division)?
I am learning about partially homomorphic cryptography, and was interested to see if there was a system such that one operation was homomorphic, but its inverse was not.
For example, if I have two ...
9
votes
3answers
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 ...
1
vote
1answer
97 views
Interactive Homomorphic Encryption
Let's say that I have a plain computational process that consists of several divisions and I do not want to do it with non-interactive homomorphic encryption.
I would like to ask how can I call this ...
2
votes
2answers
79 views
Homomorphic properties of Paillier
I'm curious about the homomorphic properties of Paillier. So, basically if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$, I will ...
0
votes
1answer
58 views
Binary representation of the inverse of a big number [closed]
In one of the first FHE schemes by Gentry, the KeyGen algorithm is defined as follow:
For a security parameter $\lambda$, set $N = \lambda ^ 2, P = \lambda ^ 2, Q = \lambda ^ 5$.
KeyGen$(\lambda)$: ...
7
votes
1answer
190 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,...
2
votes
0answers
52 views
How HomNAND has been computed in Leo Ducas and Daniele Micciancio's FHEW?
In section 4.1 of Leo Ducas and Daniele Micciancio's paper FHE Bootstrapping in less than a second, HomNAND has been computed as follows:
$$
(\textbf{a}, b) = HomNAND((\textbf{a}_0, b_0),(\textbf{a}_1,...
0
votes
1answer
48 views
Verification of data on an untrusted remote storage server
I was looking at tahoe-lafs which accepts a file, encrypts it, does erasure coding on it which generates n shares and then distributes it over the storage servers. The distribution is Share 1 = Server ...
2
votes
0answers
56 views
Verifiable secret sharing - Benaloh scheme; some doubts not answered earlier
I reviewed the paper "Secret sharing homomorphisms: keeping shares of a secret secret" by J.C. Benaloh yesterday and I had some difficulty understanding his version of verifiable secret sharing to ...
0
votes
1answer
52 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
2answers
113 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 ...
4
votes
1answer
107 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
90 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 ...
5
votes
1answer
88 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
208 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
93 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
42 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 ...
1
vote
1answer
43 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
717 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
46 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
66 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
49 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
42 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
61 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
48 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
127 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
39 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
92 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
44 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
34 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
168 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
107 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
76 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
63 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 ...
2
votes
2answers
84 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 ...
