Security and Cryptography
Symmetric and Public Key Cryptography
Due: 2 November 1998
Can you think of a situation where it makes sense to have a combination of the Bell-LaPadula and Biba mandatory integrity models?
Look at several Visa and Mastercard numbers and infer a simple algorithm for checking whether a credit card number could be valid.
Give a "black box" description (not tied to any specific cryptographic representation) of Chaumís electronic token blinding operation. Use it to give a black box description of Chaumís digital cash protocol.
In electronic commerce, one might want to make a purchase anonymously. One may also want to complain if one receives poor service (or the wrong goods). Can you think of some ways to reconcile these properties? What additional information is needed from the purchase protocol to accomplish this?
In Section 6 of Brandís paper he extends the basic cash system to restrain double-spending.
In the iKP paper the authors say that they require encryption to provide not only confidentiality, but also integrity. Decryption of a ciphertext results either in a message or in a flag indicating non-validity. Correct decryption convinces the receiver that the sender knows the plaintext that was encrypted.
Definition 1: We say that an encryption scheme is plaintext-aware if it is impossible to produce a valid ciphertext without knowing the corresponding plaintext.
Definition 2: We say that an encryption scheme E is non-malleable if given a ciphertext c = E(m) it is impossible to produce a valid ciphertext cí of a related message mí.
Hereís a protocol that allows a Customer to withdraw a coin of $1 from the Bank. Let (n, 3) be the RSA public key of the Bank.
Notice that the Customer has a probability of 1/100 to cheat successfully.
Suppose now that the protocol is not atomic. That is, the communication line may go down at the end of each step between the Customer and the Bank. What protocol should be followed for each step if the line goes down at the end of that step in order to prevent abuse or fraud by either party?
8. Transferable Electronic Cash (15)
Real-life cash has two main properties:
The electronic cash proposals we saw in class are all "non-transferable," that is the customer gets a coin from the bank, spends it, and the vendor must return the coin to the bank in order to get credit. As such they really behave as anonymous non-transferable checks. In this problem we are going to modify such proposals in order to achieve transferability.
Consider the following abstraction of a protocol similar to what we saw in class. We have three agents: the Bank, the Customer, and the Merchant.
The Bank has a pair of keys (S, P). A signature with S is a coin worth a fixed amount (say $1). It is possible to make blind signatures, meaning the Customer gets a signature S(m) on a message m, but the Bank gets no information about m.
The challenge-response protocol is needed in order to detect double-spending. Indeed the system is constructed in such a way that if the Customer answers two different challenges on the same coin (meaning heís trying to spend the coin twice) his identity will be revealed to the Bank when the two coins return to the bank. This is why the whole history of the payment protocol must be presented to the Bank when the Merchant deposits the coin.
In order to make the whole scheme transferable we give the bank a different pair of keys (S, P). It is still possible to make blind signatures with S. However messages signed with S have no value. We will call them pseudo-coins. When people open an account with the Bank, they get a lot of these anonymous pseudo-coins by running the withdrawal protocol with S as the signature key.
Suppose now the Merchant received a paid coin m, S(m), c, r and instead of depositing it wants to use it to buy something from OtherMerchant. What she could do is the following:
Notice however that Merchant can still double-spend the coin m, S(m), c, r if she uses two different pseudo-coins to transfer it to two different people. Indeed since she will never answer two different challenges on the same pseudo-coin, her identity will never be revealed. The problem is that there is no link between the real coin and the pseudo-coin used during the transfer protocol. If we could force the Merchant to use only one pseudo-coin for each real coin she wants to transfer then the problem would be solved.
Show how to achieve the above goal. You will need to modify both the payment and the transfer protocols.