Distributed computing

MIGHT A COUNTERFEIT AMAZING SAND COUNTER SUCCEED

• Can the tester use the Amazing Sand Counter’s knowledge to masquerade as the Amazing Sand Counter?

REPLAY ATTACKS AND TIME

• Tester T can use a replay technique:
• T claims to U that T is an Amazing Sand Counter.
• U presents a bucket to T.
• T removes the bucket and shows it to S, pretending to engage S in yet another test.
• U asks T to leave the room and removes some sand.
• T returns, but asks for a little time.
• T then shows the bucket to S.
• S says how many grains have been removed.
• T repeats what S says to U.
• To prevent this, a site must distinguish replayed messages from current ones, perhaps by signatures.

Crypto puzzle 1: Fagin/Vardi management dilemma

• Sometimes one doesn’t need zero knowledge, but just the answer to a yes/no question.
• An employee E complains to boss B1 about some person P1 and to boss B2 about P2.
• B1 and B2 confer and want to determine whether P1 = P2. If not, though, neither wants to reveal its Pi, nor ask any more of E.
• Is there a good non-computational technique to figure this out? Assume the set of possible people is just the list of people in E’s group and this is known to both B1 and B2.

Crypto puzzle 1: Hints

• Paper cups.
• Pieces of paper.
• Pencils.
• Remember: We just need to know if the same person is being complained about.

PUBLIC-KEY ENCRYPTION

• Motivation: Eliminate need for shared keys when keeping secrets.
• The new idea is to put some information in a public place.
• Here are the details:
• Associated with each user u is an encryption function E_u and a decryption function D_u.
• For all messages m, E_u(m) is unintelligible even knowing E_u. However, D_u(E_u(m)) = E_u(D_u(m)) = m.
• E_u is public.
• Given E_u and E_u(m), it is impossible to figure out D_u.