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.

1. Explain in English (not math!) what the role of O is. What roles do o₁ and o₂ play in the protocol?
2. Explain in English the payment (sub)protocol. What is the purpose of each step and what is the purpose of each part of each message?
3. How are double-spenders traced in case the tamper resistant card is broken?
4. Is anonymity preserved? Can the observer leak information? How or why not?

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.

1. Why is plaintext-awareness needed in iKP? Explain one possible problem if a regular (non-plaintext-aware) encryption function (such as RSA) is used.

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’.

2. Compare Definitions 1 and 2. Does one imply the other? Explain your reasoning.

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.

1. The Customer prepares 100 messages m₁, …, m₁₀₀ which are all $1 coins. The Customer blinds them; i.e., she chooses random r₁, …, r₁₀₀ and computes w_i = r_i³m_i. The Customer sends w₁, …, w₁₀₀ to the Bank.
2. The Bank chooses at random 99 of the blindings and asks the Customer to open them. That is, the Bank chooses i₁, …, i₉₉ and sends it to the Customer.
3. The Customer opens the required blindings by revealing r_i1, …, r_i99.
4. The Bank checks that the blindings are constructed correctly and then finally signs the unopened blinding. W.l.o.g. assume this to be the first one. So the Bank signs w₁ by sending to the Customer w₁^1/3 = r₁m₁^1/3.
5. The Customer divides this signature by r₁ and gets a signature on m₁ which is a valid coin.

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?

Real-life cash has two main properties:

• It is anonymous: When you use cash to buy something your identity is not revealed, whereas with credit cards your identity and spending habits are disclosed
• It is transferable: The vendor who receives cash from you can in turn use it to buy something else. He would not have this possibility if you had paid with a non-transferable check.

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.

1. The Customer chooses a message m.
2. The Bank blindly signs m and withdraws $1 from Customer’s account.
3. The Customer recovers S(m). The coin is the pair (m, S(m)).

1. The Customer gives the coin (m, S(m)) to the Merchant.
2. The Merchant verifies the Bank signature and sends a random challenge c to the Customer.
3. The Customer replies with an answer r.
4. The Merchant verifies that the answer is correct.

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.

1. The Merchant sends m, S(m), c, r to the Bank
2. The Bank verifies it and add $1 to the Merchant’s account.
3. The Bank searches its database to see if the coin was deposited already and if it was reconstructs the identity of the double-spender Customer.

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:

1. The Merchant sends m, S(m), c, r and a pseudo-coin m¢ , S(m¢ ) to OtherMerchant.
2. OtherMerchant verifies all signatures and the pair (c,r). Then sends a random challenge c¢ for the pseudo-coin.
3. Merchant replies with r¢
4. OtherMerchant checks the answer.

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.