Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm looking for a one-way hash function that can be performed by A on an encrypted piece of data E(D) provided by B, without the performer A able to figure out D or H(D). This similar to HMAC(Message, Key), except the output hash cannot be known by A.

Usage:

  • B encrypts data D => E(D)
  • B sends E(D) to A
  • A contains a secret key SK
  • A performs F(E(D), SK) => E(H(D))
  • A sends E(H(D)) to B
  • B decrypts E(H(D)) => H(D)

Constraints:

  • A cannot recover D
  • A cannot recover H(D) from E(H(D))
  • B cannot recover SK from E(H(D)) or H(D)

I believe there may be a solution involving public/private key cryptography, but I'm not about to roll my own.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

If you are not limited to HMAC, blind signatures would meet your requirements.

In RSA, you can do blind signatures as follows:

Let $M$ be the message to be signed (probably the hash of a message) and let $e,N$ be A's public key, $d$ is A's private key.

B computes $M' = M\cdot r^e \bmod{N}$ and sends $M'$ to A.
A computes $S' = M'^d\bmod{N}$ and sends it to B.
B computes $S = S'\cdot r^{-1}\bmod{N} = M^d\bmod{N}$ (i.e., $M$ signed with A's private key).

I am not aware of any libraries that support this scheme out of the box, but it wouldn't be too hard to add the functionality. Also, other cryptosystems would support this idea too.

Homomorphic Encryption
Using fully homomorphic encryption, this would be very possible to do. You would just need to implement a homomorphic version of a hash function and build it up into an HMAC function. Given current public-key homomorphic technology, it would be very slow. Still, though, this technology is too new for deployment.

Garbled Circuits
Another option for implementing HMAC that should meet the requirements you have stated is garbled circuits. Garbled circuits can evaluate AES privately much faster than even the most optimized version of homomorphic AES. Which suggests that a hash function could be practical to compute using a garbled circuit.

share|improve this answer
    
I'm not limited to HMAC, it was just the closest function I could think of. Thanks for the answer, I'll have to study the algorithm more carefully but it looks promising! –  Ian Wetherbee May 1 '12 at 16:29
1  
@IanWetherbee, HAC has a good section on blind signatures –  mikeazo May 1 '12 at 16:33
    
Great, would you see any problems with extending this to be signed by multiple nodes then returned? So node C signing S'' = S'^sk_c mod N, S''' = S''^sk_d mod N, ... , S_acd = S'''*r^-1 mod N. I don't see any since exponentiation can be done in any order, but just checking. –  Ian Wetherbee May 1 '12 at 16:52
    
@IanWetherbee, I haven't thought of any reason it won't work yet :) –  mikeazo May 1 '12 at 21:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.