People who code: we want your input. Take the Survey

# Tag Info

## Hot answers tagged probabilistic-encryption

8

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 any non-negligible probability, you have already lost, so ambiguous decryption can't make that harder). Thus, unlike probabilistic encryption, which is needed ...

6

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,EAX... The pkcs#7 padding or any other padding that is used to fill the last block to the block size with ambiguous remove, not designed for randomization. Even ...

6

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 calculate $x$ if they know $z$, or vice versa. Similarly, knowing $u_1$ and $u_2$ will let the attacker calculate $u_1^{-1} u_2 = r_1^{-1} r_2$. With $u_1$, $... 6 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, -sigopt rsa_mgf1_md:name where name is the name of a hash available to EVP_getdigestbyname -- that is, implemented and not #if'ed out by default (MD2) nor manually. For FIPS mode if ... 6 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 is known as a basic security property: it is usually refered to as semantically secure or indistinguishability (roughly: an attacker cannot guess which one of ... 5 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-)Gaussian distribution you have that $$\operatorname{Pr}\left[|X| > t\right]\leq 2\exp\left(\frac{-\pi t^2}{r^2m}\right)$$ so, for$t = \frac{q}{2}$you have $$... 5 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. 5 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 the same ciphertext then the encryption scheme would be deterministic and would not be semantically secure or would not provide indistinguishability. 4 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 we would get different encrypted value (or ciphertext).This means that the ciphertext does not depend only on key and plaintext. 4 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 of "Allice: Bob, do you love me? Bob: yes". Note that it is not required to send all the data together with the signature, as long as you can regenerate the ... 3 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 to compute a*b homomorphically, you can always compute (a-b)²-a²-b² homomorphically and divide this by two). Without requiring a bound on the number of ... 3 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),$$which is deterministic. In the first case a second encryption with the same key and message might result in a different ciphertext. Once you realise this and given ... 2 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 same problem as “yes”/“no”. The way to solve this is to include all the relevant context in what is signed. A good protocol with integrity protection includes the ... 2 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 verifier, V_F , is called one-way with respect to a well-spread distribution, \mathbb{X}, if for any PPT, A:$$\Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(... 2 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 split up into message blocks. A few block cipher modes such as ECB and CBC require this due to the way they work. Note that CipherText Stealing (CTS) can be ... 2 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 \cdot a)^{-1} = z_1 \cdot r_1^{-1}$Similar for$f_2$and$f_3$. Lets in this easy case assume that$f_2 = f_3$. We further know$(r_1 + r_2 - r_3) \cdot ...

2

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/12} \approx 4.57$. Now, we take 2 ciphertext with LWE error of std-deviation $\beta$, and sum them. Assuming independence the std-dev of the sum of the errors ...

2

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, $\mathsf{Gen}$ generates a random $MAC'$ key $\mathsf{Mac}$ is defined as $\mathsf{MAC}_k(a_1, a_2) = (t_1, t_2)$ where $t_1 = a_1 + MAC'_k( a_1, a_2)$, $t_2 = a_2 + ... 1 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 direct proof. Let$r^*\in(-1,0),$so that$1+r^* \in (0,1).$Then what you want to show is $$\frac{1}{2} e^{-\epsilon(1+r^*)}\geq e^{-\epsilon}\left(1-\frac{1}{2} e^... 1 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 attention to their words on page 15 of the book: Actually, our attack game for defining semantic security comprises two alternative "sub-games", or "... 1 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 scheme. In this scheme, queries are made through a trapdoor of the real key that we want to search, making it impossible for the set holder to retrieve ... 1 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 u_1 and u_2:$$(r_1+r_2-r_3)\cdot d=\alpha(z_1+z_2-z_3)\cdot d = (r_1 \cdot f_1+r_2 \cdot f_2-r_3 \cdot f_3)\cdot d=\beta$$Using the multiplication ... 1 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 scissors and try running with this at home! The recipient knows the secret ~256-bit number r of times that a base point B must be added to itself to yield ... 1 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 probability 1 as follows: He chooses two distinct messages m_1,m_2 at his liking and submits them to the challenger. The challenger chooses a bit b\in\{0,1\} ... 1 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 which result in a pseudorandom permutation that can only sample a vanishingly small subset (a fraction$$\frac{2^k}{(2^n)!}$$for keylength k block length n, ... 1 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 parameter, then you can apply the security of the PRF. Collision resistance doesn't seem relevant to me if the key portion of the PRF input is guaranteed to be ... 1 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|X,K)P(X)P(K)$$If you restrict$X$to only the particular one that$K$maps onto$Y$(by writing$X = D_k(y)$) then$P(Y|X,K) = 1$under the assumption that ... 1 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 generator and uses that generator's output in such a way that the algorithm's output depends on the random numbers as well as the plaintext and key. If you're ... 1 As the previous poster says the problem can not be solved if you don't know$x,z,r_1,r_2.$But the question seems to have some connection with the generalized hidden number problem. In some sense answers the opposite question of the OP. Say that you have an oracle that gives you$r_1,r_2,...,r_{d}$(polynomial many) uniformly from${\bf Z}_p$(so the$r_j\$'...

1

Your hunch is wrong because of the definition of CPA security: Assume that some knowing some kind of relation between two plaintexts would give the attacker an advantage. Now think of the INC-CPA game: Nothing stops the attacker from choosing exactly this kind of relationship. And if the scheme is IND-CPA secure, knowledge of such a relation does not break ...

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