Conference rusure::math

Did you ever do that thing with your fingers to determine who goes first?

One person (chosen arbitrarily) announces even or odd; then both of them reveal
a number of fingers concurrently; if the sum is even or odd as the announcer
proclaimed then they are first otherwise the other person is.

Can this or something like it be implemented with typical computers on a typical
network?  The problem seems to be how to share your number with the other entity
without risking your position.  If they get it first then they could quickly
change their own number to their advantage.

My thought is to transmit your number to your opponent encrypted.  Only after
receiving their number, also encrypted, would you send the key to decrypt
your's.  The thing I'm wondering is, is it possible for your opponent to send a
different key to decrypt their number to their advantage?  Could a digital
signature secure against this?

Once we get this function, can it be used to build up to the function described
in .0?

    One way to generate a trusted random bit is to select two large random
    primes, one of them congruent to 1 modulo 4 and the other congruent to
    3.  Send their product to the other party.  The other party randomly
    states "0" or "1".  Xor that bit with 0 if the lesser factor is
    congruent to 1 and 1 if the lesser factor is congruent to 3.
    
    A way to generate larger trusted random numbers is to select a random
    number modulo N, where N is any desired integer, and encrypt it with
    PGP.  The encrypted message is transmitted to the other party.  The
    other party selects another random number modulo N and transmits it. 
    Then the decryption is revealed (and checked).  The sum of the two
    numbers, modulo N, is the final random number.  (Actually, PGP adds
    some random bits that make checking the encryption problematic, but the
    idea is sound.)
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    Suppose A and B have encryption and decryption keys and encryption and
    decryption with these keys are commutative.  (I know this is possible;
    Chaum's Digicash uses it.  In RSA, the encryption of m with key e is
    m^e % n, so the encryption with keys e and f is (m^e)^f % n = m^(e*f) %
    n = m^(f*e) % n = (m^f)^e % n.  That requires a common n for A and B,
    which is a problem I'm not sure how to deal with.)
    
    A shuffles a set of playing cards, encrypts each card, and sends the
    encrypted set to B.  B shuffles the set, encrypts each element, and
    shares the result with A.
    
    Now there is a pool of "face-down" cards that the two players may draw
    from.  Whenever A selects an element, B decrypts it and gives the
    result to A, who decrypts it privately to get the card.  Conversely, B
    selects an element, A decrypts it and gives the result to B, who
    decrypts it privately to get the card.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

    By chance, I saw a mention of blinding in another discussion.  Here is
    how A can have B sign or encrypt a message using B's key while B does
    not know what is being signed or encrypted and A does not learn B's
    private key.
    
    Normally, B decrypts an encrypted text t by computing m = t^d % n, to
    get the message m.  The encryption is t = m^e % n.  Let A make up a
    random number b as the blinding factor.  Then A takes t and computes
    t*b^e % n.  A gives this to B, who decrypts it, yielding:
    
    	(t*b^e)^d % n
    		= (t^d * (b^e)^d)) % n
    		= (t^d * b^(e*d)) % n
    		= (t^d * b) % n.
    
    The last step holds since anything (relatively prime to n) raised to
    the power of e*d is congruent to itself modulo n.
    
    Now A has b*t^d % n and can compute t^d % n by multiplying by the
    inverse of b modulo n.
    
    Now we can see how a shuffle works without revealing anybody's keys or
    requiring a shared modulus.  A encrypts each card of a deck, shuffles
    the results, and gives them to B.  B encrypts them and shuffles again. 
    Whenever a player wants a card, they pick one of the remaining
    encrypted texts, which is necessarily a random draw.
    
    If B is drawing, B decrypts it with B's key, then blinds it and
    presents it to A for decryption.  B unblinds the result and has a card.
    
    If A is drawing, A blinds it, presents it to B for decryption, unblinds
    the result, and decrypts it with A's key.
    
    Another issue is how one player proves to another that they do possess
    the card they now wish to play openly.  Observe that the plaintext of
    any card, when encrypted with A's key and then B's key, yields the
    number that was drawn from the pool.  Of course, that itself is a
    problem, since either player can figure out what the cards in the pool
    are, since encryption keys are public!
    
    But this is solved with random padding.  As part of each encryption
    process, random bits are appended to the plaintext.  The results cannot
    be figured out by encrypting cards, since each player does not know the
    other's random padding.  But once the plaintext is recovered, it is
    clearly the playing card with some extra bits, and the encryptions can
    be verified.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

Reminds me of the following nonsense:

	Always shuffle a new deck of cards extra times before dealing,
	since new decks are packaged in order.  However, take care not
	to OVER shuffle, as the cards will start coming back into order.

/Eric