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
27 views
How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?
A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
0
votes
1answer
55 views
Are there any homomorphic first and second preimage resistant (cryptographic) hash functions?
Are there any homomorphic cryptographic hash functions that satisfy $\text{H(A + B)} = \text{H(A)} + \text{H(B)}$ which maintaining pre-image resistance
0
votes
0answers
29 views
Blinding factor SEAL
For a protocol, I need to blind a ciphertext. I am not sure how to choose the blinding factor. How should I choose the range? What should I consider to offer security?
I am using CKKS scheme, the one ...
2
votes
2answers
76 views
Is OTP with homomorphic encryption trivial?
If my key size is as large as the data I'm encoding, is it trivial to devise a theoretically secure homomorphic encryption scheme for integers (or else any finite/infinite group with order) that ...
2
votes
0answers
33 views
Generate unique pair $g^k, E(k^{-1})$ for each group
Let say I have n computers, with some t-threshold encryption scheme.
I want to have n public shares (known to every participant) such that any t of them generates a pair:
$g^k, E(k^{-1})$ that is ...
8
votes
1answer
124 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, $\...
1
vote
1answer
41 views
BGN encryption scheme with unbounded message space
In Evaluating 2-DNF Formulas on Ciphertexts stated that
decryption in this system takes polynomial time in the size of the message space T. Therefore, the system as described above can only be ...
0
votes
0answers
51 views
Division using Fully Homomorphic Encryption
When I am not allowed to do interaction with server, then I use Taylor approximation for division in non-interactive process.
Let's say that I am allowed to do interactions with server.
I have ...
1
vote
1answer
45 views
What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices?
How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption ...
2
votes
1answer
36 views
Standard deviation of gaussian noise in FHEW scheme
I've got two questions regarding the paper FHEW: Bootstrapping Homomorphic Encryption
in less than a second.
First, the final error of a ciphertext after the refresh procedure is stated as following ...
4
votes
1answer
65 views
What is the shortest ciphertext size output by FHE?
Assume we use batching and modulus switching techniques to reduce the size of ciphertext in fully homomorphic encryption (FHE).
Question: What is the shortest ciphertext bit-size output by the most ...
2
votes
1answer
89 views
Zero Knowledge range proof
I like the idea of a Zero Knowledge range proof. But I read that, to prove my age in a range, a commitment is required by a trusted party (TP) stating my age. How does that work? is the commitment a ...
0
votes
0answers
55 views
homomorphic division with scaling/Paillier
Let's say that I have to use fractions instead of integers and I am using Paillier cryptosystem. So, I use scaling to obtain integers. Assume that I have a secure division protocol. What happens if ...
3
votes
0answers
50 views
Is it possible to randomize the secret in homomorphic secret sharing?
I was reading the Homomorphic Secret Sharing from Paillier Encryption paper. I see that the authors suggest to secret share $\lambda y$ as $\lambda y = z_1 + z_2$. Then, one can exponentiate an ...
1
vote
0answers
43 views
SEAL - binary encoded ciphertext
In SEAL, am I able to convert a ciphertext that is encoded with polynomial to a ciphertext that is encoded as binary?
0
votes
1answer
65 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
74 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
47 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
100 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
91 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
76 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
vote
1answer
87 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
56 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 ...
6
votes
1answer
446 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
94 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 ...
3
votes
0answers
63 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
109 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
90 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
63 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
216 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
57 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
52 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
67 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
60 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
137 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
109 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
133 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
95 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
234 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
111 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
43 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
45 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
1k 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
51 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
67 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
51 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
47 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 ...
