Alice and Bob have a function they want to evaluate. For example, maybe they want to determine the maximum of their two numbers, without having the other player reveal what their number is.
To do this, they start a conversation. There are “rules of engagement” they have agreed upon, but at any point Alice may stop adhering to them. For example, she may just stop participating in the protocol. We would like to say that if Alice does this that no one gets to learn the maximum of the two numbers, but its not quite true (and if you think hard, it can’t be quite true). Instead what happens is that, depending on when Alice stops cooperating, it will take her a certain amount of computational effort to learn the maximum of the two numbers (and she will never be able to learn anything more). Bob can also learn the maximum of the two numbers, but it will take him just a little bit more computational effort.
Can you explain secure function evaluation some more? What is meant by Alice “cheating”?
Alice and Bob have a function they want to evaluate. For example, maybe they want to determine the maximum of their two numbers, without having the other player reveal what their number is.
To do this, they start a conversation. There are “rules of engagement” they have agreed upon, but at any point Alice may stop adhering to them. For example, she may just stop participating in the protocol. We would like to say that if Alice does this that no one gets to learn the maximum of the two numbers, but its not quite true (and if you think hard, it can’t be quite true). Instead what happens is that, depending on when Alice stops cooperating, it will take her a certain amount of computational effort to learn the maximum of the two numbers (and she will never be able to learn anything more). Bob can also learn the maximum of the two numbers, but it will take him just a little bit more computational effort.