10

First, remark that the desired commutativity is incompatible with security under Chosen Plaintext Attack, which (under the name IND-CPA) is considered a requirement for modern encryption systems. Proof, expanded following tylo's comment, using the IND-CPA game as played for symmetric encryption (see the CPA indistinguishability experiment in section 3.5 of ...


8

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...


4

In general, from a security analysis viewpoint, there isn't much difference between a peer-to-peer protocol and one using an untrusted server — and, insofar as there is any, the peer-to-peer case is strictly harder to secure. This is because, if we have a secure peer-to-peer protocol, we can always implement it over an untrusted server by simply ...


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


2

Unfortunately, if you want advice on a specific patent, I'm afraid you are most likely going to need to consult with a lawyer. The odds of getting reliable authoritative advice over the Internet are... not so great, in my experience. Generally speaking, this site focuses primarily on technical questions (which are answerable by many in the community here) ...


2

You are in a twist here: semantic security (equal to IND-CPA) can only be fulfilled by probabilistic encryption schemes. You need a deterministic encryption scheme for your drop-out tolerance. As it was pointed out previously, any homomorphic encryption allows you to proof in zero knowledge the equality of two ciphertexts: known: $c_0 = E(x,r_0)\;,\;c_1 = ...


2

Three issues: It is super slow. The "Oops, my bad, I need to redraw" is not correct because he can always say that when he gets anything but a king or a queen. Alice could also probably pretend she has a better deck than she has (with a nice probability of not getting caught).


1

The attack you are referring to is called an offline dictionary attack, which checks all possible values against a given transcript. However, the typical security notion for the socialist millionaires problem should forbid this attack. In fact, designing a protocol which is secure "except for offline dictionary attacks" is trivial: both players simply hash ...


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


1

The answer to your specific scenario is no, it cannot be done. As mentioned in a comment, if Bob knows his preference (B->A) and learns that the result of the calculation is $0$, then Bob now knows Alice's preference, i.e., A->B is 0.


1

With any convergent encryption algorithm E, it's easy for Alice to prove -- without revealing(*) a, b or the private key -- that a == b. In order for the data deduplication feature to work, convergent algorithms are specifically designed such that when Alice encrypts two messages a and b, such that x=E(a), y=E(b), then x == y whenever a == b. There's some ...


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