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 *).
872
questions
0
votes
0
answers
19
views
I'm wondering if using the same one public key does not guarantee privacy in the computation of multiple data owners
Participating entity: multiple data owners, computing clouds
Protocol: The multiple data owners send their data to the computing clouds, which perform the computation of the data.
Privacy protection:...
- 161
1
vote
0
answers
64
views
Understanding Gentry's initial FHE construction based on ideal lattices
I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
- 111
0
votes
0
answers
19
views
convert from integer to polynomial ring in BFV homomorphic algorithm
BFV algorithm is one type of fully homomorphic encryption algorithms, how can I encoding integer to polynomial ring by using batch encoder based on Rt:=Zt[X]/⟨(X^n)+1⟩, the plaintext space (R mod t) ...
- 1
0
votes
0
answers
15
views
[error reducing techinique in lattice based commitment]
I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
- 327
1
vote
1
answer
46
views
Decryption of Naccache–Stern cryptosystem is not guaranteed for large keys
Naccache-Stern cryptosystem is mainly based on Chinese Remainder Theorem. According to its wiki page and Partially Homomorphic encryption book, I generated following keys.
1- Picked a family of k ...
- 229
0
votes
0
answers
22
views
Understanding and Implementing fast base conversion (FastBConv, bconv) in Mathematica
According to Section 2.3 of Full-RNS CKKS:
More precisely, for a basis $ \left\{p_{0}, \ldots, p_{k-1}, q_{0}, \ldots, q_{\ell-1}\right\} $, let $ \mathcal{B}=\left\{p_{0}, \ldots, p_{k-1}\right\} $ ...
- 101
0
votes
0
answers
47
views
merging structured encrypted data
this is a followup of the post I made there: https://stackoverflow.com/questions/77428690/merging-structured-encrypted-data
Essentialy, I'd like to know if there is a way to merge bencoded data (or ...
- 1
1
vote
1
answer
45
views
Homomorphic encryption with multiple keys that is secure under the assumption of a compromise of the combined key
Is it possible to extend the general concept of homomorphic encryption:
$$f(m_1)\cdot f(m_2)=f(m_1+m_2)$$
to:
$$f(m_1)\cdot g(m_2)=f\cdot g(m_1+m_2)$$
is it further possible to construct the scheme in ...
- 123
1
vote
1
answer
43
views
Why the refresh (modulus and key switching) is required in BGV after addition?
I am reading the BGV paper. On page 18, after addition, the protocol will also refresh (modulus and key switching), may I ask why is this required? It seems to me that I can still use the same secret ...
- 327
1
vote
1
answer
57
views
in Homomorphic Encryption Standard, why in the LWE increasing security level yields smaller ciphertext?
I am currently reading Homomorphic Encryption Standard. May I ask that for table 1 in the link, why increasing the security level will yield a smaller ciphertext size (log q)?
I attach a screenshot ...
- 327
0
votes
0
answers
38
views
[About choosing params in BGV like ciphertexts]
I am new to lattice-based cryptography, so sorry that this question might seems stupid
May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
- 327
0
votes
0
answers
40
views
Question about the bootstrap of BFV
The description of bootstrapping in Section 5 of the BFV paper (https://eprint.iacr.org/2012/144) is somewhat challenging to grasp, and I have two specific questions:
The author mentions that if the ...
- 21
0
votes
0
answers
34
views
Approximate-GCD problem in polynomials
I am trying to understand the two main hard problems that have been explored in the context of homomorphic encryption: Learning with Errors Problem (LWE) and the Approximate-GCD (AGCD) problem. I have ...
- 11
1
vote
2
answers
112
views
About multiply by constant of LWE
I am new to lattice-based cryptography
May I ask that for a lattice-based encryption
$$enc(m) = A^{T}R+m \bmod q$$
If I set the $q$ to be able to decrypt to $m$ (and suppose the bound of $q$ is tight ...
- 327
0
votes
0
answers
19
views
Metrics for difference/error of output and ideally output
I'm working in some homomorphic encryption for my Ph.D. but I'm not of the field... So I'm possible going to ask a really simple question that I'm struggling to find an answer on the internet.
...
- 21
0
votes
0
answers
35
views
question for lemma 4 of the BGV paper
I would like to ask a question that arose when reading the proof of lemma 4 on page 10 of this BGV paper:
The assumption is:
And the inequality:
So it seems that
$$ \sum_{j=1}^{n} \parallel c'[j]-(p/...
- 327
0
votes
1
answer
167
views
Is there any cheaper way for multiplying a plaintext scalar to a vector?
Assume I am using the SIMD encryption of homomorphic encryption. Performing plaintext-ciphertext multiplication between two vectors $\mathbf{a}$ and $\mathbf{x}$ means
$Dec(\mathbf{a} \times Enc(\...
- 35
1
vote
1
answer
102
views
Could Yao's Millionaires' problem be used as a problem of binary search?
I recently started reading about Yao's Millionaires' problem. If the Yao's Millionaires' problem is capable of finding if one party has less money / more or equal money than the other party, then is ...
- 33
0
votes
0
answers
51
views
Understanding noise budget calculation in seal
I am trying to understand theory behind noise budget operation implemented in seal
Let the ciphertext be defined as
$$
c0=A \in Rq \\c1= As+v+delta*m \in Rq
$$
They first calculate noise ...
- 251
0
votes
0
answers
20
views
Noise of Public Key Ciphertexts in HElib
I would like to get a feeling on how the noise develops in different FHE schemes. So I ran some experiments using HElib for both BGV and CKKS. I wanted to look at the noise of a fresh public key and a ...
- 1
2
votes
1
answer
112
views
Statistics-heavy crypto papers
I'm currently taking a course in which we choose a stats-heavy paper and analyse it, summarising our work in the form of a written report and presentation. I have tried to find such a paper in crypto, ...
1
vote
0
answers
19
views
Does exist an Elliptic analogue of Benaloh encryption scheme?
The definition of Benaloh encryption scheme can be found here.
Does exist an elliptic analogue of this scheme?
I want to use this scheme but the length of the key ...
- 175
1
vote
1
answer
83
views
How does the key generation of a homomorphic secret-sharing protocol works?
I am new to cryptography and do not have sufficient background knowledge, and I am sorry for any possible vagueness in my question.
I am reading a paper (https://eprint.iacr.org/2019/129.pdf) about ...
- 13
0
votes
1
answer
27
views
What is the meaning of X is of order 2N in blind rotation of TFHE?
Could anyone please help me explain this?
I am reading the article about TFHE (Guide to Fully Homomorphic Encryption over the [Discretized] Torus).
On page 31:
I don't understand why we need to scale ...
- 3
1
vote
2
answers
67
views
Orthogonal Lock
Is there a cryptographic function that employs two locks: first 'Lock A', and then on top of that 'Lock B' but it permits unlocking 'Lock A' before 'Lock B' to read the message?
- 11
2
votes
1
answer
64
views
Is it possible to perform an unlimited amount of multiplications on the same ciphertext in fully homomorphic encryption?
I am currently playing around with some of the Python FHE libraries and found out that, e.g. TenSeal (SEAL) is able to perform "only" 8 ciphertext-ciphertext multiplications on the same ...
- 23
1
vote
1
answer
62
views
Homomorphic Encryption CKKS scheme, Encoding: canonical embeding discretization
I'm trying to understand CKKS (non bootstrappable) and I'm struggling with the encoding part.
I'm using the original paper , "Homomorphic Encryption for Arithmetic of Approximate Numbers
", ...
- 21
1
vote
1
answer
67
views
Can you instantiate Ring-LWE with coefficients from a prime-power field?
Generally, we instantiate Ring-LWE with the polynomial ring $R = \mathbb{F}_q\ /\ (X^N+1)$ for prime $q$ and some power-of-two $N$.
Can we instead do Ring-LWE over the ring $R = \mathbb{F}_q\ /\ (X^N+...
- 11
2
votes
1
answer
114
views
How to determine the homomorphic encryption CKKS scheme's parameter bounds for correctness and 128-bit security?
How to determine the homomorphic encryption CKKS scheme's parameter bounds for correctness and 128-bit security using some specific floating-point numbers and specific computation metrics like ...
- 53
0
votes
0
answers
12
views
Why does TFHE/Concrete only support <8 Bit numbers?
It seems to have something to do with their bootstrapping technique, that is build on blind rotations, but I fail to see why less than $8$ bits are used.
- 43
0
votes
1
answer
44
views
Relationship between the scaling factor and polynomial degree in CKKS variant of homomorphic encryption?
I have come across the TenSEAL tutorial on implementing homomorphic encryption (HE) and they mention the global_scale parameter.
(https://github.com/OpenMined/TenSEAL/blob/main/tutorials/Tutorial%202%...
- 101
0
votes
1
answer
72
views
The relationship between polynomial degree and HE performance [closed]
any paper mentioning the performance decreases with N?
why when N is increasing, the performance decreases? any papers?
BR
- 53
0
votes
1
answer
60
views
Combining decryption function with transformation in a way that can't be reversed
I have a program implementing a function $f$, and want to find a pair of functions $e$ and $h$ such that $h \circ e = f$, but $e^{-1}$ cannot be recovered from $h$.
In other words, given some $e$-...
- 3
-1
votes
1
answer
51
views
Simple Precomputed Ciphertext operations table instead of Homomorphic encryption
Let's say I want to perform addition on "small" numbers (if it matters, let's say integers between 1-10K) without decrypting the numbers -- i.e. I have ...
- 74
1
vote
0
answers
182
views
Quantum-safe algorithm for hiding cryptocurrency transaction amount [closed]
I have a decentralized coin system that I am trying to develop.
Each coin can be split up into 1,000,000 units.
I've been looking for a quantum-safe and practical (efficient) algorithm to send ...
- 91
-1
votes
2
answers
76
views
How to calcualte the average of several plaintexts with Paillier homomorphic encryption?
I am trying to do some calculations with the Paillier Homomorphic encryption scheme. Specifically, given three plain text integers, x1, x2,and ...
- 1
0
votes
1
answer
76
views
Homomorphic Encryption - Integer modulus in HEAAN and key sampling
I am trying to wrap my head around Homomorphic encryption, specifically the HEAAN/CKKS scheme. I am reading through the publication, but I am getting stuck on page 11, namely the KeyGen and Enc ...
0
votes
1
answer
35
views
Transform a large integer to Plaintext ERROR in SEAL Library
In SEAL library, I want to multiply a BFV ciphertext ct with an integer inverse. Here are what I do:
Compute the integer inverse as follows:
...
- 1
0
votes
1
answer
42
views
About learning with error rings with only constant coefficient
I am new to RLWE, would like to ask whether what I am thinking make sense
Suppose I have a message e.g.: x=5
And I have a lattice based encryption scheme, e.g.: BGV
could I encrypt x with BGV by ...
- 327
0
votes
1
answer
66
views
Trustless voting where the total number of votes each candidate get is kept private
Given n voters and p candidates, how can we design a trustless voting algorithm that satisfies the following properties. Each voter can only vote for exactly one candidate.
The algorithm needs to:
...
- 101
0
votes
2
answers
94
views
Securely computing the addition of n numbers owned by n people
Assume that we have n people each owning a secret number. Now we want to collaboratively compute the addition of all these numbers without anyone revealing their numbers. Then the result will be made ...
- 101
2
votes
1
answer
210
views
Using embeddings to anonymize information
This might be a stupid question, so bear with me. I was wondering if LLM embeddings can be used to anonymize input text. I couldn't find any information online that says that embeddings can be 1:1 ...
- 123
0
votes
0
answers
53
views
Homomorphic Encryption CKKS scheme: How library SEAL represents in memory a Ciphertext
I'm trying to understand how its represented a ciphertext of CKKS in memory, or the data structure.
Here is what I understand, correct me if I'm wrong. I also add some questions.
To start with, given ...
- 21
0
votes
1
answer
41
views
Fast Private Set Intersection from Homomorphic Encryption
I encountered a question while reading an article. My understanding is that fully homomorphic encryption supports ciphertext addition and multiplication. Why does the basic protocol given in this ...
- 1
3
votes
1
answer
98
views
Verify HMAC tag without knowing the key
Let's say there's Alice and Bob.
Let Alice and Bob agree on a message $M_1$, a tag $T_1$, and a function $HMAC$.
Alice proves to Bob that she knows a key $K$ such that $T_1 = HMAC(M_1, K)$ without ...
- 345
0
votes
1
answer
70
views
Two problem about noise management of BFV
I have stuck in two problems when understanding the noise management of BFV scheme, and I don't have any idea about the two problem, help me please.
Problem 1:
In the ...
2
votes
2
answers
99
views
Homomorphic encryption with both algorithm and data encrypted?
Is it theoretically possible to use homomorphic encryption to run an encrypted algorithm over encrypted data?
If this is not possible, is it at least possible to run an encrypted algorithm over plain ...
- 139
4
votes
1
answer
115
views
Does the plaintext modulus have to be prime in BGV?
I'm thinking about storing packed integers $(x_1,x_2,...,x_k)$ into a single ciphertext slot using the Chinese Remainder Theorem (CRT). However, in order for the CRT to work, the plaintext modulus ...
- 73
2
votes
1
answer
80
views
Security of RLWE encryptions of secret keys
Under which conditions is it secure to publish an encryption of the secret key $s$ under itself in terms of an $RLWE_s(s)$ ciphertext? Because for some schemes this is (repeatedly) used in ...
- 43
2
votes
0
answers
65
views
To prove equality/inequality of plaintexts of 2 ciphertexts encypted under different encryption schemes
We have 2 ciphertexts, one encrypted using Paillier and another encrypted under Elgamal encryption schemes. Is there a way to design ZK-proof to prove equality of the underlying plaintexts of these 2 ...
- 21