8 votes
Accepted

Advantages and possible usages of encryption schemes with probabilistic decryption

Since when decrypting we always want to get the correct message back, there's no reason why we would want to make this ambiguous. It would have no security advantage (if the adversary can guess with ...
user avatar
6 votes
Accepted

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

They are different concepts and have different approaches. AES like any block cipher is a primitive and the encryption is performed by using the block cipher mode of operation. Like ECB,CBC,CTR,GCM,...
user avatar
  • 43.4k
6 votes
Accepted

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?

Yes, this does leak some information. In fact, just knowing $u_1$ and $w_1$ will allow the attacker to calculate $u_1^{-1} w_1 = x^{-1} z$.* In particular, knowing this value will let the attacker ...
user avatar
6 votes

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

Meta: since this is about using a tool not the underlying algorithm/math AIUI should be security.SE instead. If anyone can and wants to migrate feel free. Per 1.0.2 source, ...
user avatar
6 votes
Accepted

Why is Paillier Cryptosystem called probabilistic?

As user curious said in a other answer probabilistic means that the encryption of the same plaintext under the same key gives as output a different ciphertext. This is a more general property and it ...
user avatar
  • 3,225
5 votes
Accepted

Understand LWE(Learning With Error) negligible error probability

Denote by $X$ the random variable which is the sum over all $S$. As mentioned, this is a Gaussian of standard deviation at most $\sqrt{m}r$ with $r = \alpha q$. Hence, by properties of the (sub-)...
user avatar
  • 3,697
5 votes

Understand LWE(Learning With Error) negligible error probability

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.
user avatar
  • 1,099
5 votes

Why is Paillier Cryptosystem called probabilistic?

Because each time you encrypt a message $m$, its ciphertext changes and is not the same (each time you encrypt you pickup a random element $z \leftarrow \mathbb{Z}_n^*$). If for each message there was ...
user avatar
  • 5,872
4 votes

What is the meaning of "probabilistic encryption algorithm"?

Informally, in probabilistic encryption random values are used to encrypt a message. Thus, each time we encrypt a message we pick a fresh random value; as a result if we encrypt the same message twice ...
user avatar
  • 1,533
4 votes
Accepted

Katz/Lindell Problem 2.2

You neglected the most important part, I believe; the encryption map itself may be probabilistic which means we might have $$c \leftarrow \mathrm{Enc}_k(m),$$ instead of $$c =\mathrm{Enc}_k(m),$$ ...
user avatar
  • 16.4k
4 votes
Accepted

How to sign low-entropy messages?

Either you make sure that you use separate key (pairs) for each different purposes, or you simply include all possible context in the signature, including the entities. So sign a message consisting ...
user avatar
3 votes

Is there an additive homomorphic encryption that supports exponentation

What you want is a cryptosystem that supports linear operations, and some bounded number of multiplications (supporting exponentiations by bounded values is equivalent to supporting multiplication, as ...
user avatar
2 votes

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

But in PKCS#7 people just use the padding size rather than some random bits. Doesn't it make AES deterministic? The padding used for block ciphers is just used to make sure that the plaintext can be ...
user avatar
2 votes

How to sign low-entropy messages?

The problem is not really the fact that the message is low-entropy, but the fact that it's context-dependent. How do I love thee? Let me count the ways… Plenty of entropy, but still mostly the ...
user avatar
2 votes
Accepted

Leak Information?

Any kind of information, maybe even only under special conditions? Sure. Just an easy one: Since we know $(r_1 \cdot a)$ amd $(z_1 \cdot a)$, we can easily calculate $f_1 = (r_1 \cdot a) \cdot (z_1 ...
user avatar
  • 1,187
2 votes
Accepted

Standard deviation of gaussian noise in FHEW scheme

Apologies for seeing this question just now. For your first question, well, there seems to be a typo: I should have written $\|s\|^2 \leq n/2$, and then we have $\sqrt{(\|s\|^2 +1) /12 } = \sqrt{251/...
user avatar
  • 1,099
2 votes
Accepted

Challenging Question for the Build a Secure MAC with Special Properties

Here is a construction that appears to meet all your criteria: We will assume that: $k \ge 2^{n+1}$ $MAC'_k(a | b)$ is a standard deterministic MAC (e.g. HMAC) of the string $(a | b)$ Then, $\...
user avatar
  • 132k
2 votes
Accepted

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

Let's look at the definition in the linked thesis: Definition 2.2.2 (probabilistic one-way function). A probabilistic function, $F$ (with randomness domain $R_n$), with a corresponding deterministic ...
user avatar
  • 6,429
1 vote
Accepted

Laplace Inequality

OK, I did this quickly. Hope it’s correct. When $r*\geq 0,$ the relationship holds as you observed. And when $r^*\leq -1,$ the same expression for both probabilities you want to compare enables a ...
user avatar
  • 16.4k
1 vote

Understanding why Semantic Security implies Message Recovery Security

Sorry if I'm a bit late but I want to consider a bit different approach to this proof, it's indeed tricky and every sentence should be read really carefully. I've just wrapped my head around this so ...
user avatar
1 vote

Understanding why Semantic Security implies Message Recovery Security

The reason $ p_0 = \frac 1 {||M||}$ is because $ p_0 $ is the probability that adversary B guesses $ m_1 $ when the message was actually $ m_0 $. In this situation, B "cheated" in playing ...
user avatar
  • 11
1 vote

Understanding why Semantic Security implies Message Recovery Security

The definition of semantic security we see in the Shoup book is better explained in his well-known paper Sequences of Games: A Tool for Taming Complexity in Security Proofs. You must pay the very ...
user avatar
1 vote
Accepted

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

Answering my own question. I believe it is possible. We can use the scheme by Boneh et al. described here. It uses pairing-based cryptography to be able to create a searchable, asymmetric, tagging ...
user avatar
1 vote

Leak Information?

The answer is correct. For this aim, you can consider the following consequence: $$f_1=r_1^{-1}\cdot z_1,~f_2=r_2^{-1}\cdot z_2,~f_3=r_3^{-1}\cdot z_3$$ Then we have from the third component $...
user avatar
  • 51
1 vote
Accepted

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

In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext. Here's an example—with lots of details not related to your question omitted, so don't take these ...
user avatar
1 vote
Accepted

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

Every secure public key cryptosystem must have a probabilistic encryption algorithm. Suppose this was not the case and consider the usual IND-CPA game. An attacker can now win this game with ...
user avatar
  • 44.6k
1 vote

Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis

I think you're being too dismissive and thinking of this as a "side project". The challenge is representing the action of the cryptographic mappings such as the key schedule and the round functions ...
user avatar
  • 16.4k
1 vote
Accepted

Probability of collision in PRF

You claim that $k$, $k'$ are chosen independently and uniformly. Assuming these keys are used nowhere else except as PRF keys in this way, and that the length of the PRF keys are at least the security ...
user avatar
  • 10.6k
1 vote

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?

The operation of the function is completely described by $P(X,Y,K)$ which factorizes as $P(Y|X,K)P(X)P(K)$ under the assumption that $X$ and $K$ are independent and leads to $$P(Y) = \sum_X\sum_K P(Y|...
user avatar
1 vote

What is the meaning of "probabilistic encryption algorithm"?

How can the output of a probabilistic algorithm be different for the same pair of plain text and key when used two different times? The probabilistic algorithm makes calls to a random number ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible