Cybersecurity

5758 readers

97 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

Be respectful. Everyone should feel welcome here.
No bigotry - including racism, sexism, ableism, homophobia, transphobia, or xenophobia.
No Ads / Spamming.
No pornography.

Community Rules

Idk, keep it semi-professional?
Nothing illegal. We're all ethical here.
Rules will be added/redefined as necessary.

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 [email protected] [email protected] [email protected] [email protected] [email protected] [email protected] [email protected]

Notable mention to [email protected]

founded 1 year ago

MODERATORS

kid

[email protected]

Minimum of two values with minimum knowledge (jlai.lu)

submitted 11 months ago by [email protected] to c/cybersecurity

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!

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 5 points 11 months ago (1 children)

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.

[–] [email protected] 0 points 11 months ago (2 children)

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!

[–] [email protected] 3 points 11 months ago (1 children)

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

[–] [email protected] 0 points 11 months ago

that's interesting indeed! thank you very much!

[–] [email protected] 1 points 11 months ago (1 children)

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.

[–] [email protected] 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