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 *).
791
questions
0
votes
0
answers
10
views
meaning of "zero-padding and split" procedure in HEAAN-RNS
I don't understand the meaning of step2-1 in Better Bootstrapping for Approximate Homomorphic Encryption. I understood all other parts of the algorithm. However, I have no idea why we need the "...
- 1
2
votes
0
answers
39
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 & ...
- 311
1
vote
0
answers
44
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 $...
- 59
0
votes
0
answers
62
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 ...
- 21
0
votes
0
answers
32
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 ...
- 1
0
votes
0
answers
29
views
Off-loading bigint multiplication from zk-SNARK using Pedersen commitment
Background
I'm working on a scheme that could "off-load" some computation from a zk-SNARK. That is,
we do some computation publically without revealing the private values using partially ...
- 21
2
votes
2
answers
117
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 ...
- 21
0
votes
0
answers
41
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 ...
- 166
0
votes
0
answers
50
views
Why g is 2 and 3 to derive the lambda and beta values for endomorphism on the secp256k1 curve?
As you can seen here, in hex, N and P are:
N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
The ...
- 1
0
votes
1
answer
48
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.
...
0
votes
0
answers
11
views
Algorithms to secretly distribute elements from a known set / with a known global characteristic
I am assuming a set of $n$ players and a central "dealer" $C$ through which all communication is routed. The state I want to end up with is that each player $i$ has a secret $s_i$ unknown to ...
- 1
1
vote
1
answer
32
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/...
- 177
2
votes
0
answers
24
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 ...
- 239
0
votes
1
answer
44
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 ...
- 239
2
votes
1
answer
97
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 ...
- 419
0
votes
1
answer
36
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 ...
- 59
0
votes
0
answers
23
views
Understanding LSB extraction
I am not able to understand LSB extraction as explained in protocol 3.4 of this paper
Improved Primitives for Secure Multiparty Integer Computation
Specifically, the protocol samples random number $r'...
- 239
0
votes
1
answer
42
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
...
- 239
1
vote
0
answers
56
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 ...
- 21
0
votes
1
answer
62
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^{\...
- 1
0
votes
1
answer
142
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) = (...
- 13
1
vote
0
answers
46
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)...
- 59
0
votes
0
answers
27
views
Is there a general scheme for the comparison of homomorphic ciphertext？
Regarding the homomorphic comparison problem, I want to use the result of homomorphic subtraction to represent the size of the two homomorphic secret texts.
The problem is that even if bootstrapping ...
- 1
1
vote
1
answer
78
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 ...
- 111
0
votes
1
answer
21
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
29
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 ...
- 13
1
vote
0
answers
48
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 ...
- 11
5
votes
1
answer
131
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 ...
- 181
1
vote
0
answers
55
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?
- 239
0
votes
0
answers
41
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 ...
- 239
0
votes
0
answers
37
views
Bilinear map and homomorphic inner product
This is a question related to homomorphic inner product as discussed here:
Inner product with homomorphic encryption
I browsed through the recommended papers and I have just a major
Stumbling block ...
0
votes
0
answers
28
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 $...
- 419
0
votes
0
answers
48
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
22
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
26
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 ...
- 239
0
votes
1
answer
117
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
74
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
79
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 ...
- 239
0
votes
0
answers
38
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 ...
- 239
0
votes
1
answer
74
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 ...
- 239
0
votes
1
answer
57
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 ...
- 673
0
votes
0
answers
19
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
63
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
143
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$ ...
- 239
1
vote
1
answer
50
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 ...
- 239
0
votes
0
answers
83
views
EC ElGamal multiplicatively Homomorphic
Can we make EC ElGamal have multiplicative homomorphic property?
- 1
0
votes
1
answer
65
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 ...
- 133
0
votes
0
answers
38
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
243
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
210
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