# Tag Info

9

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $IND-$ notation ...

7

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect? Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...

5

Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.

4

Spartacus: Maybe i came out with the solution, since the cryptosystem described above is not CCA-secure, an adversary A can intercept (A,B) and compute a new ciphertext $$C = 2B\bmod N = 2^er^e \bmod N$$ Since he's carring out a CCA-attack he has access to a decryption oracle and since: $$C\neq B$$ the oracle output RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\...

3

I am stuck at the point where I proved that the complexity is $O(2^\rho)$ using brute-force approach. How shall I proceed? Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy. Instead, what we typically do in a proof is assume that the adversary had some ...

3

I'll answer question 2, leaving the first as an exercise to the reader. I'll do this on intuitive grounds, rather than using explicit conditional probabilities. The adversary is free to compute $v_1\cdot v_2$ regardless of what we ask, therefore removing everything about that and $v_3$ does not change the problem, which reduces to: We somewhat have ...

3

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? This is up to your security ...

2

(Note: This answer is based on $k$ being generated by applying a pseudorandom function to a unique message-ID ā counter ā each time.) It depends how many times you want to encrypt with it. If you want it as a complicated OTP, then it's secure. In order to see this, just ignore the $x$ parts and note that $s_1m \bmod p$ and $s_2m \bmod p$ are to independent ...

2

If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it? Nope; FHE allows a server that knows $E(m_1)$ and $E(m_2)$ to produce a ciphertext which is a representation of the value $E(m_1 \odot m_2)$ (for pretty much arbitrary functions $\odot$); what it doesn't allow a server to do is determine whether $m_1 = m_2$...

1

The algorithm $E'(m)=E'(k,m)=E(0^n,m)$ is defined with a hard-coded key, thus the key is part of the algorithm definition of $E'$. Because of Kerckhoff's principle we generally assume the attacker to know our algorithm definition. Because of this, the attacker can just try decrypting the challenge ciphertexts of the eavesdropper security game himself (or ...

1

There are two styles of definition that deal with the issue of message "length" in different ways. One style considers an encryption algorithm that is capable of encrypting bit strings of arbitrary length. Such an algorithm cannot completely hide the message length, for information-theoretic reasons. (Padding short messages to conceal their lengths doesn'...

1

Proposition One-wayness of ElGamal encryption holds under the Computational Diffie-Hellman (CDH), and conversely. CDH Problem (informally) Given $(P, [r]P, [s]P)$ find $[rs]P$. Let the public key be $Q = [s]P$ where $s$ is the corresponding secret key. Let also a ciphertext $C = (C_1, C_2)$ with $C_1 = [r]P$ and $C_2 = M + [r]Q$ for a message $M$ (...

1

The author does not define hybrid PKE schemes. What is their definition? A hybrid public-key encryption scheme is a scheme that uses public-key encryption along with symmetric encryption to gain speed advantages for long messages. The usual instantiation is to simply encrypt a key for the symmetric scheme and prepend the resulting cipher text. The more ...

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