Minimum of two values with minimum knowledge
Minimum of two values with minimum knowledge
Hey! I program a lot but I'm not very good with cybersecurity and stuff, although I have a basic usage of GPG and asymetrical encryption.
My problem is:
Let's imagine that Alice (A) and Bob (B) each have a file with a number written in it.
Ideally, I'd like a program that A can run on her computer that would take the B file but encrypted, and output the minimum of the two values contained in A and B files.
But without any way for A to know what the number of B is, except if B value is the minimum, obviously.
Can someone help me with that? Thank you for reading!
If A can run this program at will and it determines the minimum value, it's O(log(n)) to determine what B is, even with perfect encryption, by using arbitrary values of A.
INT X = MAX INT PREV_X = 0 BOOL B_IS_MIN = True
While (X != PREV_X){
PREV_X = X B_IS_MIN = Encrypted_Min(X,B)
If(B_IS_MIN), X = X/2 If(!B_IS_MIN), X = X*1.5
}
Unless I've made a typo, this psuedocode will step to B in log time, and will break the while loop once it's found, even if the user has no way to know the value of B besides the minimum.
Indeed, I didn't think of that. And would it be possible to allow only one check and destroy/make the information of B unusable after this check?
Thank you for your reply!
With some more restrictions, you may want to look into oblivious transfer https://yewtu.be/watch?v=wE5cl8J27Is
Possibly. I'm not a big crypto guy, but it's my understanding that any kind of transaction has a chance of being repeated. If there were a bad actor, and that bad actor used a VPN to swap identities, he could narrow this down considerably and weaken encryption. My code is as dumb as it gets, willing to consider 1 as a valid encryption key, but smarter code would be a lot more efficient.
On top of that, you wanted this minimum code to run on A's computer. If you do not trust A, then you've given a potential bad actor a program that could be decompiled to unencrypt your keys.
It sounds to me like in your current state, you need to trust A before you do this operation, and if you do, you can just share an unencrypted B.
Why do I feel like I am reading the synopsis for your year end project? Alice and Bob (and eve, that's you) is an old scenario used in school. If that's the case go back and watch your lectures, study with friends. Do not try and use chatgpt because other professors will see through that too. Bon chance, Aimee.
That comment is neither helpful nor interesting criticism. It's not even pleasant to read.
- I don't understand why you say I'm Eve.
- I don't have any formation in cybersecurity, so no "lectures to go back and watch"
- It's not even a school project of any sort
- I was not planning on asking chatGPT, but I'm sure its answer would actually be more helpful for my problem than your comment
I used Alice and Bob because I read stuff with this scenario and liked it, that's all...
Maybe you thought that warning/advice would be helpful, but for me at least, it just sounds very paternalistic.