Minimum of two values with minimum knowledge

shifty51, 5 months ago

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.

payasson, 5 months ago

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.

Khanzarate, 5 months ago

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.

payasson, 5 months ago

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!

Khanzarate, 5 months ago

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.

payasson, 5 months ago

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

mattreb, 5 months ago

With some more restrictions, you may want to look into oblivious transfer yewtu.be/watch?v=wE5cl8J27Is

payasson, 5 months ago

that’s interesting indeed! thank you very much!