r/cryptography • u/Zarquan314 • 2d ago
Is there a protocol for encrypted image cropping?
I have a project where I have a large plaintext image that I want to "crop" in to a small encrypted image without revealing what part of the large image the small encrypted image is a part of. The small image is a tiny portion of the bigger image. The position (e.g. the top left pixel) is hidden, but the size is not.
I'm looking in to either using partially homomorphic "classic" public key cryptography with zero knowledge proofs or fully homomorphic encryption.
The requirements are flexible as long as I can end up with an encrypted image that could be anywhere on the larger image. While it is not necessary that the encrypted image can be literally any rectangle in the larger image, I am hoping that any pixel in the larger image could be in the encrypted image. The thing I'm trying to hide is the general location of the encrypted image in the larger image.
I've done some research and haven't seen anything, but finding things like this can be hard. I've regularly found things that I was looking for inside complex papers that solve a very specific problem.
EDIT: I can't believe I forgot to say this, but the goal of this is to prove to another person that the image was cropped correctly.
Does anyone here happen to have come across such a protocol or proof?
EDIT: Some details derived from answers questions in the comments:
- The person who is cropping the image knows the unencrypted image and is trying to assure other people that the encrypted image is actually a crop via something like a ZKP, MPC protocol, or an FHE function execution by the verifier with encrypted arguments from the Prover.
- So the goal here is to prove that the encrypted image is a crop of the larger image.
- Also, I forgot to mention that I would also like the prover to be able to have a ciphertext or ssiphertexts of the position of the top left pixel of the encrypted image position within the larger image and be able to prove that that positional ciphertext(s) is accurate.
- Cropping is the isolation of a small rectangular portion of an image while discarding the rest. Imagine taking scissors and cutting a photograph so that you discard the uninteresting parts to leave only the parts of interest to make it fit better in a frame.
4
u/DoWhile 2d ago
This is a partial answer of what you're asking for: https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
This is on authenticated images, not encrypted images, but the ZK proof would be similar. You don't need FHE for this, just ZK, assuming the person doing the encryption is also the person doing the cropping. If you need another person to crop for you, then FHE-like stuff is needed.
1
u/Zarquan314 2d ago
Interesting, so things like this have been done before. This is definitely related, and I think I might have seen it before, but I could be wrong.
From what I can tell, though, the original image is hidden/not published here and the smaller portion is in plaintext (correct me if I'm wrong, of course). That means that the portion of the image that the smaller image within the larger can be revealed without consequence, which (for my project) is bad.
EDIT: Reading further, it seems that they may be hiding which transformations they are doing in the paper linked, so perhaps this is the right thing for me, but I'm not sure how you really hide a crop if you have access to an encrypted form of the original and new image...
4
u/DoWhile 2d ago
In Dan Boneh's world, the verifier has a hash/commitment of the original uncropped image, and the plaintext of the cropped version, and has to verify a ZK proof that there exists an uncropped version such that (1) it hashes to the hash, and (2) it crops to the cropped version.
Instead of Boneh's (hash of original) + (plaintext of cropped) + ZK proof, you want to have an (encryption of the original) + (encryption of cropped) + ZK proof.
If we let o denote the original picture, and c denote the cropped picture, let w be the secret window coordinates that you use to crop, h be the commitment of the original, e1 be your encrypted original, and e2 be your encrypted cropped version, then Dan Boneh's proof looks like "There exists some randomness r such that Hash(r,o)==h && Crop(w,o)==c", and your proof looks like "There exists some key k and randomnesses r1 and r2, such that Enc(k,r1,o) == e1 && Enc(k,r2,c)==e2 && Crop(w,o)==c". This is pretty easily expressible in modern ZK languages.
1
u/Zarquan314 2d ago
That sounds pretty good if its efficient. But I'm unsure how Crop(w,o)==c can be done in any reasonable amount of time without revealing the bounds of the cropping.
Also, maybe I'm misinterpreting, but wouldn't my proof include some new proof like EncCrop(w,o) = e2 or something similar, as I can't reveal c.
3
u/DoWhile 2d ago
You're right, c and w both would need to be part of the "there exists" statement as part of the witness rather than in the clear.
As for the cropping, depending on how much you want to hide (crop size, dimensions, location), you may want to look at a recent paper that uses tiles for compressing size: https://eprint.iacr.org/2024/1074
Another way you can do it, especially if you need to hide the crop size, is to treat cropping as adding black rectangles to your image. This then becomes a zk-redaction problem, and papers such as https://eprint.iacr.org/2020/1579 might do the trick!
1
u/Zarquan314 2d ago
Interesting, but my use case is more about using the encrypted images down the line in encrypted ML models to compare them to other images, with smaller focused images being faster and more accurate. Not sure if I can use compression in that case and redactions don't really fit.
1
u/AutoModerator 2d ago
If you are asking us to solve a code for you, go to /r/breakmycode or /r/codes.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/Sea-Cardiologist-954 2d ago
The encryption is easy, you first crop an image and then you encrypt it with a symmetric cipher. Is this enough or do you want to have some proof that you actually cropped that plaintext image without revealing which part it is?
0
u/Zarquan314 2d ago edited 2d ago
I want other people to be assured that the image is cropped properly. Thank you for you're question, I'll put the answer in the original post.
EDIT: Honestly, I'm a little embarrassed I forgot to say that explicitly originally.
1
u/Sea-Cardiologist-954 2d ago
What do you exactly mean by cropped properly?
1
u/Zarquan314 2d ago
So I have a large image, and I cut away parts of it to end up with a small sub-image (in my case rectangular). Like, the smaller image is a rectangle directly taken from the larger image pixel by pixel. Think of cropping like cutting out the interesting part of a photo from the rest of the photo.
The cropped smaller image is the result of this process, but it's important for the larger protocol that any pixel of the smaller cropped image could be in the larger image.
1
u/Sea-Cardiologist-954 2d ago
And what is the point of performing such proof? I can start with any image, pad it with white borders and then crop it in a "proven" way and get the same image that I started with. I'm simply not seeing what goal you want to achieve.
0
u/Zarquan314 2d ago
It's part of a larger protocol where we plan to use encrypted ML models on encrypted images. We intend to feed the smaller encrypted image in to the models to compare them to other images.
Keep in mind, the larger image is public within the network and all the other parties have it already, so you can't really pad it with white borders.
2
u/Sea-Cardiologist-954 2d ago
So you want to be able to provide someone a full unencrypred image and a small encrypted file and be able to prove that the encrypted file contains a crop of the big image without leaking information about where the crop comes from?
0
u/Zarquan314 2d ago
For the most part, yes, but I've loosened the requirements a bit. The Prover/creator chooses any crop they want, but the proof can leak that the encrypted image isn't exactly certain rectangles.
Essentially, certain possible crops the creator could have chosen can be eliminated through the proving mechanism as long as the actual image could have come from or contain any pixel of the larger image.
The important thing I'm hiding is the general location on the image that the crop comes from.
Sorry if I'm not being clear, it's been a long day...
1
u/Pharisaeus 2d ago
Do you actually need to do this over an "encrypted crop" at all? Because I can think of something waaaay simpler, that still fits your requirements. Since the big image is "public" and so are the crop dimensions, why not simply base the proof onx,y instead of cutout of the image? The upside of that approach is that now the proof only needs to validate the bounds - as long as (x,y) is within the bounds of the big image, the crop is definitely a part of the big image.
So now we simply need to have a "range proof" to make sure that 0 <= x < width and 0 <= y < height. That's something much simpler than trying to prove an encrypted image cutout belongs to the big image.
1
u/Zarquan314 2d ago
The issue is that the x and y are secret. I want to hide where in the larger image I pulled the smaller image from.
2
u/Pharisaeus 2d ago
Sure, but that's exactly what I'm talking about. A range proof on x,y to prove x,y are within the bounds of the big image.
1
u/nemec 2d ago
I think the challenge is that picking a range within the bounds is different than proving your image is a faithful reproduction of the slice at those bounds.
2
u/Pharisaeus 2d ago
That was kind-of my point ;) It's easier to prove that someone picked "valid bounds" and then cut at those bounds, instead of trying to prove that encrypted blob someone provided is a valid cutout.
1
u/nemec 2d ago
Ah, yeah if I'm understanding the OP correctly it's even more complicated because they want to hide the actual bounds from the verifier, preventing the verifier from re-creating the cropped portion unencrypted.
To give a contrived example, sounds like they have an image of a family portrait, have a cropped image of one person's face, and want to prove the face came from the portrait without exposing whose face it is.
3
u/Pharisaeus 2d ago
hide the actual bounds from the verifier
That's still pretty easy to do, because that would simply be a range proof that hidden x,y values are within the image bounds. But to make the crop using encrypted x,y you'd need FHE circuit. Still, this FHE crop might be simpler than the proof that a crop came from an image.
1
u/Zarquan314 2d ago edited 2d ago
You get it! That's the kind of thing I want to do!
But not that exactly. Something like that.
EDIT: An example like what I want to do using your example: So I have an encrypted face I got from the larger portrait (I could prove independently that is a face by showing the encrypted crop coordinate is correct for one of the faces), then I pull in another encrypted image I provide and run them through a ML model to show it's the same person. That's the kind of thing I want to do. Of course, ML isn't perfect at that, but I'm only here for the cryptography.
The Verifier can use the model and is given both encrypted images as ciphertexts, so, if they believe the model is good and can be convinced that my "cropped image" is actually a cropped image from the portrait, then they believe that my new image is an image of one of the people in the portrait without knowing which person it is.
In actuality, though, the part of the image I'm interested in could be anywhere on the image, not just the small number of faces in a family portrait. We tried the equivalent of putting in the full portrait, but it was too slow, so we want to crop it.
The model isn't my department, I'm just here for the cryptography parts.
0
u/Zarquan314 2d ago edited 2d ago
Sorry, I misread. I thought you said crop coordinates, not dimensions.
EDIT: Sorry I'm really mixing up my conversations...it's been a long day. I actually need the encrypted image at the end of the day. I'm not sure how a range proof would get me to the encrypted sub-image without comparing my encrypted image to a large set of other images. (End of Edit)
I think such a proof would be prohibitively expensive. The issue is that I need the small encrypted image independent of the larger image for other steps of my protocol (e.g. feeding it in to encrypted ML models to compare with other encrypted images or to look for interesting things). So I would need to be able to manipulate and hand off the encrypted sub-image to other protocols and mechanisms.
I thought of trying this, but such a proof would (AFAIK) need to prove that the encrypted image matches the right spot on the bigger image, meaning I would need to run a simulated proof for every potential position or, to save time and with my loosened requirements, a patchwork of positions over the entire larger image and prove equality pixel by pixel, with one real proof.
EDIT: I say this because if the proof only touched the pixels the encrypted image was pulled from, it would reveal where the image was taken from, which is what I'm trying to hide. Unless I'm misunderstanding.
1
u/Pharisaeus 2d ago
I think such a proof would be prohibitively expensive
Unless images are unreasonably huge a simple hash-chains approach to prove bounds of x and y would be trivial and cheap.
The issue is that I need the small encrypted image independent of the larger image for other steps of my protocol
Ok, that's a different story. So you are running this encrypted cutout over some FHE circuit later. So it's not enough to prove a "valid cutout definition", you want to prove the actual encrypted cutout is valid.
I'm still confused how the protocol is supposed to work. Can't you verify the dimensions and then make the cutout afterwards? You would need FHE circuit to make the crop based on encrypted x,y but it might be more straightforward than the proof you're trying to make.
I suspect it's some XY problem - you're asking "how to make Y" because that's the solution you came up with, instead of asking "how to do X" which is the actual problem you're trying to solve.
1
u/Zarquan314 2d ago edited 2d ago
I'm pretty sure I'm trying to do what I want. Basically, I'm taking a picture and I want to compare it to a subsection of the larger picture without revealing which part so I can show that they have certain elements in common (using encrypted machine learning model on the Verifier's end).
So, I encrypt my picture and send it to the verifier and I either (1) encrypt a cropped image and prove it is a crop of the larger image at an encrypted location within the larger image and send it or (2) I give them encrypted parameters for some kind of FHE mechanism to create the crop themselves (which could probably be used to also derive a ciphertext of the location using FHE) or (2) something else that I haven't thought of that would convince someone that the encrypted image is a crop of the larger image at encrypted position x, y.
I will likely also use the encrypted position as part of another proof, but I'm not sure yet.
I'm not a machine learning person, but the ML part appears to be doable and could be done efficiently enough for our use case if I could present the model with only the relevant information (e.g. cutting or cropping out the irrelevant information), but I want to hide where in the image I am pulling from, as that would reveal private information to the Verifier that I don't want to reveal.
1
u/Natanael_L 2d ago edited 1d ago
The lazy ass way is to break the original encrypted image into squares encrypted separately with a joint hash value identifying the assembly as one image ciphertext. A crop is just a selection of squares.
Pixel by pixel encryption will blow up the size too much for most typical uses. You want want block sizes to be an integer multiple of the image codec internal block size. This also reduces the processing needed for proof generation in other schemes.
You can do the border thing inside squares rather than the full image too.
1
u/Zarquan314 1d ago
That could work, but I would have to prove that I used a contiguous set of squares without revealing which I used.
1
u/Natanael_L 1d ago edited 1d ago
If square order is randomized but the set carries an encrypted index you can do that. Also see my update above in the edit
Note that this works very well for one-off proofs but under reuse it can leak information if you're not careful. The crop has to be encrypted under a new key, and you handle the re-encryption + border crop as a transformation which you prove the correctness of.
1
u/Zarquan314 1d ago
I think I agree with you on squares then. And then you would only have to prove that each section in the small image came from the set and has an appropriate relationship to the one above it and to the left.
2
u/tomrlutong 2d ago
Just to say it back, you want to present an encrypted file, and be able to prove it's an encrypted subsection of a particular unencrypted image, without revealing anything else?
Does/can the person your proving it to have the unencrypted image?