Cybersecurity

5759 readers

64 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 2 years ago

MODERATORS

[email protected]

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

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

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 (5 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 (4 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!

load more comments (2 replies)