Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
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 ...


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

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

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

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 + ...


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 ...


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 ...


1

Actually, only probabilistic schemes will be of interest, since all other schemes (such as the "plain" homomorphic version of RSA) will not provide semantic security. This is problematic, because for many applications of homomorphic encryption plaintext messages can then easily be guessed by "trial encrypting" potential candidates and comparing the ...


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