# Tag Info

36

But i wrote and tested a script in python that does exactly the story above. Yes, obviously it can happen; however you have to be a bit careful about how you do it to actually be secure. Here's is likely what your python script does; it generates a bitstring (based on the key), and xor's the bitstring and the plaintext together, generating the ciphertext (...

11

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations. Since permutations don't commute in general, a "perfect" commutative block ...

10

Breaking such a scheme is easy. Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = ... 7$\operatorname{ROT}(n)$is also known as the Caesar cipher.$\operatorname{ROT}(n)$can be thought of as a character based stream cipher. It works because addition - the encryption method used - is commutative. In other words$\operatorname{ROT}(x, \operatorname{ROT}(y, m)) = \operatorname{ROT}(y, \operatorname{ROT}(x, m))$. Another well known commutative ... 6 It can't be achieved under the assumptions you are making, because the attacker can distinguish it by selecting an arbitrary$k'$, and checking if$E(k')$commutes with the permutation in question. That is, to check a permutation$P$, we pick an arbitrary$x$, and check if:$E(k', P(x)) = P(E(k',x))$This equation always holds if$P = E(k)$for some value ... 6 If this works, depends on the encryption algorithm you use. It needs to have the special property$Enc_{K_1}(Enc_{K_2}(M)) = Enc_{K_2}(Enc_{K_1}(M))$. Most traditional encryption schemes (AES) do not have this property, the symmetric equivalent of RSA is the only one that I am aware of. EDIT: Stream cipher, if used correctly, work too. 6 This answer is supplementary to the one provided by Mikero. Assuming that the$\operatorname{map}$and$\operatorname{kdf}$functions are properly randomized and provide appropriate output (e.g. large enough to be non-repeating), then no two ciphertexts will share common factors. So being able to use$\operatorname{gcd}$to break ciphertexts is not ... 5 Yes, systems that allow this have a name: commutative encryption. In practice, there are two varieties: If A, B, C just xor in a keystream, it all commutes. Of course, anyone seeing the intermediate results can deduce quite a lot; this may make this unacceptable for some uses. Pohlig-Hellman (not related to the Pohlig-Hellman algorithm); we pick a global ... 5 This method of encryption is described in Section 9.5.1 of Mathematics for Computer Science by Lehman, Leighton & Meyer. They attribute this encryption technique to Alan Turing, but they say that they are working from just a textual description and are not sure exactly how to interpret the specific algorithm he had in mind. I don't know what their source ... 4 Any synchronous stream cipher, or block cipher in a stream-like mode of operation (such as counter-based modes), will have this property. That's because they are, in essence, stretching a user-supplied key to an arbitrary length, and then using it as an XOR mask to encrypt (or decrypt) the message. Since the message content isn't relevant to cipher stream, ... 4 Actually, there's the Pohlig-Hellman cipher (dating back to the 70's) that can do precisely this; it works like this: There's a large public prime$p$(for which the DLOG problem is hard) The secret key is an integer$x$that is relatively prime to$p-1$To encrypt a message$M$with key$x$, we compute$C = M^x \bmod p$To decrypt a message$C$with key$x$... 4 The classical ElGamal cryptosystem satisfies your requirements. Indeed, let us consider a group$\mathbb{G}$of prime order$p$and a generator$g \in \mathbb{G}$. Let$(h_1,h_2) = (g^{s_1},g^{s_2})$be two public keys for two random secret keys$(s_1,s_2)$. To encrypt a message$m \in \mathbb{G}$with the public key$h_1$, pick a random coin$r_1 \in \...

4

Here is an answer to your question using a zero knowledge proof in the case of Elgamal encryption. The biggest difference between this solution and your own is that Alice does not need to tell Bob the value of $r_1$ anymore. This makes the zero knowledge proof more complicated. Setting the scene: Let $\mathbf{G}$ be the group of prime order $p$ in which ...

4

Having spent a couple of nights thinking about this question, it seems to me that: there is no commutative block cipher that could pass your test, and in any case, indistinguishability from a random commutative block cipher is probably not a good measure of cryptographic quality, since it turns out that a random commutative block cipher is, with ...

4

What you are asking appears to be 'is AES commutative'? The short answer to which is no: encrypting with AES with key 1 then key 2 will not (generally) give the same output as encrypting with key 2 then key 1, which is what would be required for naive implementation. However, there are modes in which AES can be used which would be commutative. For example, ...

3

The right solution is to use a private set intersection protocol. Using Pohlig-Hellman is not the best approach. This problem has been studied in the literature, and there are sophisticated and effective solutions available; they go by the name "private set intersection". In other words, you are asking the wrong question. You have a particular ...

3

Yes, there are some other algorithms that do not rely on commutative encryption. The Wikipedia page for Mental poker lists some other examples. It describes a non-shuffling poker protocol that uses homomorphic encryption. It has this caveat, though: However, the method needs all cards that have already been dealt to be known to all, which in most poker-...

3

No, because CFB isn't commutative. You can see this by looking at the decryption of double-CFB encrypted ciphertext. Even assuming a constant IV (so single-use keys), if you decrypt in the wrong order it cannot work, since the ciphertext is used as input into the block cipher and will differ from what was used with that key when encrypting. The exception, ...

3

Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called "PSI with associated data" or "PSI with data transfer". For example, you can see this variant of PSI described explicitly in: Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear ...

2

One idea is to use normal hybrid encryption. Bob can reuse the symmetric ciphertext and encrypt the symmetric key (material) again using Carol's public key. With a proper choice of authentication in the symmetric part, Bob will be unable to find another key that correctly decrypts the ciphertext to some other message. For example, HMAC has this property, ...

2

The term you're looking for is commutative encryption. For instance, the following would work with any block cipher in counter mode, which uses a commutative operation (exclusive-or) for encryption: Alice, given a ciphertext $(\mathit{IV}_0,\mathit{cipher}_0)$ under Bob's key corresponding to some $\mathit{message}$, super-encrypts the ciphertext $\mathit{... 2 Please note: Authentication can't trivially be provided. Assume Alice is given the encrypted message$C=E_{K_B}(P)$, she wants to learn$P$without revealing$P$to Bob. Bob however is willing to serve as a decryption oracle for arbitrary messages. If$E_K(P):=P_K\oplus P$($P_K$being the pad generated by the cipher) then solving the above scenario is ... 2$\newcommand{\Enc}{\operatorname{Enc}}$Actually, Pohlig-Hellman exhibits a homomorphism and commutativity. For the commutativity, see poncho's answer on your other question. The homomorphism goes as follows (it is really just plain multiplication, not unlike what is possible with textbook RSA):$$\Enc(m_1)\cdot\Enc(m_2)=m_1^a\cdot m_2^a=(m_1m_2)^a=\Enc(... 2 Your protocol won't work if the encryption scheme is randomized. In fact, the commutative property would be that$D(D(x,priv_a),priv_b)=D(D(x,priv_b),priv_a)$, which is different than$E(E(x,pub_a),pub_b)=E(E(x,pub_b),pub_a)$. A deterministic encryption scheme cannot be semantically secure. So if a scheme could meet the requirements to be used in this ... 2 I believe this protocol should be satisfying the requirements of an Oblivious PRF. This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis: Parameters: A multiplicatively-written Group$\mathbb ...

2

This isn't a direct answer to the question, because the other answers have that well in hand. However, I thought it may be helpful to add a note about why one time pads work, and why this isn't one. There is a common perception that a OTP is just a function where the key is as long as the plaintext. However, that doesn't work. For a very easy scheme to see ...

2

Let a signed message consist of a bit string $m$ and a set of signatures $\Sigma$. A ‘signed message’ of a bit string $m$ with no signatures is $(m, \{\})$. When the $i^{\mathit{th}}$ user signs $(m, \Sigma)$, they return $(m, \Sigma \cup \{\sigma\})$ where $\sigma = \operatorname{Sign}_{S^i}(m)$. The verifier confirms that there are signatures by all the ...

2

Rather than using a commutative encryption scheme, I'd suggest looking at private set intersection. From the description in your first paragraph, it sounds like that's what you're looking for.

1

If you define $E_a(M) = M \oplus a$ then the key $ab$ can also be defined as $a \oplus b$ as follows: $E_b(E_a(M)) = (M \oplus a) \oplus b$ $E_{ab}(M) = M \oplus (a \oplus b)$ However using the same key and/or message more than once in XOR will leak the other one. So I think it's potentially not what you're looking for. As far as I know, SRA is also a ...

1

You were on the right track with Yao's Millionaires Problem. Yao's Millionaires Problem is just one specific example, but almost anything can be calculated securely by using by a garbled circuit. @mikeazo is right that if Bob chooses 1, then he'll always know Alice's choice. However, if Bob chooses 0, then the output of the circuit will always be 0, so Bob ...

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