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 *).
763
questions
0
votes
0
answers
20
views
How to pack the inputs using hybrid encoding?
I'm reading Gazelle. This paper proposes a matrix multiplication vector(encrypted) method using the SIMD property of RLWE-based FHE. It proposed a hybrid encoding. For $n_o \times n_i$ matrix, when $...
- 379
0
votes
0
answers
35
views
How to quantify privacy, when using homomorphic encryption?
How can you measure how secure or private the new variables are relative to the real (actual) variables.
I want to compare homomorphic encryption and differential privacy in combination with machine ...
- 1
0
votes
0
answers
13
views
Trouble extracting actual ciphertext (attribute "parts") from helib::Ctxt ciphertext
I'd like to access directly to the numbers composing the ciphertext Ctxt from HElib, but reading the documentation I don't seem to find anything that can help me.
I have an object Ctxt containing the ...
0
votes
0
answers
21
views
How $f(x)$ set in ring-lattice crypto?
I want to clear out some confusions I have about Lattice crypto.
As discussed in this talk Signatures, Commitments, Zero-Knowledge, and Applications
For ring $Z_q[x]/f(x)$, I want to understand ...
- 197
0
votes
1
answer
100
views
non-reversible additive cryptographic hash algorithm
I need a lightweight cryptographic hash function which is additive but not reversible, however I'm not sure such a function exists! (it would be better if it works in multisets as well)
By additive I ...
0
votes
1
answer
62
views
Additively homomorphic (modified) RSA?
Is there a way to modify the RSA so that it's homomorphically additive?
I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, ...
- 1
1
vote
0
answers
57
views
Why there is so high computational cost of multiplication in Microsoft Seal?
I was doing some Microsoft Seal testing on my macbook pro (i7) and got following results
Coefficient mod $q = 100$ bits and Polynomial degree $n= 8192$
Ciphertext-Plaintext multiplication takes 0.211 ...
- 197
0
votes
0
answers
17
views
What is minimum size of polynomial modulus in Seal implementation of BFV?
Is there a way to get flexible parameters in Seal for batching? The issue is that for polynomial mod $n=4096$, the function I am computing has a multiplicative depth of $3~4$, to handle noise growth I ...
- 197
0
votes
1
answer
38
views
How to understand noise growth in BFV?
I am trying to understand the noise growth due to multiplication in BFV encryption.
As explained in section 4 and equation 3 of this paper: https://eprint.iacr.org/2012/144.pdf.
I couldn't follow what ...
- 197
0
votes
1
answer
45
views
Difference between Non-Interactive Secure Multiparty Computation (NISMPC) and Fully Homomorphic Encryption (FHE)
Until recently, I only knew about SMPC* and FHE, but now I just encountered the term NISMPC. I was wondering what is their difference and what is their difference in their use cases?
Sometimes in ...
- 280
0
votes
0
answers
18
views
Data encryption or Blockchain in data sharing between *multiple* sources?
imagine several parties that own data, and some of them need to use data of other parties, but have only limited access rights to it. An example:
Party #1 (pharmacy store) needs confirmation from ...
0
votes
0
answers
32
views
Definition of Circuit Depth in Homomorphic Encryption
I am currently trying to get a grasp of homomorphic encryption and are working through the paper by Armknecht et al. (2015): https://eprint.iacr.org/2015/1192 which gives a nice overview and clear ...
- 101
1
vote
1
answer
78
views
What are limits of Modulus Switching in BFV encryption?
I want to understand the limits of modulus switching in BFV.
Lets assume $q$ represents ciphertext modulus and $t$ represents plaintext modulus.
$q$ is set to a $60$ bit value and $t$ is set to $20$ ...
- 197
1
vote
1
answer
35
views
What is Relationship between ciphertext quotient and polynomial degree in RLWE?
In Ring Learning with Errors problem, the size of the ciphertext quotient $q$ decides the size of the polynomial degree $n$ or vice versa. In other words, rlwe problem is hard only when the polynomial ...
- 197
0
votes
0
answers
66
views
EC ElGamal multiplicatively Homomorphic
Can we make EC ElGamal have multiplicative homomorphic property?
- 1
0
votes
1
answer
48
views
Fully Homomorphic Encryption Scheme?
I came up with a rather simple FHE scheme that shouldn't work, but I can't figure out how it breaks. Any help with this is appreciated!
Part one
First, note that if we had an abelian field where ...
- 101
0
votes
0
answers
20
views
How to set context parameters in python homomorphic encryption libraries to work with large numbers
I am trying to work with large numbers in homomorphic encryption libraries in python such as TENSEAL that implemented on top of SEAL. However, i face errors in setting the "context parameters&...
- 11
3
votes
2
answers
157
views
Practical implementations of Private Set Membership
Problem Statement
Imagine you have a set (no duplicate elements) e.g. S1 = {'a', 'b', 'c'}.
You wish to share a private (and ideally both small in size and ...
- 143
2
votes
1
answer
100
views
Fast fully homomorphic arithmetic scheme? BFV = slow bootstrapping, TFHE = slow arithmetic
The BFV scheme is good for representing lots of integers inside a polynomial and we can even operate on them individually relatively fast. However, bootstrapping on BFV is infeasible, such that no ...
- 21
1
vote
1
answer
51
views
Securely sort lists of numbers from two parties
I am looking for ways to securely sort two lists of numbers. Yao's millionaire's problem considers each party with one secrete number and compare them securely. Are there papers on extension to this ...
0
votes
2
answers
91
views
What is a secure, modern, partially homomorphic encryption scheme?
I was reading this paper by Philippe Golle on using the homomorphic properties of ElGamal encryption to play a game of mental poker (i.e. cryptographically secure poker without a trusted third party ...
2
votes
1
answer
106
views
Sparse Subset Sum Problem
In Gentry's seminal results on FHE (https://dl.acm.org/doi/10.1145/1536414.1536440), it is assumed that the sparse subset set problem is hard. It looks like there is a follow up paper on the concrete ...
- 113
0
votes
0
answers
55
views
Are there (fully) homomorphic libraries that implement BFV with bootstrapping?
All libs that I could find like SEAL and LattiGo do not implement BFV bootstrapping. LattiGo for example implements bootstrapping for CKKS, which I heard is not true bootstrapping because you end up ...
2
votes
0
answers
33
views
In BGV scheme, How should I understand FHE.Add?
The following is from BGV paper (https://eprint.iacr.org/2011/277.pdf) p. 12.
$\text{FHE.Add}(pk,\textbf{c}_1,\textbf{c}_2)$: Takes two ciphertexts encrypted under the same $\textbf{s}_j$ (If they ...
- 145
0
votes
0
answers
28
views
Can I operate forever on the CKKS scheme, or there's a limit for re-scaling?
It looks like on BFV, I can always relinearize and keep doing operations on numbers. However, on CKKS, when we multiply 2 values together, their scale gets multiplied also. So we end up having to re-...
0
votes
0
answers
32
views
Are there circuits that operate on plaintext, analogous to how FHE works?
Fully Homomorphic Encryption lets us operate over encrypted data. Is there something analogous that let us operate over plaintexts directly, without knowing the circuit?
For example, let's say that I ...
0
votes
1
answer
50
views
Extracting/learning info from fully homomorphic schemes
On the BFV fully homomorphic scheme, given a polynomial secret key, we can encrypt polynomial plaintexts and generate polynomial ciphertexts.
So, for example, if we have 2 ciphertexts, we can compare ...
- 51
2
votes
1
answer
199
views
What is the difference between the Fully Homomorphic BFV and BGV schemes?
When I read about BFV or BGV, they all look similar: they use polynomials from $\mathbb{Z}[X]/X^n+1$ as secret keys/pubic keys, etc.
What is the main difference?
- 51
0
votes
0
answers
53
views
Control the error bound when using HElib CKKS
I'm using HElib CKKS to do experiments and wondering if it's possible to control the error bound in each basic operation such as multiplication, encoding, and rotation.
I have this question is because ...
- 33
1
vote
1
answer
39
views
single slot operations on SIMD fully homomorphic polynomial
According to https://eprint.iacr.org/2011/133.pdf and many other papers, there's an isomorphsim between the space of polynomials and its coefficients. So, at least in the BFV scheme, we can do:
$$p(x) ...
- 51
3
votes
1
answer
58
views
Can voters be authorities at the same time?
There is an encryption scheme where the votes are encrypted with ElGamal and the decryption key is the secret that is shared among the authorities. After everybody voted they publish their part of the ...
- 131
2
votes
2
answers
188
views
Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?
According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only ...
1
vote
1
answer
204
views
How to Prove Correct Decryption in ElGamal Cryptosystem
I am working on a project that uses ElGamal cryptography using multiplicative notation. The project is an internet voting implementation that uses the cryptosystem to encrypt the received ballots, re-...
1
vote
0
answers
102
views
How to set parameters (i.e., gen, ords and mvec) for bootstrapping in HElib?
I'm using the homomorphic encryption library, HElib, to do experiments.
I tried to use bootstrapping with parameters that are not in the table provided with HElib.
But I have no idea how to choose the ...
- 33
1
vote
0
answers
55
views
Classic secret sharing schemes vs Homomorphic secret sharing schemes
What is the difference between the classic secret sharing schemes that are used in the protocols of Ben-or and Rabin, Ben-Or, M., Goldwasser, S., Wigderson (that is the Shamir's secret sharing scheme) ...
- 261
0
votes
0
answers
36
views
Summarized steps for zero knowledge proof on a public blockchain transaction
Im triying to understand Zero knowledge proof and its applications, my first instict is a blockchain (I will use Bitcoin-like for simplicity sake)
Im triying to wrap my head around it by describing ...
2
votes
1
answer
94
views
How can CPA-secure LWE cryptosystem be broken by an active attacker?
The LWE-cryptosystem is only CPA-secure as for example stated in A Decade of Lattice-Based Cryptography. Consider the following system described there (Section 5.2)
The secret key is a uniform LWE ...
- 337
3
votes
1
answer
170
views
Why are the parameters (such as modulus and dimension) of homomorphic encryption so large?
Compared with the common lattice-based PQC schemes, the modulus $q$ and dimension $n$ of homomorphic encryption are so large. For example, in Kyber, $n=256, n \times k = \{512,768,1024\}$, $q = 12289$...
- 31
0
votes
0
answers
73
views
Homomorphic Encryption Library Supporting Addition, Multiplication & Logical Shift
Does anyone know of a C++ homomorphic encryption library that supports addition, multiplication and logical right shift over integers? Some set of instructions that allows the implementation of ...
- 101
3
votes
1
answer
78
views
What are Practical Primitives based on Lattices, LWE and FHE?
Lattice-based cryptography is being used for several primitives and applications.
I know there are newer works for PIR, PSI, ORAM that have seen tremendous improvements due to FHE. In some cases, FHE ...
- 197
1
vote
0
answers
55
views
Key Switching Error in CKKS
I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have ...
- 8,424
3
votes
0
answers
119
views
The decryption correctness of RLWE based Encryption
I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper.
And the decryption ...
- 33
2
votes
0
answers
51
views
Secure (sub-exponential time) FHE
In Gentry's easy FHE intro, it is stated that
Researchers [1, 8] showed that if $\epsilon$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell ...
- 37.7k
0
votes
0
answers
37
views
Are there any implementations of "More Fun With Funky Plaintext Spaces" from the BGV paper?
Fully Homomorphic Encryption without Bootstrapping describes considerations for large (exponential in the security parameter) integer plaintext spaces in Section 5.4, "More Fun with Funky ...
- 101
1
vote
1
answer
43
views
Is there a secure two party protocol that makes P1 (with x as input) gets rx+r' and P2 gets (r,r')
It should be a secure two party protocol against malicious adversary.
P1's input is X in Zp* (p is a prime number);
P2's input is nothing.
P1's output is rX+r'. r,r' are random numbers from Zp*
P2' ...
- 83
0
votes
1
answer
111
views
Chinese remainder theorem in ECDSA for parameters in secp256k1?
It is known that it is possible to apply the Chinese remainder theorem and attack RSA under precise conditions.
https://tls.mbed.org/public/WSchindler-...
- 3
1
vote
0
answers
62
views
Homomorphic sorting of a vector of FHE ciphertexts
Bonjour à tous,
Je dispose d'un vecteur contenant 15 nombre réel chiffrés avec les schéma de chiffrement homomorphe CKKS. Mon problème est que je souhaite trier ce vecteur par ordre croissant. Je ne ...
- 11
3
votes
1
answer
92
views
Functional and security model for SEAL
What's the functional and security model for SEAL?
From this I get that it
allows additions and multiplications to be performed on encrypted integers or real.
But what are the limitation, like range,...
- 122k
1
vote
1
answer
61
views
Security level of FHE constructions for non-standard parameters
homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.
...
- 197
0
votes
1
answer
36
views
Can Alice verify a guess of Bob's number in this Homomorphic Encryption solution to the millionaire problem
I'm looking at https://link.springer.com/content/pdf/10.1007%2F11496137_31.pdf and it seems like in the protocol they propose if Alice can guess Bob's number, she can pretty easily verify that guess. (...
- 137