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 *).
889
questions
1
vote
2
answers
123
views
Why is FHE nontrivial?
If I understand correctly (please let me know if any of the following is wrong), a fully homomorphic encryption scheme $\mathcal{E}$ is such that for any messages $x, y$,
$$
\mathcal{E}(x + y) = \...
1
vote
1
answer
330
views
Plaintext Multiplication in BFV
In this paper I'm reading (specifically section 3.1), the authors say that the BFV encryption scheme supports plaintext multiplication, which basically means that given a ciphertext, $c$ that is an ...
0
votes
1
answer
94
views
How are arbitrary boolean gates constructed in homomorphic encryption using only addition and multplication?
I've recently become interested in homomorphic encryption, specifically how boolean gates are constructed to do arbitrary circuit arithmatic on the encrypted data without decrypting it.
I have heard ...
0
votes
1
answer
129
views
CKKS encoding notation and doubt with why project to base
I'm trying to understand CKKS (non bootstrappable) and I'm struggling with the encoding part. Particularly with to questions.
I'm using the original paper , "Homomorphic Encryption for Arithmetic ...
1
vote
0
answers
87
views
MPC Protocol with Additions and Multiplications for FREE
Imagine an MPC protocol where both multiplications and additions come for free (2 round). The protocol works over arithmetic circuits, and the security setup is as relaxed as possible:
Semi-Honest.
...
1
vote
0
answers
61
views
Using additive secret sharing to share the secret key of BFV scheme among $N$ participants
I want to share the secret key of the BFV scheme among N users using the additive secret-sharing protocol (n-out-of-n threshold secret-sharing). Can anyone please help me to adapt the two algorithms ...
2
votes
0
answers
109
views
How can I use additive secret sharing to share the secret key of BFV scheme among $N$ participants?
I want to share the secret key of the BFV scheme among N users using the additive secret-sharing protocol (n-out-of-n threshold secret-sharing). Can anyone please help me to adapt the two algorithms ...
2
votes
1
answer
174
views
Dense sphere packings and lattice-based cryptography
It is known that there are two popular applications of lattices: dense sphere packings and lattice-based cryptography. I didn't find any information on the Internet about possible interaction of these ...
0
votes
0
answers
119
views
Can we calculate absolute value function in homomorphic encryption efficiently?
Is it feasible to efficiently calculate a homomorphic absolute value function over ciphertext given a pair of numbers $a$ and $b$, i.e., |a-b|? Although there are approximate methods that use addition ...
2
votes
1
answer
273
views
Shamir's secret sharing homomorphism for different degree polynomials
The $(t,n)$ Shamir’s polynomial based secret sharing scheme is $(+,+)$-homomorphic in which the addition of two polynomials secrets equals the Lagrange’s interpolation of the sum-of-shares for the ...
1
vote
1
answer
110
views
What arithmetic operations are supported from fully homomorphic encryptions(FHE)?
I'm wondered about what arithmetic operations are supported from FHE.
I want to know for 2nd Gen(BGV,BFV), 3rd GEN(GSW,CGGI), 4th GEN(CKKS)!
Is 3rd can support more than and/or/not? I heard it is for ...
2
votes
0
answers
32
views
Does homomorphic operations have to process one level by one level in BGV?
Suppose the highest level is $L$. There are 2 ciphertexts from 2 different messages under the same secret key but in different level, one is in level $\ell$: $\mathsf{ct}(\pmb{m})\in\mathcal{R}_{Q_{\...
2
votes
2
answers
467
views
How to understand these concepts in HE: Bootstrapping, Modular Switching, Key Switching, Evaluation, Relinearization?
I want to distinguish different concepts: Bootstrapping, Modular Switching, and Key Switching. I am also sometimes confused about Evaluation & Relinearization.
My understanding of these concepts ...
0
votes
0
answers
88
views
Can two ciphertexts that decrypt to the same plaintext be statistically "distant"?
It might be a little dumb: I think it should be possible, if I encrypt a plaintext using the same public key twice, it should be possible to end up with two ciphertexts that for whom the statistical ...
1
vote
0
answers
523
views
For integers, when should I use BFV / BGV / CKKS / TFHE?
When performing homomorphically encrypted computations, when should I use BFV / BGV / CKKS?
It seems BFV / BGV is better suited for integers, and CKKS for floats. It also seems BFV-BGV have some ...
2
votes
0
answers
113
views
Regev PKE not CPA secure for specific $A$?
I encountered notes stating that, for certain fixed $A$, such as $A \in M_{n\log(q)\times n}$ as follows:
\begin{bmatrix}
1 & 0 & 0 &\dots\\
2 & 0 & 0 &\dots\\
4 & 0 & ...
1
vote
0
answers
52
views
Is it possible to execute multi party computation over public ledger?
Let $F(x_1,…,x_n)\mapsto(y_1,…,y_n)$ be some arbitrary computable function.
Suppose there are $n$ parties, where each party $i$ encrypt its message $m_i$ with a public key $\mathrm{pk}_i$ and obtain $...
0
votes
0
answers
108
views
Is there a special limit in the range of the hash function?
Is there a special limit in the range of the hash function?
More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set?
In ...
0
votes
0
answers
124
views
What is the recommended way to use fully homomorphic encryption which supports numpy matrix operations?
For a project I'm working on, I need to perform addition, subtraction and dot operations on relatively large encrypted 2x2 dimensional matrices.
The project is written in python and I am using the ...
2
votes
2
answers
169
views
Examples of systems using partially homomorphic schemes
Background of the question:
I’m working on constructing a cryptosystem to achieve a specific goal that could utilize partially homomorphic schemes. (details of the cryptosystem are out of the scope ...
0
votes
0
answers
89
views
Semantically secure RSA with Multiplicative Homomorphism
Most real-world RSA implementations add padding and such that break the multiplicative homomorphism of raw RSA. However, this multiplicative homomorphism can be useful.
I haven't seen any existing ...
0
votes
1
answer
65
views
Encrypting data before Saas-solution
The compliance department is asking me for recommendations on encrypting data before Saas-solutions. Meaning that the Saas-solution should not be able to see the data when stored and processed.
...
1
vote
1
answer
94
views
Is it possible to use Batching with any of the Partial Homomorphic Cryptosystems?
I'm familiar with the concept of batching in the context of (Fully) Homomorphic Encryption - whereby many values can be encrypted as a single ciphertext and operated on simultaneously in an SIMD/...
2
votes
0
answers
109
views
SIMD mode for RGSW encryption?
I know schemes like BFV, BGV, and CKKS supports SIMD operations where the plaintext is vector of values instead of polynomial. I am wondering if RGSW/TFHE kind of schemes can also support SIMD ...
1
vote
1
answer
81
views
How to hide result of FHE?
Lets say we are given BFV encryption of x, let this encryption is represented as E(x). In FHE, the client can decrypt and get ...
2
votes
1
answer
439
views
How to choose the large noise when using noise flooding technique in FHE?
In LWE based multi party FHE schemes, the parties should choose a much larger noise when perform joint decryption. In this paper, the author just said that using noise flooding technique to avoid the ...
0
votes
1
answer
54
views
Transforming a encryption of binary representation of a number to an encryption of vector representation
Suppose Alice chooses a number $n\in Z_q$ and decompose it to its binary representation $b_0,b_1,...,b_d$. Then Alice encrypts these bits (can be any encryption scheme). Is it possible for Bob (who ...
0
votes
1
answer
83
views
Millionaire problem where one entry is public?
I want to evaluation following functionality:
Parties have secret shares of private input [a] and public input b, they want to measure if
a>b, additionally only one party should learn the output
...
1
vote
0
answers
97
views
Additive Homomorphic Encryption scheme with very small ciphertext size
I'm looking for a Additive Homomorphic Encryption scheme which can allow a ciphertext of size smaller than 128 bit.
I started studying this topic very recently so I don't have much knowledge, but I ...
0
votes
1
answer
108
views
Does the Saber.PKE algorithm submitted in PQC NIST Round3 support the additional homomorphism?
As for the PQC algorithm Saber.PKE based on M-LWR, I wonder whether it supports homomorphic addition operation. According to my related work, the error of this algorithm can be written as $e_S = ||s^{\...
0
votes
1
answer
179
views
Can I subtract 2 ciphertexts in FHE exactly?
In most FHE schemes, for a polynomial $m_1$,
$$enc(m_1) = a_1*s + e_1 + m_1$$
Suppose I have $enc(m_1),enc(m_2)$. Can I subtract them exactly? Sum works, but subtraction is:
$$enc(m_1) - enc(m_2) = (...
1
vote
0
answers
70
views
Compute a hash function given commitment to some secret element
Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
3
votes
3
answers
276
views
Is it possible to prove that an encrypted message was encrypted with some public key without divulging the plaintext or secret key?
I know this seems a bit contrived, but I’m a layperson to cryptographic systems and have been trying to think if it’s possible to devise a scheme where it’s possible for a sender to prove, in a public ...
0
votes
1
answer
53
views
Why does the distribution of BFV's sk use $R_2$, and what are the disadvantages of using $\chi$?
Instead of sampling $\mathbf{s},\mathbf{u} \gets \chi$, we will sample $\mathbf{s},\mathbf{u}$ from $R_2$, i.e. the norm $||\mathbf{s}||=||\mathbf{u}|| = 1$.
$\cdots$.
The security implications of ...
1
vote
1
answer
41
views
On using interaction to achieve FHE from old PHE schemes
Suppose we have A and B, e.g. a user a server, where A encrypts data to be processed by B homomorphically.
It seems that we could construct a pseudo-fully homomorphic encryption system---prior to ...
1
vote
0
answers
71
views
Is there any function that calculates Frobenius Norm in palisade? (Homomorphic encryption)
As I understand, Frobenius Norm is supported under homomorphic encryption. (It’s HE compatible.) However, I cannot seem to find the corresponding function in palisade’s library and documentation. Or ...
5
votes
1
answer
276
views
Addition-Subtraction Chains with cheap or free doubling
Related Problem
Standard Addition-Subtraction Chain (ASC) for an integer $k$ defines the order of addition/subtraction (doubling) operations so that $k$ is finally reached, starting with $1$.
This is ...
1
vote
0
answers
149
views
Where there is special Modulus in Microsoft Seal?
As explained in their example here, Microsoft Seal uses a special modulus that is used for all key material like relinearization key. I wanted to ask why special modulus is used?
0
votes
0
answers
201
views
Why use cyclotomic polynomials for RLWE?
This paper On Ideal Lattices and Learning with Errors Over Rings proposed RLWE which is Ring and hence efficient version of LWE problem. My question is that they considered cyclotomic polynomials for ...
1
vote
1
answer
175
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
247
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
vote
0
answers
123
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 ...
0
votes
1
answer
197
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 ...
0
votes
1
answer
126
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 ...
1
vote
1
answer
349
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$ ...
1
vote
1
answer
110
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 ...
0
votes
0
answers
145
views
EC ElGamal multiplicatively Homomorphic
Can we make EC ElGamal have multiplicative homomorphic property?
1
vote
2
answers
218
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 ...
3
votes
2
answers
526
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 ...
2
votes
1
answer
546
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 ...