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 *).
742
questions
2
votes
2answers
63 views
+100
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 ...
0
votes
0answers
32 views
Need help to implement Semi-Honest protocol [closed]
I want to implement Semi-Honest protocol proposed by Freedman and others in python. The code is shown below. However, I could not understand the result after decrypting. Please could you explain me, ...
1
vote
1answer
142 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
0answers
47 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 ...
1
vote
0answers
41 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) ...
0
votes
0answers
25 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
1answer
74 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 ...
3
votes
1answer
144 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$...
0
votes
0answers
69 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 ...
3
votes
0answers
58 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 ...
1
vote
0answers
26 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 ...
3
votes
0answers
107 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 ...
2
votes
0answers
45 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 ...
0
votes
0answers
35 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 ...
1
vote
1answer
37 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' ...
0
votes
1answer
79 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-...
0
votes
0answers
50 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 ...
3
votes
1answer
87 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,...
1
vote
1answer
53 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.
...
0
votes
1answer
34 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. (...
0
votes
2answers
68 views
Pailler cryptosystem safety
I am working on system which can calculate average salary for different positions in large companies I want to use pailler schema to do such calculation.
I have 3 fields which I want to encrypt:
...
1
vote
0answers
50 views
Formal Verification for Multiparty Computation and Homomorphic Encryption?
I've recently found some work on the use of Formal Verification Software, like ProVerif for enclaves. I wonder is if its feasible to have something similar for MPC and Homomorphic Encryption and ...
1
vote
0answers
22 views
Is it possible to Publicly Query Privately Held Data with proof of Correctness?
We can secretly query inputs from a public DBs using what we call in the literature PIR. We can secretly query inputs from a privately held DB by means of Private Set Intersection (PSI). We can also ...
1
vote
1answer
76 views
How does batching in FHE work?
Let's say we have a BGV style homomorphic encryption scheme. The message space will be the ring $$R_p = \mathbb Z_p[x]/(x^d + 1)$$ where $p$ is a prime congruent to $1$ modulo $2d$. Now let's say we ...
0
votes
0answers
27 views
Verify encrypted signature using encrypted version of publickey without decrypt them
I try to explain the problem (maybe it's trivial): is there a way to do the following: sign a message with private key, send encrypted version of signature and an encrypted version of publickey to ...
3
votes
1answer
102 views
$n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security
For example, Paillier's RSA modulus is $n=pq$, but OU's RSA modulus is $p^2q$. I think when two $n$ are the same, the security of the two cryptographic schemes must be different. So for example, if I ...
1
vote
1answer
52 views
Multi-party Millionaire's variant: how to find the highest number without revealing who holds it?
Let's say that $n$ honest-but-curious parties each hold a value $x_i$. The parties want to learn what is the maximum value across the parties $\{x_1...x_n\}$ without sharing their values (unless they ...
-1
votes
1answer
60 views
Is there some function of $n$ that is a multiple of $\phi(n^2)$?
Not sure which forum to post this question so here is a link to it from MSE.
This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system.
I understand that this will ...
3
votes
1answer
99 views
Does asymmetric order-preserving encryption exist?
As I understand from this post, mapping from plaintext space to ciphertext space is the fundamental point of all order-preserving encryption. So the only way that we let someone encrypt an arbitrary ...
0
votes
0answers
31 views
For a given security parameter $\kappa$. what does $poly(\kappa)$ mean?
Let ($Gen,Enc,Dec$) be an LHE scheme with security parameter $\kappa$ and
message space $M$. Assume that a multiplication operation exists in $M$,
i.e., is a finite ring. Let $F : \{0, 1\}^s × L → M$ ...
0
votes
0answers
28 views
HElib: send sk and pk to another party for decryption and encryption
This question is about the serialization of pk, sk, and context in HElib.
In my scenario, ...
0
votes
0answers
21 views
How to understand the per-gate computation overhead of the FHE scheme?
In BGV12(Fully Homomorphic Encryption without bootstapping), they investigate the efficiency of a FHE scheme by considering the per-gate computation overhead of the FHE scheme, defined as the ratio ...
1
vote
0answers
61 views
How does bootstrapping work?
I have read FHE lately. In Fully Homomorphic encryption using ideal lattice[Gen09], I noticed his recrypt algorithms:
We have a ciphertext $\phi_1$ which is encrypted by public key $pk_1$, and can be ...
0
votes
0answers
61 views
What's the performance of the HElib and SEAL?
HElib contains the CKKS and BGV, SEAL contains the BFV and CKKS, is there some concrete performance data about these two lib?
0
votes
0answers
39 views
Is it possible to allow a user to log in if logged out without identifying them?
I have to verify that the user has registered and is currently logged out without identifying the user. Essentially, I am looking for privacy-oriented authorization mechanisms which prevent ...
1
vote
1answer
86 views
SS/HE/GC/OT secure integer comparison
I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in ...
0
votes
1answer
56 views
Simple question about BGV scheme
While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding:
Let $p$ be a plaintext modulus and $q$ be ...
1
vote
0answers
63 views
Homomorphic encryption key switching
I understand the general idea of key switching, but I would like to know when it is used. Sometimes it is referred to as same thing as relinearisation(after multiplication), but is key switching also ...
0
votes
1answer
39 views
How to know the exact result in Paillier chiper-costant multiplication
The encryption function $E_{k^+}: Z_n \rightarrow Z_{n^2}$.
The decryption function $D_{k^-}: Z_{n^2} \rightarrow Z_n$.
$m_1 = 42, k = 15, n=77$.
After encryption, exponentiation and decryption, I get:...
2
votes
0answers
45 views
RLWE like problem
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$.
Let $s \gets R_q$ be a ...
0
votes
1answer
52 views
An implementation about multi thread TFHE
recently I'm trying to use TFHE library for project(https://tfhe.github.io/tfhe/). In order to accelerate the whole program, I use pthread to make multi thread computation. However, I find that the ...
0
votes
1answer
83 views
Joint distribution of RLWE samples
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. We draw samples $s_i \gets R_q$ uniformly at random. Additionally, we define the error distribution $\chi$ as a discrete ...
1
vote
0answers
18 views
Proving the security of the public key BGV scheme
The security proof basically comes down to the following based on this paper.
We want to show that two distributions are statistically indistinguishable.
Say we have that $a,a′,x,x′$ are drawn from an ...
2
votes
2answers
120 views
Role of AND operation in FHE, MPC and ZK
Going through LowMC, one of the main advantage of it seems to be useful in Fully Homomorphic Encryption (FHE), Multi-party Computation (MPC) and Zero Knowledge (ZK) proofs. I have no idea about any of ...
1
vote
0answers
36 views
CKKS : Ciphertext extension
I have a CKKS ciphertext containing [a, b, c, d] and I want to get these 4 ciphertexts : [a, a, a, a]; [b, b, b, b]; [c, c, c, c]; [d, d, d, d].
Is there a more efficient way than repeating the ...
0
votes
0answers
60 views
Rotation with redundant slots in HElib
As described in another question How to get exact number of slots in HElib?, get the exact number of slots with relative small parameters m and ...
0
votes
0answers
28 views
What is the evaluation step in an HE scheme? [duplicate]
I quote:
By homomorphic encryption, we mean the family of encryption schemes
being able to perform homomorphic operations on ciphertexts, without
decrypting them. The first time someone introduced ...
2
votes
0answers
42 views
Palisade: EvalMult between plaintext and ciphertext resulting in tower size mismatch
I hope someone can help me understand an error I get when using Palisades. I want to only use the first 329 slots of a BGV ciphertext, and zero out the rest (which at some point contains some '...
1
vote
1answer
58 views
How to understand why an algorithm uses additive or multiplicative homomorphic
If we take the example of LWE (Learning With Errors) how does one know if it's homomorphic by addition or multiplication?
0
votes
0answers
52 views
A question about HElib again
Sorry but I've got a question about HElib again. I'm applying HElib to make a secure logical calculation and I apply bootstrapping as usual. Paras I selected was from "example". However, ...