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!
You're viewing a single thread.
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
that's interesting indeed! thank you very much!
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.
Alright thank you for your reply, I'll think about it :) maybe having a vérification that can be done in any computer and any amount of time is just not possible for my use case