Can you re-encrypt data without knowing what the data is or using PRE?

Question

I'm currently working on a distributed consensus-based system. I currently give the system a private key through a threshold encryption model, and I want to be able to take some data encrypted with the network's public key and re-encrypt it with an arbitrary public key without any member of the network knowing what the data was.

I know proxy re-encryption is a good solution if the person who originally encrypted the data creates a re-encryption key, but this needs to be a specific key rather than an arbitrary one making it not suitable for such a use-case.

In the following question that was asked, a comment concerning the ability to simply re-encrypt the data with one's own public key and decrypt it themselves would be of concern. In this model, I believe I have solved that aspect by requiring the network to come to a consensus to re-encrypt anything.

Re-encryption without knowing the secret

I would love to know if something along these lines is even possible or if I'm just out to lunch.

Answer 1

I'll assume we're dealing with a Diffie-Hellman like "encrypt to public key" operation. Notation will be additive. Public points are uppercase, private scalars are lowercase.

Normal DH for a public key group element Y=y*G picks an ephemeral secret scalar r and does SHARED_SECRET=r*Y , HINT=r*G then encrypts the message using the SHARED_SECRET producing the tuple (HINT,encd_bytes)

The holder of the y private key can do SHARED_SECRET=y*HINT=y*(r*G) to re-derive the shared secret and decrypts the encd_bytes.

re-encrypting

It's possible to derive a new hint value that will work with another public key X=x*G ... but the process needs either r or y to find the SHARED_SECRET and x to calculate a value that when multiplied by x yields that shared secret. This is not that useful since the private part of the public key targeted likely isn't available. The problem here is that a naive DH decryptor is expecting to get a point and just multiply by their secret scalar to get the shared secret.

If we can modify the decryption process slightly we don't need to do that. The key is to do another DH encryption to get another shared key and send along an OFFSET point to be added to get the original shared secret. Decryption now consists of doing SHARED_SECRET=y*HINT+OFFSET then decrypting on the tuple (HINT,OFFSET,encd_bytes)

SS1=y*HINT1 re-derive shared secret

SS2=s*X new shared secret

HINT2=s*G new hint

OFFSET=SS1-SS2 offset to generate old shared secret

Since everything above is additive, additive key shares can be used to compute parts of the above values to be added together. If the private key is split into n parts (y[0],y[1],...y[n]) each key share holder can choose an s[i] and send additive shares for the final (HINT,OFFSET) values.

SS1[i]=y[i]*HINT1

SS2[i]=s[i]*X

HINT2[i]=s[i]*G

OFFSET[i]=SS1[i]-SS2[i]=y[i]*HINT1-s[i]*X

Putting that all together

s=sum(s[i],i=(0...n)) secret shared ephemeral scalar

y=sum(y[i],i=(0...n)) shared secret network key

HINT2=sum(s[i],i=(0...n))*G=s*G

OFFSET=sum(y[i]*HINT1-s[i]*X,i=(0...n))

=sum(y[i],i=(0...n))*HINT1 - sum(s[i],i=(0...n))*X

=y*HINT1-s*X

So yes, this should work with additive shares

There's probably a zero knowledge proof to show each key share holder did the calculationcorrectly via something like this How can we prove that two discrete logarithms are equal? but more complicated.

Note that this can be repeated. If you already have a tuple (HINT,OFFSET,encd_bytes) it can be re-targeted to another public key by doing the above procedure and adding the two offsets.

Answer 2

The ability of re-encrypting the data to arbitrary public key implies the ability of decryption.

So, you can simply upload your secret key in a secret-shared form to your network nodes. With consensus, they can run a "decrypt then encrypt" procedure. This procedure could be run in an MPC way so that the intermediate plaintext is not revealed.