Questions tagged as ['homomorphic-encryption']

Lattice-based cryptography is being used for several primitives and applications.

I know there are newer works for PIR, PSI, ORAM that have seen tremendous improvements due to FHE. In some cases, FHE is the only tool that can be used for practical constructions of these primitives.

My question is which other such primitives have seen improvements (in performance or security)?

I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have looked into.

My particular point of confusion is with $B_{\mathsf{mult}}(\ell)$ (on page 12, as part of lemma 3), which is defined to be $P^{-1}q_\ell B_{\mathsf{ks}}$, where $B_{\mathsf{ks}} = O(N\sigma)$

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 correctness proof of the scheme follows

In this proof , I can get the second last equation in decryption procedure , i.e. $$\mathbf{m} + (t/q)(\mathbf{v}-\epsilon \cdot \mathbf{m}) + t\cdot \mathbf{r} $$ ...

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 whether two ciphertexts encrypt the same thing), then $\epsilon$ can be broken in sub-exponential time.

Side question: This answer mentions that any probabilistic PHE scheme can be made deterministic. This h ...

Fully Homomorphic Encryption without Bootstrapping describes considerations for large (exponential in the security parameter) integer plaintext spaces in Section 5.4, "More Fun with Funky Plaintext Spaces". Has anybody implemented these techniques in code?

It should be a secure two party protocol against malicious adversary.

P1's input is X in Zp* (p is a prime number); P2's input is nothing. P1's output is rX+r'. r,r' are random numbers from Zp* P2' output is r and r'.

Is there any efficent protocol to realize this functionality other than by using homomorphic encrytion? If only HE solves this problem, which is the most efficent one?

Thanks for help!

It is known that it is possible to apply the Chinese remainder theorem and attack RSA under precise conditions.

https://tls.mbed.org/public/WSchindler-RSA_Timing_Attack.pdf

But the question is, can the Chinese remainder theorem in ECDSA be applied to the parameters in secp256k1?

Bonjour à tous, Je dispose d'un vecteur contenant 15 nombre réel chiffrés avec les schéma de chiffrement homomorphe CKKS. Mon problème est que je souhaite trier ce vecteur par ordre croissant. Je ne sais pas comment m'y prendre. Votre aide me sera la bienvenue. Merci

Hello everyone, I have a vector containing 15 real numbers encrypted with the CKKS homomorphic encryption scheme. My problem is that ...

What's the functional and security model for SEAL?

From this I get that it

allows additions and multiplications to be performed on encrypted integers or real.

But what are the limitation, like range, precision, on inputs and outputs? What operations can be performed? Is there some limitation beyond range/precision?

What is the security model an application designer using SEAL as a black box should assum ...

homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.

Is there an simple way to calculate the security level?

I'm looking at https://link.springer.com/content/pdf/10.1007%2F11496137_31.pdf and it seems like in the protocol they propose if Alice can guess Bob's number, she can pretty easily verify that guess. (Section 3: Our Protocols)

Bob isn't performing any private operation besides generating the random encryptions to fill out the items he's sending back to her. So Alice could do the exact same thing  ...

I am working on system which can calculate average salary for different positions in large companies I want to use pailler schema to do such calculation.

I have 3 fields which I want to encrypt: companyName, jobTitle, seniority and salary

Let’s say I have 3 different companies which want to calculate average salary on different positions but they don’t want to share data between them. We have su ...

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 their applications?

I always thought there were limitations adopting simulation based proofs and Universal Composability, in general, in Formal Verification, but as of late I'm thinking there must be mor ...

We can secretly query inputs from a public DBs using what we call in the literature PIR. We can secretly query inputs from a privately held DB by means of Private Set Intersection (PSI). We can also secretly read/write from a private DB, using ORAM. We can even secretly query a private distributed state, by combining ORAM and MPC.

I wonder, however, what happens for the one use case not annotated ...

Let's say we have a BGV style homomorphic encryption scheme. The message space will be the ring $$R_p = \mathbb Z_p[x]/(x^d + 1)$$ where $p$ is a prime congruent to $1$ modulo $2d$. Now let's say we say messages $m_1(x), m_2(x) \in R_p.$ How do we obtain a ciphertext encrypting both $m_1(x)$ and $m_2(x)$? The BGV paper mentions the CRT isomorphism $$R_p \cong R_{\mathscr{p_1}} \times ... \times R_{\mat ...

I try to explain the problem (maybe it's trivial): is there a way to do the following: sign a message with private key, send encrypted version of signature and an encrypted version of publickey to verifier in a manner that the verifier can verify the signature without decrypt publickey and signature? Thanx in advance for the answer.

For example, Paillier's RSA modulus is $n=pq$, but OU's RSA modulus is $p^2q$. I think when two $n$ are the same, the security of the two cryptographic schemes must be different. So for example, if I take 3072 for Paillier's $n$, how long should I take for OU's $n$?

Let's say that $n$ honest-but-curious parties each hold a value $x_i$. The parties want to learn what is the maximum value across the parties $\{x_1...x_n\}$ without sharing their values (unless they hold the maximum), or knowing who holds the maximum (aside from learning that the holder is or is not them). What are some approaches, optimizing for round complexity?

Not sure which forum to post this question so here is a link to it from MSE.

This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system.

I understand that this will occasionally fail (approximately 1 in $\sqrt n$), but I feel this is unlikely enough to ignore. Am I correct in my assumption?

As I understand from this post, mapping from plaintext space to ciphertext space is the fundamental point of all order-preserving encryption. So the only way that we let someone encrypt an arbitrary plaintext is to give him/her this mapping. But, on the other hand, if we give someone this mapping, the encryption breaks because anyone who has access to it can easily decrypt any ciphertext since this mapp ...

Let ($Gen,Enc,Dec$) be an LHE scheme with security parameter $\kappa$ and message space $M$. Assume that a multiplication operation exists in $M$, i.e., is a finite ring. Let $F : \{0, 1\}^s × L → M$ be a pseudo-random function with seed space $ \{0, 1\}^s$ ( $s=poly(κ)$) and the label space $L$.

I understand what $\kappa$ is as the security parameter of the encryption scheme, but I'm unfam ...

This question is about the serialization of pk, sk, and context in HElib. In my scenario, there are two trusted parties (A and B), these two parties can encrypt the messages and decrypt the ciphertexts.

So, A will send the context, pk, and sk to B. Then, A encrypts the message and send ctxtA to B, B decrypts ctxtA and sends another ctxtB to A. This example is just for explanation.

But it's confusing in ...

In BGV12(Fully Homomorphic Encryption without bootstapping), they investigate the efficiency of a FHE scheme by considering the per-gate computation overhead of the FHE scheme, defined as the ratio between the time it takes to compute a circuit homomorphically to the time it takes to compute it in the clear. I wanna know what means compute a circuit homomorphically and compute it in clear?

Thank you ...

I have read FHE lately. In Fully Homomorphic encryption using ideal lattice[Gen09], I noticed his recrypt algorithms:

1. We have a ciphertext $\phi_1$ which is encrypted by public key $pk_1$, and can be decrypt by secret key $sk_1$.
2. we use a public key $pk_2$ to encrypt the bits of $sk_1$, and we get $Encrypt_\epsilon(pk_2,sk_{1,j})\to \overline{sk_{1,j}}$.
3. we use the same public key $pk_2$ to encrypt the b ...

HElib contains the CKKS and BGV, SEAL contains the BFV and CKKS, is there some concrete performance data about these two lib?

I have to verify that the user has registered and is currently logged out without identifying the user. Essentially, I am looking for privacy-oriented authorization mechanisms which prevent simultaneous user sessions.

I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in cryptography. There are some papers comparing the efficiency of HE based/ GC based/ OT based protocols, for example https://eprint.iacr.org/2016/544.pdf by Geoffroy Couteau(still a bit hard for me to understand th ...

While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding:

Let $p$ be a plaintext modulus and $q$ be a ciphertext modulus (they are coprime). Let $\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$ be the fixed set of representatives modulo $m$ and $[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$ be modulo  ...

I understand the general idea of key switching, but I would like to know when it is used. Sometimes it is referred to as same thing as relinearisation(after multiplication), but is key switching also used when rotating (batched ciphertexts)? If so, how similar to each other are different key switching situations? I am interested in the most popular schemes(BFV, BGV, CKKS).

Thanks for help!

The encryption function $E_{k^+}: Z_n \rightarrow Z_{n^2}$.
The decryption function $D_{k^-}: Z_{n^2} \rightarrow Z_n$.
$m_1 = 42, k = 15, n=77$.
After encryption, exponentiation and decryption, I get: $$D_{k^-}((E_{k^+}(m_1))^k) \equiv 14 \bmod 77$$ The class of residue of $14$ is of the form: $$\langle 14 \rangle = \{\alpha \in Z: 14 + \alpha*77\}$$ And one of these values is $630 = 14 + 8*77 \ ...