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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
101 views

Ring learning with errors KEX and probabilistic encryption

I came across Prof. Bill Buchanan's video "Lattice Crypto: Ring LWE with Key Exchange" explaining the RLWE-KEX. I understood everything he explained until the last part, where he is talking ...
A. H's user avatar
  • 21
2 votes
1 answer
146 views

Is there a version of LWEEncrypt in which probability of decryption error is zero?

Is there modification to LWE public key crypto-system which makes the decryption process is totally deterministic and does not affect security?
Ali Haktan German's user avatar
1 vote
0 answers
81 views

Katz/Lindell Problem 2.2 - Purpose of proof where you redefine the key space?

I am self-studying by using "Introduction to Modern Cryptography: Principles and Protocols" (2nd edition). I am looking at the following problem. Prove that, by redefining the key space, we ...
Foobar's user avatar
  • 247
1 vote
0 answers
60 views

If a different plaintext may produce the same ciphertext, is the system perfectly secure?

Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $...
UNOwen's user avatar
  • 11
4 votes
2 answers
741 views

Advantages and possible usages of encryption schemes with probabilistic decryption

We can define deterministic and probabilistic encryption; Deterministic $c = E(k,m)$, and Examples are textbook RSA, block ciphers in ECB mode. Deterministic encryption fails to achieve CPA security....
kelalaka's user avatar
  • 47.6k
0 votes
1 answer
362 views

Do probabilistic one-way functions imply deterministic one-way functions?

Suppose $f$ is a probabilistic one-way function. Then my question is, does there exist a construction of a deterministic one-way function $g$ based on $f$? Or is it possible that probabilistic one-...
Keshav Srinivasan's user avatar
2 votes
2 answers
572 views

Why random number used in RSA padding but not in AES?

I noticed that people use a random number in the RSA-OAEP padding scheme to avoid deterministic encryption. But in pkcs#7 people just use the padding size rather than some random bits. Doesn't it make ...
Yyao's user avatar
  • 123
0 votes
0 answers
341 views

Probability of collision when we use a particular part of sha 256 hashed value

So I was supposed to use hash some co-ordinates and I was supposed to use k 3-wise independent hash functions in order for the mathematical explanations behind that algorithm to be hold. But after ...
Subha Nawer Pushpita's user avatar
3 votes
1 answer
103 views

Laplace Inequality

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then: $$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$. I know that for $r*>0$ it satisfies ...
Miguel Gutierrez's user avatar
3 votes
6 answers
624 views

Understanding why Semantic Security implies Message Recovery Security

I am stuck in the proof where it says $$p_0=\frac{1}{|M|},$$ I just do not understand how we can infer this equality. Also, am I right in understanding that B is defined as choosing his two messages ...
PhantomR's user avatar
  • 131
0 votes
1 answer
68 views

Is it possible to construct dataset for only another party to consult?

Is it possible to construct a dataset made of some kind of probabilistic encrypted indexes such that anyone can update the information contained in the set but only the one with a secret key could be ...
Afonso Delgado's user avatar
2 votes
1 answer
139 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 ...
Binou's user avatar
  • 408
1 vote
0 answers
95 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 ...
Sam OT's user avatar
  • 448
0 votes
1 answer
123 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 ...
Robert's user avatar
  • 51
1 vote
0 answers
151 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 ...
Robert's user avatar
  • 51
1 vote
2 answers
230 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$...
Robert's user avatar
  • 51
4 votes
0 answers
256 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$ ...
mohsen pourpouneh's user avatar
2 votes
3 answers
1k 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 ...
user50420's user avatar
5 votes
1 answer
756 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 ...
CRYPTONEWBIE's user avatar
0 votes
1 answer
126 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; ...
tpm900's user avatar
  • 203
5 votes
0 answers
274 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?
Z.P.'s user avatar
  • 353
7 votes
2 answers
605 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 ...
xtt's user avatar
  • 369
1 vote
0 answers
413 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 ...
Sam OT's user avatar
  • 448
1 vote
1 answer
324 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 ...
Sam OT's user avatar
  • 448
1 vote
1 answer
534 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 ...
user153465's user avatar
  • 1,573
1 vote
2 answers
155 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 ...
Shuzheng's user avatar
  • 321
2 votes
2 answers
260 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 ...
maya's user avatar
  • 139
1 vote
1 answer
676 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.
user3561024's user avatar
2 votes
1 answer
1k 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: <...
neubert's user avatar
  • 2,895
5 votes
2 answers
2k 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"?
vishnuvp's user avatar
  • 420
2 votes
3 answers
2k 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 algorithm". How is it different from "deterministic encryption algorithm"? How can ...
Pratik Singhal's user avatar
5 votes
2 answers
101 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 ...
user13676's user avatar
  • 805
2 votes
1 answer
307 views

Weakening of Paillier cryptosystem due to ciphertext equivalence and order in CryptDB

The Paillier 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 ...
sashank's user avatar
  • 6,134
2 votes
1 answer
252 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 ...
sashank's user avatar
  • 6,134