[PET] Homomorphic hashing?

Alfonso De Gregorio adg at beewise.com
Thu Nov 3 09:57:08 GMT 2011

Dear Jason,

On Mon, Oct 31, 2011 at 3:04 PM, R. J. Cronk <rjc at privacymaverick.com> wrote:
> I'd like to be able to take two numbers and do a greater than comparison x <
> y.  However, I'd like to be able to do this without knowing x and y.  This
> might be useful in blind bidding where I want to compare two bids without
> actually revealing the bid. Is there such a thing or can anybody suggest an
> alternative method?
> Jason

A secure multiparty computation protocol -- the Millionaire's problem
-- for comparing two quantities without disclosing their values to
each party was provided by Andrew Yao in "Protocols for secure
computations", pp.160-164, 23rd Annual Symposium on Foundations of
Computer Science, FOCS 1982.

How to do the same with an homomorphic encryption scheme? I've asked
myself the same question in the context of cryptographic counters
based on  an additive homomorphic cryptosystem. Here's a protocol I've
sketched at http://plaintext.crypto.lo.gy/article/661/privacy-preserving-comparison-of-cryptographic-counters

It is worth to note how we don't want a construction where the
comparison is a public-key operation, otherwise it might be used to
establish total order between counters or their updates.

The protocol below allow an entity with knowledge of the public-key to
create and update two cryptographic counters and let the private-key
owner to compare them for greater-than, less-than, or equality without
disclosing the counters' plaintext values.

Let's assume that:
- the plaintext counter is defined over Z*  (*), and
- the entity with access to the private-key can ask to compare the
cryptocounter at most one time between increment/decrement operations.

*) How to enforce this requirement while using the Paillier PKCS?

Let A and B be two cryptocounters and the difference be defined over
encrypted data.

The entity with access to the public-key starts computing:

/* The differences among counters */
1. diffAB = A - B
2. diffBA = B - A

/* a new string of size l uniformly at random */
3. r <- R{0,1}^l

/* the product of the differences by the random quantity */
4. d1 = diffAB r
5. d2 = diffBA r

The entity with access to the private-key can computes:
6. if D(d1) > 0 then A > B
7. if D(d2) > 0 then B > A
8. else A = B

As always, I very welcome improvements and alternative methods :-)


BeeWise - Security Event Futures  http://beewise.org/

More information about the PET mailing list