# Questions tagged [probabilistic-encryption]

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts.

23 questions
Filter by
Sorted by
Tagged with
2answers
274 views

### Understand LWE(Learning With Error) negligible error probability

According to Regev's paper, p15 Correctness. Note that if not for the error in the LWE samples, $b-⟨a, s⟩$ would be either 0 or ⌊ q ⌋ depending on the encrypted bit, and decryption would always be ...
2answers
89 views

### Does $(u_1=r_1\cdot x,\ \ w_1=r_1\cdot z, \ \ u_2=r_2\cdot x,\ \ w_2=r_2\cdot z)$ Leak Information?

Consider we have a fixed value $x$. We pick values $r_1,r_2,z\leftarrow \mathbb{F}_p$, where $p$ is a large prime number, and it is public. So $r_1,r_2,z$ are uniformly random values. We compute ...
1answer
297 views

### Katz/Lindell Problem 2.2

2.2 Prove that, by redefining the key space, we may assume that $\text{Enc}$ is deterministic without changing $\text{Pr}[\text{Enc}_k(m)=c]$ for any $m, c$. After banging my head against this ...
2answers
1k views

### Why is Paillier Cryptosystem called probabilistic?

The definition of Paillier Cryptosystem says that it is a probabilistic asymmetric key algorithm for public key cryptography. Can some body explain why it is called "probabilistic"?
0answers
134 views

### computational indistinguishable/distinguishable?

Let $a,b,c,d$ be selected at random from $Z_q$. Consider the following two distributions $X_1$ and $Y_1$: $X_1={(r_1\cdot a, r_2\cdot b, r_3\cdot c, (r_1+r_2-r_3)\cdot d)}$ where $r_1,r_2,r_3$ ...
0answers
109 views

### What's the difference between game-based and simulation-based security? [duplicate]

What's the difference between game-based and simulation-based security? When we use the simulation-based, how to construct the simulator based on the adversary?
2answers
143 views

### How to sign low-entropy messages?

Suppose you would like to prove authenticity of messages where the message space is small. Suppose the meaning of the message depends highly on the context, e.g. on time but also on events that are ...
1answer
712 views

### setting the MGF hash to a different value other than the regular hash with openssl for PSS signatures

In PKCS1's Probabilistic Signature Mode you have the Hash and the MGF Hash. Both appear to be, by default, sha1, with the OpenSSL CLI client, however, I can change it to sha256 with the following: <...
1answer
58 views

### Standard deviation of gaussian noise in FHEW scheme

I've got two questions regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. First, the final error of a ciphertext after the refresh procedure is stated as following ...
2answers
344 views

### If a probabilistic encryption algorithm is used, how does decryption return the correct message?

Given a key $k$ and a plaintext $p$, a deterministic encryption algorithm will return a ciphertext $c_1$. In a second trial, I run the same key and plaintext $p$ through the encryption algorithm and ...
1answer
180 views

### Weakening of Pallier cryptosystem due to ciphertext equivalence and order in CryptDB

Pallier Cryptosystem is probabilistic in nature and IND-CPA secure. By design given two ciphertexts one cannot distinguish whether decrypting those two ciphertexts will result in same or different ...
2answers
1k views

### What is the meaning of probabilistic encryption algorithm?

I am learning cryptography by myself and I am not able to understand the meaning of probabilistic encryption algorithms. How is it different from deterministic encryption algorithms ? How can the ...
2answers
183 views

### Leak Information?

Let a,b,c,d be selected at random from $\mathbb Z^*_q$. We pick values $r_1,r_2,r_3,z_1,z_2,z_3 \gets \mathbb Z^*_q$. Do $u_1,u_2$ that are computed as follows, leak information about values $a,b,c,d$...
1answer
458 views

### Is there an additive homomorphic encryption that supports exponentation

For example say we have two numbers a and b. Now is there any partial homomorphic encryption scheme that allows to compute (a-b)^2 over the ciphertexts of a and b without round trips.
1answer
213 views

### Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis [closed]

I'm currently doing a PhD in probability theory, specifically (discrete space) Markov chains and their mixing properties. As well as my current main project, I'm looking to have a side project, eg to ...
1answer
200 views

### Probability of collision in PRF

My question is related to this: Collision-resistant Pseudorandom function Assume we have a pseudorandom function as follows: $PRF: \{0,1\}^{l}\times\{0,1\}^{t}\rightarrow\{0,1\}^{m}$, where $l$ is ...
2answers
97 views

### How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold?

How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold for any cryptosystem? In his book Cryptography, Theory ...
1answer
204 views

### Partial Homomorphic Schemes that are probabilistic

As mentioned in wikipedia there are many Partial Homomorphic Encryption(PHE) scheme like RSA, Elgamal, Pailler etc. Pailler encryption scheme seems to be probabilistic Are there any other PHE ...
0answers
44 views

### Question on nCPA Security and Uniform Permutations

I feel I am misunderstanding the idea of nCPA security and its relation to uniform permutations. In particular I've been reading the paper "Hoang, Morris Rogaway; An Enciphering Scheme Based on a Card ...
0answers
145 views

### Leak information (new setting)

This question is similar to Leak Information?, but with new settings. Let $a,b,c,d,e,f$ be selected at random from $\mathbb Z^*_q$. Also, let $r_1,r_2,r_3,z_1,z_2,z_3,p_1,p_2,p_3$ be selected at ...
0answers
179 views

### Thorp-Shuffle Coupling

My question is regarding the coupling of the Thorp-Shuffle, as described in Morris/Rogaway/Stegers, Thorp-Shuffle Encryption. On pages 7 to 9, they describe and implement a coupling. It's all fairly ...
1answer
87 views

### Challenging Question for the Build a Secure MAC with Special Properties

We would like to ask you to give a construction for requested scheme which provides those properties or give a proof that is not achievable. [Note that unsuccessful attempts to build such a scheme ...
1answer
73 views

### What is the advantage of a probabilistic PKC over a traditional PKC?

While reading through a textbook, I came across the idea of a probabilistic public key cryptosystem, which uses a probabilistic TM to generate the public encryption and private decryption algorithm; ...