Skip to main content

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

256 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
2k views

Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?

There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...
Habib's user avatar
  • 951
9 votes
0 answers
689 views

LT codes with Homomorphic hashing

I have been working on a project implementing LT codes with Homomorphic hashing (inspired from http://blog.notdot.net/2012/08/Damn-Cool-Algorithms-Homomorphic-Hashing and http://blog.notdot.net/2012/...
user794034's user avatar
8 votes
1 answer
737 views

Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
Guillem's user avatar
  • 81
7 votes
1 answer
493 views

Is there any way to check hash of homomorphic encrypted data?

I need some algorithm that satisfies: H - hash function Enc - encryption function (using public key) M - secret data $Enc(H(M)) = H(Enc(M))$ Let this system exist: the First person has a secret ...
Nonam's user avatar
  • 71
6 votes
0 answers
144 views

Is it possible to derive a homomorphic signature from homomorphic encryption

At the moment I am trying to find a practical way to implement a linearly homomorphic signature. Background: "In a homomorphic signature scheme, a user Alice signs some large dataset x using her ...
Tom Hamer's user avatar
6 votes
0 answers
250 views

Additive homomorphic encryption scheme without change in operator

I'm looking for an additive homomorphic encryption that the addition operator (+) in its plaintext space be the same as addition operator in its ciphertext space. (Schemes like Paillier do addition in ...
user26343's user avatar
5 votes
1 answer
242 views

fully homomorphic encryption without bootstrapping

In this paper by Alperin-Sheriff and Peikert from 2014, the authors state To date, bootstrapping remains the only known way of obtaining fully homomorphic encryption for arbitrary unbounded ...
Celdor's user avatar
  • 51
5 votes
1 answer
288 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
5 votes
0 answers
196 views

Is it possible to enhance white-box cryptography security by homomorphic encryption?

Background: Let's discussed based on published symmetric white-box crypto only, such as Chow's white-box AES. I only know basic concepts/objectives of homomorphic encryption, such as PHE and FHE. ...
TJCLK's user avatar
  • 497
5 votes
0 answers
77 views

Threshold homomorphic

Quite a specific question, but are there any threshold signatures that are also homomorphic? Preferably ones that work in the discrete log setting and don't require any pairings.
Max Chamberlin's user avatar
5 votes
0 answers
467 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
Rohit Khera's user avatar
5 votes
0 answers
264 views

How do they avoid Zero Knowledge Proofs in the paper Priced Oblivious Transfer: How to sell Digital Goods?

I don't understand a part of the paper Priced Oblivious Transfer - How to Sell Digital Goods. Particularly, the authors avoid using zero knowledge proofs and in section 3.3 they explain how they do ...
user2234174's user avatar
5 votes
0 answers
475 views

Homomorphic system that allows Hamming distance computation?

How can I work out Hamming distance between two binary vectors securely? I would like to know how I can apply homomorphic techniques here.
Y.V's user avatar
  • 51
5 votes
0 answers
252 views

Is an MPC protocol from ElGamal a good solution for homomorphic multiplication?

I want to compute a multiplication between many secret values and then distribute the result to everyone involved. For this, I thought about an MPC protocol built from Threshold Homomorphic Elgamal. ...
guglielmo london's user avatar
5 votes
0 answers
435 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
haael's user avatar
  • 285
4 votes
0 answers
141 views

Zero Knowledge Proofs for Microsoft SEAL (Homomorphic Encryption)

I am working on a system involving multiple parties performing homomorphic cryptographic operations using Microsoft SEAL (BFV). Because of the nature of the system, it would be preferable for the ...
Andrei Florian's user avatar
4 votes
0 answers
200 views

Formal Verification for Multiparty Computation and Homomorphic Encryption?

I've recently found some work on the use of Formal Verification Software, like ProVerif for enclaves. I wonder is if its feasible to have something similar for MPC and Homomorphic Encryption and ...
DaWNFoRCe's user avatar
  • 872
4 votes
0 answers
113 views

What are some of the current relevant fully homomorphic schemes?

As of February 2017, I have the feeling that all information on FHE is currently a bit scattered and finding a good summary/ timeline on the topic is really hard. I'm currently looking into FHE over ...
LQWE's user avatar
  • 101
4 votes
0 answers
283 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
guglielmo london's user avatar
4 votes
0 answers
125 views

How about a homomorphic integer sorting in a MPC context?

I want to implement the ATV-FHE scheme as described by Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption (...
guglielmo london's user avatar
4 votes
0 answers
299 views

Obfuscating point-like functions

There are standard schemes for obfuscating a point function; I'm wondering if we know how to obfuscate a slight generalization of a point function. I'll elaborate more precisely. Definition 1. A ...
D.W.'s user avatar
  • 36.5k
4 votes
1 answer
246 views

Generating random vector for Full Homomorphic Cryptography

The site below explains that part of doing homomorphic encryption, you need to generate a vector of random numbers that have the property that its dot product against a randomly generated bit vector ...
Alan Wolfe's user avatar
3 votes
0 answers
238 views

The decryption correctness of RLWE based Encryption

I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper. And the decryption ...
zbo's user avatar
  • 75
3 votes
0 answers
78 views

Can the hash of the ciphertext be derived from the hash of the plaintext

Let $C$ be a symmetric cipher $H$ a hash function. Alice uses $C$ with a key $k$ to encrypt plaintext message $m$ yielding ciphertext $c$. She then calculates the hash of the message $h_m = H(m)$ and ...
Tobias Brandt's user avatar
3 votes
0 answers
117 views

Homomorphic encryption scheme for modulo reduction

I want to know if there is any Homomorphic encryption scheme that supports modulo reduction, i.e., using $Enc_{pk}(m)$ and a public $w$ to compute $Enc_{pk}(m \mod w)$. Thank you.
Felix LL's user avatar
  • 321
3 votes
0 answers
174 views

Homomorphic Encryption Roadmap

I'm looking for some suggestions on what to read (papers, notes, book chapters?) on homomorphic encryption in order to understand the most recent (more optimal) schemes, as well as optimized use cases ...
andy's user avatar
  • 85
3 votes
0 answers
78 views

What is labeled program

I've been studying homomorphic encryption. From their instantiations, i read Labeled Homomorphic Encryption (labHE) scheme 1 where it combines the notion of homomorphic encryption with labeled ...
kawsaw's user avatar
  • 115
3 votes
0 answers
155 views

Is there a partially homomorphic cryptosystem without an inverse (addition without subtraction, multiplication without division)?

I am learning about partially homomorphic cryptography, and was interested to see if there was a system such that one operation was homomorphic, but its inverse was not. For example, if I have two ...
user3667125's user avatar
3 votes
0 answers
261 views

Homomorphic encryption over finite fields

I'm curious on the following question: let $\mathbb{F}_{2^n}$ be a finite field which is an extension of $\mathbb{F}_2$ with order of $n$, is there an encoding scheme $e:=\mathbb{F}_{2^n}\rightarrow \...
Paul's user avatar
  • 243
3 votes
0 answers
126 views

How to test a FHE implementation?

I want to implement a FHE scheme based on NTRU, namely the scheme described here https://eprint.iacr.org/2014/039.pdf . How to test the security of my implementation ? Do I have to implement the ...
Radu Mardari's user avatar
3 votes
0 answers
169 views

Key Recovery Smart-Vercauteren SWHE

In the article (https://eprint.iacr.org/2009/571.pdf, pag 8) of Smart and Vercauteren, it is mentioned that the recovery of the private key is an instance of the small principal ideal problem. But I ...
Radu Titiu's user avatar
3 votes
0 answers
135 views

Lowest number challenge scheme

Suppose Alice knows a secret number $a$, and Bob knows a secret number $b$. Is there a simple way for Alice and Bob to know who has the lowest number, without Alice & Bob exchanging their numbers ...
Florian Omnes's user avatar
3 votes
1 answer
265 views

Using error-correcting codes for the bootstrapping procedure of Fully Homomorphic Schemes

In the context of Fully Homomorphic Schemes, we use a technique called "bootstrapping" to refresh the ciphertext, by evaluating homomorphically the decryption circuit with an encrypted version of the ...
Binou's user avatar
  • 408
3 votes
1 answer
296 views

Why gcd(r,(p-1)/r) needs to be 1 in benaloh cryptosystem

I recently discovered the benaloh cryptosystem. I am working with the system as it is discribed in the following link: https://en.wikipedia.org/wiki/Benaloh_cryptosystem However I need some help in ...
user28082's user avatar
  • 173
2 votes
0 answers
80 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 ...
G Pavithra 's user avatar
2 votes
0 answers
40 views

Homomorphic encryption and program obfuscation

[Say I want to outsource the computation of $y=f(x)$ without revealing information about $x$, $y$, or $f$. I thought I'd have to combine homomorphic encryption with some obfuscation $\mathcal{O}$, ...
yoyo's user avatar
  • 420
2 votes
1 answer
182 views

FHE Relinearization

I don't understand why relinearization is so significant. I understand the equations in the paper (in this post I'll be using notation from BV but I would it applies to BGV+BFV) but if anything it ...
shockedeel's user avatar
2 votes
0 answers
53 views

Can BGV scheme work with congruent values

Since all evaluation in BGV scheme is on polynomials it seems that it does not really matter if the coefficients of the polynomials are within $q$ range or not. All must be okay for the congruent ...
oddy's user avatar
  • 36
2 votes
0 answers
50 views

Commitments and snarks: overflow over a finite field

Let x = 100 - initial balance M = 1,000,000,000 transfer amount final balance M+x E(p-M) + E(M + x) = E(p - M + M + x) = E(p + x) = E(x) producing correct proof of the fact that the final balance ...
pes oves's user avatar
2 votes
1 answer
267 views

Avoid CKKS Bootstraping

CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every ...
xade93's user avatar
  • 51
2 votes
0 answers
50 views

Possibility of changing the plaintext modulus after encryption in homomorphic schemes like BGV

I'm working on a project with two computation "phases". In the first phase, I would like to homomorphically compute operations on my ciphertexts with a plaintext modulus of 2. But for my ...
Fishy Sticks's user avatar
2 votes
0 answers
44 views

DGHV FHE, How is the maximum value of the rightmost term in Lemma A.1 calculated?

The proof of Lemma A.1 of the paper "FHE over the Integers" (Page 21-22) states that the absolute value of the rightmost term of $c=p\cdot (kq_0+\sum_{i\in S}{q_i})+(m+2r+k\cdot2r_0+\sum_{i\...
Ray Den's user avatar
  • 21
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
0 answers
33 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_{\...
DDD's user avatar
  • 95
2 votes
0 answers
126 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
2 votes
0 answers
112 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
2 votes
0 answers
49 views

In BGV scheme, How should I understand FHE.Add?

The following is from BGV paper (https://eprint.iacr.org/2011/277.pdf) p. 12. $\text{FHE.Add}(pk,\textbf{c}_1,\textbf{c}_2)$: Takes two ciphertexts encrypted under the same $\textbf{s}_j$ (If they ...
zxcv's user avatar
  • 155
2 votes
0 answers
83 views

Secure (sub-exponential time) FHE

In Gentry's easy FHE intro, it is stated that Researchers [1, 8] showed that if $\epsilon$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell ...
mikeazo's user avatar
  • 38.7k
2 votes
0 answers
50 views

RLWE like problem

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s \gets R_q$ be a ...
Erfan Hosseini's user avatar
2 votes
0 answers
205 views

CKKS : Ciphertext extension

I have a CKKS ciphertext containing [a, b, c, d] and I want to get these 4 ciphertexts : [a, a, a, a]; [b, b, b, b]; [c, c, c, c]; [d, d, d, d]. Is there a more efficient way than repeating the ...
Matthieu Brabant's user avatar

1
2 3 4 5 6