13
Minimum of two values with minimum knowledge (jlai.lu)
submitted 11 months ago by payasson@jlai.lu to c/cybersecurity@sh.itjust.works
8 comments fedilink hide all child comments

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!

top 8 comments
sorted by: hot top controversial new old
[-] Khanzarate@lemmy.world 5 points 11 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@jlai.lu 0 points 11 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!

[-] mattreb@feddit.it 3 points 11 months ago

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

[-] payasson@jlai.lu 0 points 11 months ago

that's interesting indeed! thank you very much!

[-] Khanzarate@lemmy.world 1 points 11 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@jlai.lu 0 points 11 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

[-] shifty51@sh.itjust.works -1 points 11 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@jlai.lu 1 points 11 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.

this post was submitted on 22 Dec 2023
13 points (93.3% liked)

Cybersecurity

5734 readers
11 users here now

c/cybersecurity is a community centered on the cybersecurity and information security profession. You can come here to discuss news, post something interesting, or just chat with others.

THE RULES

Instance Rules

Community Rules

If you ask someone to hack your "friends" socials you're just going to get banned so don't do that.

Learn about hacking

Hack the Box

Try Hack Me

Pico Capture the flag

Other security-related communities !databreaches@lemmy.zip !netsec@lemmy.world !cybersecurity@lemmy.capebreton.social !securitynews@infosec.pub !netsec@links.hackliberty.org !cybersecurity@infosec.pub !pulse_of_truth@infosec.pub

Notable mention to !cybersecuritymemes@lemmy.world

founded 1 year ago
MODERATORS
kid@sh.itjust.works
Lanky_Pomegranate530@midwest.social