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 *).
932
questions
1
vote
1
answer
17
views
In the DGK Cryptosystem, how hard is it to recover g, if we have knowledge of the private key?
Given the knowledge of the values for $v_p$, $v_q$, $n$ and $u$, and knowing that $g^{u*v_p*v_q} \mod n = 1$, how hard is it to compute the value of $g$? My assumption is that it is as hard as the RSA ...
- 13
1
vote
1
answer
53
views
How to multiply a boolean share with an arithmetic share
The problem is to multiply a boolean share with an arithmetic share, a commonly used technique in functions such as multiplexing. In my opinion, a straightforward approach would be to convert the ...
- 47
1
vote
1
answer
34
views
CKKS Encryption key, decryption key and evaluation key sizes
I am using CKKS to securely compute one function. I am using Pyfhel library with the below parameters for the experiment:
...
0
votes
0
answers
36
views
Help with Hybrid Homomorphic Encryption
I read in this paper here that symmetric ciphers like AES is not a good choice for Hybrid Homomorphic Encryption due to large multiplicative depth. I want to understand more about this statement. How ...
- 19
0
votes
0
answers
23
views
Issue building RLWE based program
I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
0
votes
0
answers
13
views
Tutorial of lattice estimator to compute a specific function with BGV
I recently try to go into lattice estimator https://github.com/malb/lattice-estimator
I did find the document of it, but unfortunately, can not follow.
May I ask how to run the lattice estimator to ...
- 361
2
votes
1
answer
62
views
What does the $\pi_r^{-1}$ notation mean in the Frobenius Map in CKKS Scheme?
I read the Homomorphic Encryption Paper, TensorFHE. On page 5, they explain the Frobenius Map function that is used for the ciphertext rotation in CKKS Scheme.
It said:
For every $a^{(i)}=(a^{(i)}_j)$ ...
- 123
0
votes
0
answers
25
views
Set union homomorphic hash function that ignores duplicates
Does a hash function with set(not multi-set) union homomorphism exist? LT-hash is very close to what I am looking for where items could be added/removed from the set in arbitrary order but adding the ...
- 1
1
vote
1
answer
104
views
EC-ElGamal scalar-to-point mapping for a secure multiparty computation setting
The ElGamal cipher is additively homomorphic for points, but not for scalars. In a single party setting, people usually get around this by mapping the scalar m to ...
user113967
2
votes
1
answer
96
views
Number field embeddings for homomorphic encryption
Suppose Alice chooses a number field $K$ and a polynomial $f(x) \in K[x]$. She computes the splitting field $L$ along with an embedding $\varphi: K \rightarrow L$. In SageMath,
...
- 131
0
votes
0
answers
49
views
CKKS encoding. Why not just use fft
I am studying the ckks scheme from this blog post. In the vanilla encoding part we want to encode a complex vector of size N to a complex polynomial of degree N-1. This of course is possible if we ...
2
votes
0
answers
68
views
Fully homomorphic encryption textbook suggestion
I am looking for mathematics textbooks which include a rigorous introduction to fully homomorphic encryption and especially CKKS / TFHE algorithms at the level of Boneh and Shoup's A Graduate Course ...
- 171
0
votes
0
answers
24
views
Help with TFHE multiplication
I am trying to understand TFHE and realise that TFHE supports three types of ciphertexts:
LWE : supports additive homomorphism and multiplication with constants
RLWE : compact version of LWE
RGSW : ...
- 19
0
votes
0
answers
32
views
Homomorphic Encryption from LWE (Gentry) - Error Bounds
I am reading Gentry2013. He describes on page 10 under descryption, that $v_i \in (q/4, q/2]$. Later he describes that this ensures that the error does not grow outside of $q/2$ such that the ...
1
vote
1
answer
40
views
Why use coordinate-wise random rounding instead of regular rounding?
I've been reading a blog article on CKKS encoding and there they implement a coordinate-wise random rounding algorithm (which can be found in this paper) instead of the plain old rounding. The same ...
- 171
1
vote
0
answers
35
views
Sparse Packing for CKKS
Let $N$ be a power of two integer and $n$ be a divisor of $N$. We can encode a vector in $\mathbb{C}^{N/2}$ into the polynomial ring $R=\mathbb{Z}[X]/(X^N+1)$ as described in the original CKKS paper ...
- 171
0
votes
0
answers
35
views
Homomorphic Subtraction and Sign Evaluation
Are there any homomorphic encryption methods that allow both homomorphic subtraction and sign evaluation? Given two integers $A$ and $B$, I would like to know, homomorphically, whether $E(A)-E(B)$ is ...
1
vote
0
answers
32
views
Understanding FHE bootstrapping: value of $q$ fed to lattice estimator
I am implementing OpenFHE. In the implementation I'm generating the modulus chain as shown in the example here. I am trying to run Lattice estimator for the same parameters in this example.
I wanted ...
- 19
0
votes
0
answers
24
views
Urgent help with R-LWE Parameters Choice
I am trying to understand CKKS bootstrap algorithm and wanted to understand how is p (plaintext modulo) and q (ciphertext modulo) related in determining the size of the modulus chain. Suppose my ring ...
- 19
0
votes
1
answer
58
views
About TFHE schemes
I'm starting to read about TFHE, however my background is not that deep. Mostly, I've learnt about it thanks to this paper, and I am trying to delve deeper into it. I've also read the Zama blog post ...
- 23
-1
votes
1
answer
105
views
Urgent help with LWE Estimator
I am trying to estimate LWE parameters. I know of the GitHub library for LWE estimator but it has no instructions for installation and also provides no guidance for running simple examples. I have ...
- 19
0
votes
0
answers
28
views
Privacy-preserving source to destination shortest path algorithms with real-time querying
I'm looking for implementations of privacy-preserving shortest path algorithms that offer real-time or near real-time query performance, where both the source and destination nodes are kept secret.
I'...
- 101
0
votes
0
answers
36
views
Homomorphic Max For Two Distances
I have a interesting geometric problem involving distances on a finite plane. I'll provide the unencrypted mathematical background and proof and after that pose the question as it pertains to HE.
...
5
votes
4
answers
4k
views
Is the XOR of hashes a good hash function?
Definitions:
Let $h$ be a hash function with output size $n$ bytes. Suppose the file $F$ can be divided into chunks of size $n$ bytes $F=f_0+f_1+\dots +f_i$ where the operator "$+$" stands ...
- 153
1
vote
0
answers
61
views
Difference between TFHE and CKKS?
What are the differences in parameters while implementing CKKS vs TFHE?
For example modulus size, ring dimensions, bit security. Any pointers to literature would be appreciated
- 19
0
votes
0
answers
19
views
Is there any bound on the size of ring dimension for Torus FHE?
I see that all implementations of TFHE in opensource supports 2^10 to 2^12 size of ring dimensions. Is there any specific reason (crypto) behind choosing the value or can we choose higher dimensions (...
- 19
0
votes
0
answers
28
views
Does the use of OPRF or OT remove the need of HE in PSI?
I was reading a systematic literature review on Private Set Intersection (PSI) protocols (https://www.sciencedirect.com/science/article/pii/S1574013723000345#sec8), which mentions that the main ...
- 1
3
votes
2
answers
538
views
Is ElGamal homomorphic encryption using additive groups works only for Discrete Log ElGamal? What about EC ElGamal?
It is known that in Discrete Log ElGamal encryption, the ciphertext $E$ is encrypted as:
$a\ =\ g^k$, where $k$ - random scalar from $[0,\ p)$, $g$ - group generator
$b\ =\ (Y^k*m)\mod\ p$, where $Y$ -...
- 77
0
votes
0
answers
44
views
Can there be fully homomorphic encryption with this property?
Lets say Alice has data D and wants to send this data for Bob to process it with algorithm A. Is it possible to encrypt D so that it can only be used to run algorithm A? Alice and Bob will communicate ...
1
vote
0
answers
67
views
Formal connection between fully homomorphic encryption schemes and field homomorphism
In fully homomorphic encryptions schemes (FHE), we aim to preserve both additional and multiplication operations in the encrypted space such that the operations can be decrypted later. This concept ...
- 145
2
votes
1
answer
102
views
Question Regarding Idenitities of Gentry's Homomorphic Encryption on LWE
In the paper Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based Gentry introduces the following identity $\mathbf{a} \in \mathbb Z^n,\mathbf{...
0
votes
0
answers
43
views
Zero-Knowledge Proof of a number being generated "randomly" (similar to a dice roll)
If party1 asks other parties to give a random number, for simplicity, say in a range from 1 to 6 (like in a dice). Is it possible for party1 to ensure that the number received is in a given range and ...
- 307
1
vote
0
answers
19
views
Mental Poker: Can the shuffle of the deck be done Publicaly by a single player at the start of the game
Ref: Mental Poker Revisited by Barnett and Smart.
I am looking at mental poker problem.
Generally, the shuffling process is done by a single player who starts the game and not by all players.
But, in ...
- 307
2
votes
0
answers
53
views
Where are the bad and good lattice basis for LWE's ciphertext: (as+e+Δm, a)?
Letś talk about LWE with 2 dimensions. I've seen somewhere they talking about encrypting with the good basis (public key) and then only the bad basis can decrypt.
I assume that the bad basis is the ...
- 21
0
votes
1
answer
45
views
Can Batch Encode and Bootstrapping Be Used Together
I have referenced some documents stating that "To implement bootstrapping, the plaintext modulus 𝑡
needs to be chosen as a prime power." Meanwhile, the SEAL library documentation on Batch ...
- 1
1
vote
2
answers
122
views
Real-or-Random Security (IND$-CPA) for Homomorphic Encryption?
I am reading papers about homomorphic encryption recently. To my knowledge, all of them opts for the Left-or-Right security i.e. distinguish between $M_0$ and $M_1$ given $\mathcal{E}_K(M_b)$ for $b \...
- 13
1
vote
1
answer
60
views
Literature on Batching in FHE
From what I understand, the folklore way to batch Ring-LWE style cipher texts is to use the Chinese remainder theorem. I am wondering if there are any different approaches/optimizations to this style ...
- 27
0
votes
0
answers
33
views
Should Homomorphic Encryption Keys Be Generated by a Key Generation Server or the Data Owner?
I'm currently working on a project involving homomorphic encryption and I'm trying to determine the best practices for key generation. Specifically, I'm unsure whether the keys should be generated by ...
- 1
4
votes
2
answers
181
views
Why is division in fully homomorphic encryption impossible?
I am trying to use division in PySyft or tenSeal or anything but the devs still haven't learned how to support division?!?!
- 41
1
vote
1
answer
95
views
How can one model the behaviour of CKKS decryption noise?
I am trying to program a simulator for CKKS. It is a "simulator", in the sense that
there is actually no encryption involved, but
to a person seeing only the plaintexts (before encryption ...
- 31
2
votes
2
answers
115
views
Efficient commutative one-way encryption or hashing
Spent two days researching the subject, but so far I haven't come up with a satisfying answer as to whether there is a feasible solution to the following problem:
A has a secret $m$ whereby $0 \leq m \...
- 23
1
vote
1
answer
131
views
Decrypting the sum of votes but not the single vote
For educational reasons I am implementing an e-voting platform.
The idea is that the voter generates the ballot on client side, the ballot is verified using a zero-knowledge proof protocol. Also, the ...
- 13
0
votes
2
answers
110
views
About IND-CPA security of Homomorphic Encryption
I am trying to understand IND-CPA security in (Partially) Homomorphic Encryption schemes. However, the result of the proofs is usually something stating that a ciphertext does not expose anything ...
0
votes
1
answer
136
views
Plaintext modulus choice for Fully Homomorphic Encryption
For SIMD fully homomorphic encryption scheme like BFV/BGV, and the underlying R-LWE problem parameterized by $n, p, q, \alpha$ (respectively the dimension, the plaintext modulus, the ciphertext ...
- 121
0
votes
0
answers
31
views
Ideal multiplicative depth for a generic Levelled CKKS scheme
If I need to implement a generic hardware accelerator for the Levelled CKKS scheme (no bootstrapping supported), what would be the ideal multiplicative depth I should support? - that can support a ...
- 1
1
vote
1
answer
97
views
Is it possible to homomorphically evaluate an encryption circuit?
I know that it is possible to homomorphically evaluate a decryption circuit as it is the main idea behind bootstrapping, but I was wondering if it was possible to evaluate an encryption circuit ...
- 121
1
vote
1
answer
89
views
Implement reciprocal of a floating point number using Chebyshev approximation in CKKS
I am trying to obtain the reciprocal of a floating point value $x$ using the Chebyshev approximation, where $x$ is mostly in the order of $10^3$ to $10^5$. Subsequently, I am trying to implement that ...
2
votes
1
answer
87
views
The cost of the additive homomorphic encryption of McEliece cryptosystem
Let's have two integer-vectors $v_1$ and $v_2$ that are encrypted by McEliece public key. An intermediate node between the sender and receiver receives the two encrypted vectors $\text{E}(v_1)$ and $\...
- 33
0
votes
0
answers
35
views
Interactive Zero-Knowledge Proof for the Multiplication Gate
Refer to an interesting article (link) on Medium on the subject matter.
To understand more about pRandomValue and vRandomValue.
The article mentioned, "pRandomValue, on the other hand, is used to ...
- 307
0
votes
0
answers
126
views
Homomorphic Decryption with the Encryption (ciphertext) of Secret key for Bootstrapping purpose
The section 3.1 of the GHS11 mentions that:
Given the $q_L$-ciphertext $c = (c_0, c_1)$ (that encrypts a polynomial $a \in F_2[X]/F(X)$), we postprocess it to get $c^\prime = (c_0 + c^*, c_1) \text{ ...
- 11