Name: 名称：sIDIt will be highly suggested to use LaTeX or MS Word to type in your answer; if you have 强烈建议使用 LaTeX 或 MS Word 输入您的答案；如果您有to scan your handwriting, please make sure your handwriting is clearly recognizable. 请确保您的手写字迹清晰可辨，以便扫描。
Q1. (5 points) Give one concrete example that follows the "security via obscurity" idea, and explain why it may fail to work. Q1. (5 分) 给出一个具体的例子，说明“通过模糊性实现安全”的理念，并解释为什么它可能会失败。
Q2. (10 points) PKI provides a digital certification system. Each certification basically contains the information of valid - period algorithm metadata together with a signature of CA. (1) Could we just use an MAC to generate ? please briefly explain. (2) Root CA needs to be very careful about his secret key which is the root trust of the whole PKI system. He may choose to be offline, and introducing a bunch of intermediate CAs to interact with the users who are requesting certificates. At the system setup phase, he issues certificates for each of the and let those intermediate CAs to generate certificates. Essentially any certificate generated by any of the is considered valid. Another solution is for the CA to split his root secret into pieces and stored in different machines, and leverage a threshold certification generation procedure that only when machines respond with a valid certificate share, user can combine and obtain a valid certificate. Which of the two solutions is more vulnerable (or requiring more trust)? please briefly explain. Q2. (10 分) PKI 提供了一个数字认证系统。每个认证基本上包含 有效期 算法 元数据以及 CA 的签名 。(1) 我们能否仅使用 MAC 来生成 ？请简要解释。(2) 根 CA 需要非常小心他的秘密密钥，因为这是整个 PKI 系统的根信任。他可以选择离线，并引入一批中间 CA 与请求证书的用户进行交互。在系统设置阶段，他为每个 颁发证书，并让这些中间 CA 生成证书。实际上，任何由 中的任何一个生成的证书都被视为有效。另一种解决方案是 CA 将他的根秘密分割成 份，并存储在 台不同的机器上，并利用一个阈值认证生成程序，只有当 台机器响应有效的证书共享时，用户才能组合并获得有效证书。哪种解决方案更脆弱（或需要更多信任）？请简要解释。
Q3. (10 points) Self-referential encryption. Normally, encryption is used only on messages that are independent of the secret key, thus security guarantee implicitly assumes this. However, situations may arise due to careless key management, for example a backup system may store the backup encryption key on disk and then encrypt the entire disk, including the key, and backup the result. Another example is the BitLocker disk encryption utility (used in WindowsVista) where the disk encryption key can end up on disk and be encrypted along with the disk contents. In those cases, adversary obtains normal ciphertext that encrypting some content, as well as a special token (using the same key to encrypt the key itself as a message). It might be possible to specially design encryption and strengthen the security to handle this, but conventional encryptions may not be safe to be directly used this way. Q3.（10 分）自引用加密。通常，加密仅用于与秘密密钥无关的消息，因此安全保证隐含地假设这一点。然而，由于不当的密钥管理，可能会出现一些情况，例如备份系统可能会将备份加密密钥存储在磁盘上，然后加密整个磁盘，包括密钥，并备份结果。另一个例子是 BitLocker 磁盘加密工具（用于 Windows Vista），其中磁盘加密密钥可能会存储在磁盘上，并与磁盘内容一起加密。在这些情况下，对手获得正常的密文 ，该密文加密了一些内容，以及一个特殊的令牌 （使用相同的密钥加密密钥本身作为消息）。可能有可能特别设计加密并增强安全性以处理这种情况，但传统加密可能不安全，不能直接以这种方式使用。
Design an IND-CPA secure encryption that can be easily broken when used this way, and briefly analyze why it is IND-CPA secure when is not present, and why it is broken when is also given. (Hint: you do not need to worry about any mathematical details, just use an IND-CPA encryption as a blackbox and modify a bit). 设计一个 IND-CPA 安全的加密方案，当以这种方式使用时可以很容易被破解，并简要分析为什么在没有 的情况下它是 IND-CPA 安全的，以及为什么在给出 时它被破解。（提示：您不需要担心任何数学细节，只需将 IND-CPA 加密视为黑箱并稍作修改）。
Q4. (10 points) Searchable encryption and IND-CPA security. As you have seen in the class, the ciphertext of IND-CPA security of public key encryption does not leak any single bit of information. Now consider encrypted database entries , where for a message . The database manager still wants to support basic database operations such as search, sort and more. Suppose we design a special order preserving encryption which satisfies that , iff . This naturally supports the sort operation on ciphertexts. Could you find an issue with such kind of order preserving encryption that everyone can easily crack the plaintext: i.e., given any ciphertext for some unknown message (assuming the size of message is known, with 100-bits), anyone can easily figure out the value of . Q4. (10 分) 可搜索加密和 IND-CPA 安全性。正如你在课堂上看到的，公钥加密的 IND-CPA 安全性的密文不会泄露任何单个比特的信息。现在考虑加密数据库条目 ，其中 表示消息 。数据库管理员仍然希望支持基本的数据库操作，如搜索、排序等。假设我们设计了一种特殊的保持顺序的加密方式，满足 ，当且仅当 。这自然支持对密文的排序操作。你能找到这种保持顺序的加密方式的一个问题吗？即，给定任何密文 对应某个未知消息 （假设消息的大小已知，为 100 位），任何人都可以轻松找出 的值。
Q5. (10 points) Suppose before the first lecture, you all received an email from a non-USYD email address claiming "please use the following public key for future communication with me - the lecturer of COMP5619". Since we never met, you guys naturally felt suspicious about the email. In order to convince you the public key is the correct one for me, what should I further provide, assuming you all have access to the website of USYD, which contains USYD VC's public key . Q5.（10 分）假设在第一次讲座之前，你们都收到了来自非悉尼大学（USYD）邮箱地址的电子邮件，声称“请使用以下公钥 与我进行未来的沟通——COMP5619 的讲师”。由于我们从未见面，你们自然对这封邮件感到怀疑。为了让你们相信这个公钥是我正确的公钥，我还应该提供什么，假设你们都可以访问悉尼大学的网站，该网站包含悉尼大学副校长的公钥 。
Q6. (10 points) USYD library can be accessed only by students or staff during after-work hours, that means only ones who have access to USYD card can pass the verification in the entrance. It is clear that each of our card contains some pre-installed key that can be used during the identification procedure. Could you give a complete solution for designing the protocol for the device to control access, assuming only students/staff can have a valid card? (Hint: describe how each key in the card is generated, and managed, ideally the university only wants to keep one master key. And describe the protocol when you touch your card could be a simple challenge-response one, with the use of a proper cryptographic tool). Q6. (10 分) USYD 图书馆在下班时间仅可由学生或工作人员访问，这意味着只有持有 USYD 卡的人才能通过入口的验证。显然，我们每张卡都包含一些预先安装的密钥，可用于身份识别程序。您能否提供一个完整的解决方案，设计一个控制访问的协议，假设只有学生/工作人员可以拥有有效的卡？（提示：描述卡中每个密钥是如何生成和管理的，理想情况下，大学只想保留一个主密钥。并描述当您触碰卡时的协议，这可以是一个简单的挑战-响应协议，使用适当的加密工具）。
Q7. (10 points) (1) Diffie-Hellman is a wonderful invention for key exchange. Unfortunately, with the possibility of quantum computer, Diffie-Hellman assumption will be solved by a quantum computer, so that the key exchange wont be secure anymore against a quantum computer, so does TLS. There are a bunch of other encryption experts that envisioned this, and designed a new public key encryption scheme Enc* that can be secure even against a quantum computer. Could we still have a secure TLS even against the quantum computer? at least the key exchange component? If you believe so, please give a simple construction of the new key exchange protocol. Q7. (10 分) (1) Diffie-Hellman 是一个出色的密钥交换发明。不幸的是，随着量子计算机的出现，Diffie-Hellman 假设将被量子计算机破解，因此密钥交换将不再对量子计算机安全，TLS 也是如此。有许多其他加密专家预见到了这一点，并设计了一种新的公钥加密方案 Enc*，即使面对量子计算机也能保持安全。我们是否仍然可以在量子计算机面前保持安全的 TLS？至少在密钥交换组件方面？如果你相信这一点，请给出新的密钥交换协议的简单构造。
(2) Any key exchange protocol, requires the parties to use good randomness, which is expensive to collect. Pseudorandom generator is thus to expand a shorter random string to a longer string that is pseudorandom. Considering the following function PRG, given some randomness (as input) that is represented as two integers is defined as , where is a public matrix as below, (2) 任何密钥交换协议都要求各方使用良好的随机性，而收集这些随机性是昂贵的。因此，伪随机生成器的作用是将较短的随机字符串扩展为较长的伪随机字符串。考虑以下函数 PRG，给定一些随机性（作为输入），表示为两个整数 定义为 ，其中 是如下的公共矩阵，
so the output of is , which is longer than , and for each . Is this PRG a secure pseudorandom generator? if yes, please briefly explain; if not, please give an explicit "attack" on the pseudorandomness of the output. 所以 的输出是 ，这比 长，并且对于每个 。这个 PRG 是一个安全的伪随机生成器吗？如果是，请简要解释；如果不是，请对输出的伪随机性给出一个明确的“攻击”。
Q8. (15 points) During the TLS handshake phase, the client has to authenticate the server, and share a key with the server to build a secure channel for future use, e.g., transmitting password. There are multiple possibilities for an attacker to weaken the security without breaking the key exchange, including man-in-the-middle attack and the replay attack. Q8. (15 分) 在 TLS 握手阶段，客户端必须对服务器进行身份验证，并与服务器共享密钥，以建立一个安全通道以供将来使用，例如传输密码。攻击者有多种可能性削弱安全性而不破坏密钥交换，包括中间人攻击和重放攻击。
(1). Man-in-the-middle can happen as the attacker hijacts the communication channel between server and client, and then impersonates. For example, normally, Client sends , Server sends , then they both get as the shared key. But now, the attacker sends to the client, claiming is from the server, in this case, the client would consider as the shared key, which can be computed by the attacker. Briefly describe how TLS prevents such impersonation. 中间人攻击可以发生，因为攻击者劫持了服务器和客户端之间的通信通道，然后进行冒充。例如，通常情况下，客户端发送 ，服务器发送 ，然后他们都得到 作为共享密钥。但现在，攻击者向客户端发送 ，声称 是来自服务器，在这种情况下，客户端会将 视为共享密钥，而这个密钥可以由攻击者计算。简要描述 TLS 如何防止这种冒充。
(2). In a replay attack, the attacker simply stores one session of the information he eavesdropped from the server, and sends in the future session to obtain advantage. Since now the messages were indeed from the server, thus cannot be considered as impersonation, but still, the message is not sent for the right time. Briefly describe how TLS handles such an issue. 在重放攻击中，攻击者简单地存储他从服务器窃听到的一次会话信息，并在未来的会话中发送，以获取优势。由于这些消息确实来自服务器，因此不能被视为冒充，但消息并不是在正确的时间发送。简要描述 TLS 如何处理此类问题。
(3) TLS/SSL enables two parties to build a secure channel, but still there are all kinds of security problems that may leak the server data, name two examples of security attacks that TLS/SSL cannot take care of. TLS/SSL 使两个方能够建立安全通道，但仍然存在各种安全问题可能泄露服务器数据，举两个 TLS/SSL 无法处理的安全攻击的例子。
Q9.(10 points) Certificate management. CA in the PKI system is in charge of issuing and managing the certificates. While users may lose secret keys, or algorithms got upgraded, the certificate revocation is one indispensable functionality. As you have seen in the class, OCSP-Stapling is one technique that tries to reduce the workload of CA during the OCSP (online certificate status protocol, in which every verifier queries the CA whether a certain certificate is revoked or not). Using such a technique, CA outsources the work to an EFT server, which periodically downloads latest revocation list from OCSP server; while daily online query is handled directly by the EFT server. List two potential drawbacks of OCSP-Stapling, and briefly explain, why it is still not an ideal certificate revocation mechanism. Q9.(10 分) 证书管理。在 PKI 系统中，CA 负责颁发和管理证书。虽然用户可能会丢失私钥，或者算法得到升级，但证书撤销是一个不可或缺的功能。正如你在课堂上看到的，OCSP-Stapling 是一种试图减少 CA 在 OCSP（在线证书状态协议，验证者查询 CA 某个证书是否被撤销）期间工作负担的技术。使用这种技术，CA 将工作外包给 EFT 服务器，EFT 服务器定期从 OCSP 服务器下载最新的撤销列表；而每日在线查询则由 EFT 服务器直接处理。列出 OCSP-Stapling 的两个潜在缺点，并简要解释为什么它仍然不是理想的证书撤销机制。
Q10. (10 points) Secret sharing is one classical approach to disperse one secret into multiple devices/parties, so that only sufficient number of them come together, one can reconstruct the original secret. It is the base of the whole threshold cryptography. More specifically, a -secret sharing means the original secret is made to pieces, and with more than pieces, one can reconstruct , while if one is only holding pieces or fewer, he learns nothing about . (1) could you construct a secret sharing? (2) a threshold PKI basically asks multiple CAs to jointly issue each certificate, whole not enough CAs cannot issue a valid certificate. Could you briefly describe what a certificate looks like in a (2,2)-PKI system? Here (2,2)-PKI means we need to CAs to jointly issue a valid certificate, while any one of the CAs cannot. Also assume the content of the certificate includes ( , id, validperiod, algorithm, metadata) as a message to be endorsed by the two CAs jointly. Q10. (10 分) 秘密共享是一种经典的方法，将一个秘密分散到多个设备/参与方中，以便只有足够数量的它们聚集在一起，才能重建原始秘密。这是整个门限密码学的基础。更具体地说， -秘密共享意味着原始秘密 被分成 个部分，拥有超过 个部分的人可以重建 ，而如果一个人只持有 个部分或更少，他将对 一无所知。 (1) 你能构建一个 秘密共享吗？ (2) 一个门限 PKI 基本上要求多个 CA 共同签发每个证书，而不足够的 CA 无法签发有效证书。你能简要描述一下(2,2)-PKI 系统中的证书是什么样子的吗？这里的(2,2)-PKI 意味着我们需要两个 CA 共同签发有效证书，而任何一个 CA 都无法单独签发。同时假设证书的内容包括（ ，id，有效期，算法，元数据）作为由两个 CA 共同认可的消息。
Bonus question. Public key encryption (PKE) usually requires the ciphertext leak nothing about the plaintext, with standard secure notion called IND-CPA security. There is an advanced version of PKE, called anonymous PKE, in which not only IND-CPA secure, but also satisfying an anonymity, in 附加问题。公钥加密（PKE）通常要求密文不泄露任何关于明文的信息，具有一种称为 IND-CPA 安全性的标准安全概念。PKE 有一个高级版本，称为匿名 PKE，它不仅满足 IND-CPA 安全性，还满足匿名性。
the sense that the ciphertext leaks nothing about the public key. This type of anonymous PKE is needed in applications such as anonymous cryptocurrency like ZCash, which we will explain in a future lecture. Could you follow the IND-CPA definition methodology, to define anonymity here? (Hint: basically specify adversarial power, and adversarial goal). (5 points) 密文不泄露任何关于公钥的信息。这种匿名公钥加密（PKE）在诸如 ZCash 等匿名加密货币的应用中是必要的，我们将在未来的讲座中解释。你能按照 IND-CPA 定义的方法来定义这里的匿名性吗？（提示：基本上指定对手的能力和对手的目标）。(5 分)
More importantly, do you think this anonymity is just an extended property if IND-CPA security? (there are easy examples for concrete scheme, ElGamal is actually one such concrete example. ) or it is inherently different from IND-CPA security? if you support the former, could you construct an anonymous PKE, just using any IND-CPA secure PKE as a blackbox? (using the latter simply via API access without knowing details). If you support the latter, could you try to provide some proof (there is something called blackbox separation that you may check some paper)? (20 points) 更重要的是，你认为这种匿名性只是 IND-CPA 安全性的扩展属性吗？（对于具体方案有简单的例子，ElGamal 实际上就是这样一个具体例子。）还是它与 IND-CPA 安全性本质上不同？如果你支持前者，你能否仅使用任何 IND-CPA 安全的公钥加密（PKE）作为黑箱构建一个匿名 PKE？（通过 API 访问简单使用后者，而不需要了解细节）。如果你支持后者，你能否尝试提供一些证明（有一种叫做黑箱分离的东西，你可以查阅一些论文）？（20 分）