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 *).

Filter by
Sorted by
Tagged with
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) = \...
Matias Heikkilä's user avatar
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 ...
Eli Yablon's user avatar
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 ...
August H's user avatar
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 ...
mmazz's user avatar
  • 21
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. ...
DaWNFoRCe's user avatar
  • 872
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 ...
Mastour Ikhlass's user avatar
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 ...
Mastour Ikhlass's user avatar
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 ...
Dimitri Koshelev's user avatar
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 ...
Jingyi Li's user avatar
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 ...
Mona's user avatar
  • 197
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 ...
user97821's user avatar
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_{\...
Daisy Ding's user avatar
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 ...
Daisy Ding's user avatar
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 ...
Aryan's user avatar
  • 1
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 ...
Bastiaan Quast's user avatar
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 & ...
Anon's user avatar
  • 403
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 $...
Doron's user avatar
  • 99
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 ...
ali alizade's user avatar
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 ...
meirgold's user avatar
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 ...
K T's user avatar
  • 21
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 ...
Zarquan's user avatar
  • 313
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. ...
oilyhiccup's user avatar
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/...
slickboy's user avatar
  • 177
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 ...
LWE-13's user avatar
  • 251
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 ...
LWE-13's user avatar
  • 251
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 ...
Bob's user avatar
  • 509
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 ...
Doron's user avatar
  • 99
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 ...
LWE-13's user avatar
  • 251
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 ...
Key Heon Lee's user avatar
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^{\...
R YS's user avatar
  • 1
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) = (...
Rafaelo's user avatar
  • 23
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)...
Doron's user avatar
  • 99
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 ...
John Chadwick's user avatar
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 ...
Jossn Lin's user avatar
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 ...
Shep's user avatar
  • 13
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 ...
Coco's user avatar
  • 11
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 ...
fakub's user avatar
  • 181
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?
LWE-13's user avatar
  • 251
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 ...
LWE-13's user avatar
  • 251
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 ...
Amid Moeinzadeh's user avatar
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, ...
Arya513's user avatar
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 ...
LWE-13's user avatar
  • 251
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 ...
LWE-13's user avatar
  • 251
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 ...
tur11ng's user avatar
  • 962
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$ ...
LWE-13's user avatar
  • 251
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 ...
LWE-13's user avatar
  • 251
0 votes
0 answers
145 views

EC ElGamal multiplicatively Homomorphic

Can we make EC ElGamal have multiplicative homomorphic property?
jeljeli's user avatar
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 ...
Eli Yablon's user avatar
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 ...
JoeKir's user avatar
  • 143
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 ...
PPP's user avatar
  • 21

1 2
3
4 5
18