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
0 votes
0 answers
53 views

Difficulty of factoring large semiprime N if given a second value y = (p-1)*r, where r is a random large prime?

Lets say we have 2 public values: N and y $$ N = pq $$ $$ y = r(p-1) $$ Where p, q, and r are large primes, are different, have a large distance between them and are kept secret. I have three ...
block103's user avatar
1 vote
1 answer
64 views

Is it possible to homomorphically evaluate an encryption circuit?

I know that it is possible to homomorphically evaluate a decryption circuit as it is the main idea behind bootstrapping, but I was wondering if it was possible to evaluate an encryption circuit ...
ProfCornDog's user avatar
1 vote
1 answer
48 views

Implement reciprocal of a floating point number using Chebyshev approximation in CKKS

I am trying to obtain the reciprocal of a floating point value $x$ using the Chebyshev approximation, where $x$ is mostly in the order of $10^3$ to $10^5$. Subsequently, I am trying to implement that ...
Sumana Bagchi's user avatar
2 votes
1 answer
78 views

The cost of the additive homomorphic encryption of McEliece cryptosystem

Let's have two integer-vectors $v_1$ and $v_2$ that are encrypted by McEliece public key. An intermediate node between the sender and receiver receives the two encrypted vectors $\text{E}(v_1)$ and $\...
Anas Ahmad's user avatar
0 votes
0 answers
31 views

Interactive Zero-Knowledge Proof for the Multiplication Gate

Refer to an interesting article (link) on Medium on the subject matter. To understand more about pRandomValue and vRandomValue. The article mentioned, "pRandomValue, on the other hand, is used to ...
user60588's user avatar
  • 191
0 votes
0 answers
121 views

Homomorphic Decryption with the Encryption (ciphertext) of Secret key for Bootstrapping purpose

The section 3.1 of the GHS11 mentions that: Given the $q_L$-ciphertext $c = (c_0, c_1)$ (that encrypts a polynomial $a \in F_2[X]/F(X)$), we postprocess it to get $c^\prime = (c_0 + c^*, c_1) \text{ ...
kindi's user avatar
  • 11
2 votes
1 answer
40 views

Initial approximation in CKKS Bootstrapping

In this CKKS bootstrapping paper https://eprint.iacr.org/2018/153 the authors use a Taylor expansion to approximate the complex exponential function within a small range. More precisely, for the input ...
opag's user avatar
  • 63
1 vote
1 answer
85 views

How to write zk-snark arithmetic circuits

Paper: "Dispute-free Scalable Open Vote Network using zk-SNARKs" by Muhammad ElSheikh Available at: https://arxiv.org/pdf/2203.03363.pdf In this paper, the author has mentioned some pre-...
user60588's user avatar
  • 191
1 vote
0 answers
37 views

Is it possible to verify and prove the decryption of an FHE cyphertext without the verifier knowing the key with zkProof?

Suppose Bob encrypts a plaintext($p$) with an FHE scheme and a key($k$), then sends the $c$ to Alice. Alice wants to know the plaintext but can't trust that Bob won't send a different string. Can Bob ...
Vasily Sobolev's user avatar
0 votes
2 answers
129 views

Are security assumptions based on quantum computers too strict? Causing cryptographers to tie their own hands

Have security assumptions based on quantum computers de facto constrained the emergence and application of many new cryptographic schemes (e.g., fully homomorphic encryption)? It seems to me that, in ...
WAN Lipeng's user avatar
1 vote
1 answer
121 views

Find two hard to reverse functions f and h such that f ∘ h ∘ g = h (f and h injective, no constraints on g)

I am looking from 3 functions $f,g,h$ from $\mathbb N \to \mathbb N$ (they can be bijections, they need to be injective at least), such that: $$f \circ h \circ g = h $$ and $f$ is hard to reverse ...
Mathematical_Noob's user avatar
2 votes
1 answer
90 views

Bootstrapping in TFHE

I've read the series of blog posts explaining TFHE scheme on zama.ai's website (four parts), and some things are not clear to me. I would appreciate if someone can shed some light on those topics. I ...
Pier's user avatar
  • 23
1 vote
2 answers
72 views

Private set intersection using homomorphic encryption

I have a question regarding the scheme below. PSI using homomorphic encryption appears to subtract the plaintext into the ciphertext. I understand that homomorphism is maintained in operations between ...
shs's user avatar
  • 13
0 votes
0 answers
52 views

Privacy Challenges in Applying Fully Homomorphic Encryption to Find Closest Shops Based on Zipcodes

Context To learn about fully homomorphic encryption (FHE) and a new language I implemented the Paillier cryptosystem in Go, and I thought it would be fun to apply it to the following interaction: A ...
a.t.'s user avatar
  • 101
1 vote
0 answers
79 views

Digit Extraction for HE Bootstrapping

I was wondering if someone could explain the Digit Extraction from HElib in simple words: Apply a homomorphic (non-linear) digit-extraction procedure, computing $r$ ciphertexts that contain the ...
kindi's user avatar
  • 11
1 vote
0 answers
18 views

Non-prime value chosen for u in DGK encryption

In DGK encryption, one of the parameters of public key is value u where it is a small prime with minimum length l+2. It is not obvious for me what is the security compromise if u is not prime. Any ...
Fattaneh's user avatar
2 votes
1 answer
59 views

About Naccache-Stern higher residue cryptosystem definition

About the Naccache-Stern cryptosystem, I have found two different encryption algorithms: In the original paper from Naccache and Stern, the encryption step is performed by calculating $c = g^m \...
hectorvr14's user avatar
0 votes
1 answer
60 views

Homomorphic Encryption and Conjugation

In the implementation of HEAAN, they have implemented the conjugate function. It computes conjugate of a polynomial. Effectively they have reverted the positions of the coefficients and negated their ...
kindi's user avatar
  • 11
1 vote
0 answers
71 views

Privacy-Preserving User Tracking Across Systems with Homomorphic Encryption or hashing

I'm working on a project where we have three different software systems—let's call them A, B, and C. Systems A and B handle user data identified by phone numbers and want to send user actions to ...
Mr Alihoseiny's user avatar
1 vote
0 answers
39 views

Dealing with MITM attack in e-voting systems

I've read many e-voting papers that use El-Gamal scheme which I recall is vulnerable to man-in-the-middle attack, yet I find no discussion or even mentioning of it in those papers. -Does anyone knows ...
ShAr's user avatar
  • 150
0 votes
0 answers
42 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:...
user2642459's user avatar
1 vote
0 answers
88 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 ...
Parham's user avatar
  • 111
0 votes
0 answers
53 views

divide integer to multi by polynomial ring in BFV homomorphic algorithm

The BFV algorithm is one type of fully homomorphic encryption algorithms. How can I encode an integer to polynomial ring by using batch encoder based on $R_t := {Z_t[X] \over ⟨(X^n)+1⟩}$? The ...
Nibras's user avatar
  • 1
0 votes
0 answers
17 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 ...
js wang's user avatar
  • 327
1 vote
1 answer
61 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 ...
sefiks's user avatar
  • 229
0 votes
1 answer
65 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\} $ ...
Tokubara's user avatar
  • 103
0 votes
0 answers
48 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 ...
Plop's user avatar
  • 1
1 vote
1 answer
66 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 ...
baxbear's user avatar
  • 125
1 vote
1 answer
71 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 ...
js wang's user avatar
  • 327
1 vote
1 answer
59 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 ...
js wang's user avatar
  • 327
0 votes
0 answers
52 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 ...
js wang's user avatar
  • 327
0 votes
0 answers
60 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 ...
纪老猴子's user avatar
0 votes
0 answers
45 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 ...
Anisha's user avatar
  • 11
1 vote
2 answers
132 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 ...
js wang's user avatar
  • 327
0 votes
0 answers
21 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. ...
mmazz's user avatar
  • 21
0 votes
0 answers
42 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/...
js wang's user avatar
  • 327
0 votes
1 answer
195 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(\...
Zhengyi Li's user avatar
1 vote
1 answer
119 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 ...
bd55's user avatar
  • 33
0 votes
0 answers
63 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 ...
LWE-13's user avatar
  • 251
0 votes
0 answers
32 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 ...
yael's user avatar
  • 1
2 votes
1 answer
122 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, ...
smoking_big_ole_doinks's user avatar
1 vote
0 answers
20 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 ...
Galois group's user avatar
1 vote
1 answer
106 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 ...
zhengyuansu's user avatar
0 votes
1 answer
35 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 ...
lap quoc's user avatar
1 vote
2 answers
69 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?
Arik Malachi's user avatar
2 votes
1 answer
79 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 ...
Freak14's user avatar
  • 23
1 vote
1 answer
119 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 ", ...
mmazz's user avatar
  • 21
1 vote
1 answer
88 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+...
S. M.'s user avatar
  • 11
3 votes
1 answer
274 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 ...
macknight's user avatar
0 votes
0 answers
16 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.
opag's user avatar
  • 63

1
2 3 4 5
18