{"id":{"repo_id":"nus","oai_identifier":"oai:scholarbank.nus.edu.sg:10635/204942"},"canonical_url":"https://search.dev.ndltd.org/etd/nus/oai:scholarbank.nus.edu.sg:10635/204942","repository":{"repo_id":"nus","name":"National University of Singapore","base_url":"https://scholarbank.nus.edu.sg/oai/request"},"display":{"title":"DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY","abstract":"In this thesis, we study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a composition theorem for randomized query complexity. Next we consider composition theorems where a query function is composed with a communication function, which are often called query-to-communication 'lifting' theorems. We show results lifting various adversary bounds, which are a lower bound technique in query complexity, to randomized and quantum communication complexity. We study direct product theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel repetition theorem for one-round non-local games whose input distributions are anchored. Third, we prove a parallel repetition theorem for a class of two-round non-local games also via anchoring. The final result of the first part of the thesis is a direct product theorem for interactive quantum communication complexity in terms of the efficiency or quantum partition bound, which is a lower bound on quantum communication. In the second part of the thesis, our first result is exhibiting a device-independent protocol for a cryptographic task known as encryption with certified deletion, whose security we prove using the parallel repetition theorem for two-round games proved in the first part. Finally, using the interactive direct product result from the first part, we prove that it is possible to do device-independent quantum key distribution even with devices that leak information.","abstract_html":"In this thesis, we study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a composition theorem for randomized query complexity. Next we consider composition theorems where a query function is composed with a communication function, which are often called query-to-communication 'lifting' theorems. We show results lifting various adversary bounds, which are a lower bound technique in query complexity, to randomized and quantum communication complexity. We study direct product theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel repetition theorem for one-round non-local games whose input distributions are anchored. Third, we prove a parallel repetition theorem for a class of two-round non-local games also via anchoring. The final result of the first part of the thesis is a direct product theorem for interactive quantum communication complexity in terms of the efficiency or quantum partition bound, which is a lower bound on quantum communication. In the second part of the thesis, our first result is exhibiting a device-independent protocol for a cryptographic task known as encryption with certified deletion, whose security we prove using the parallel repetition theorem for two-round games proved in the first part. Finally, using the interactive direct product result from the first part, we prove that it is possible to do device-independent quantum key distribution even with devices that leak information.","abstract_has_math":false,"creators":["SRIJITA KUNDU"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-07-21","date_published":"2021-07-21","updated_at":"2026-07-24T03:31:26Z","subjects":["Query complexity, communication complexity, device-independent cryptography, direct product, composition"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["SRIJITA KUNDU"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2021-07-21"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://scholarbank.nus.edu.sg/handle/10635/204942"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Query complexity, communication complexity, device-independent cryptography, direct product, composition"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://scholarbank.nus.edu.sg/bitstreams/8fe5e4c3-eec8-46fa-9c72-0ebd14dfe207/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a composition theorem for randomized query complexity. Next we consider composition theorems where a query function is composed with a communication function, which are often called query-to-communication 'lifting' theorems. We show results lifting various adversary bounds, which are a lower bound technique in query complexity, to randomized and quantum communication complexity. We study direct product theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel repetition theorem for one-round non-local games whose input distributions are anchored. Third, we prove a parallel repetition theorem for a class of two-round non-local games also via anchoring. The final result of the first part of the thesis is a direct product theorem for interactive quantum communication complexity in terms of the efficiency or quantum partition bound, which is a lower bound on quantum communication. In the second part of the thesis, our first result is exhibiting a device-independent protocol for a cryptographic task known as encryption with certified deletion, whose security we prove using the parallel repetition theorem for two-round games proved in the first part. Finally, using the interactive direct product result from the first part, we prove that it is possible to do device-independent quantum key distribution even with devices that leak information."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["e21e4e93d65a94436e3d8d16cdc2a3b1","83b5f37c479c9ca2dab8afbc1ae94251"]},{"key":"dc:title","label":"Title","values":["DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY"]}]}],"canonical_facts":{"dc:creator":["SRIJITA KUNDU"],"dc:date.issued":["2021-07-21"],"dc:description.abstract":["In this thesis, we study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a composition theorem for randomized query complexity. Next we consider composition theorems where a query function is composed with a communication function, which are often called query-to-communication 'lifting' theorems. We show results lifting various adversary bounds, which are a lower bound technique in query complexity, to randomized and quantum communication complexity. We study direct product theorems in communication, and closely related parallel repetition theorems in communication, using a technique called anchoring. First, we prove a strong direct product theorem for one-way quantum communication complexity using this technique. Second, we give a simplified proof of a parallel repetition theorem for one-round non-local games whose input distributions are anchored. Third, we prove a parallel repetition theorem for a class of two-round non-local games also via anchoring. The final result of the first part of the thesis is a direct product theorem for interactive quantum communication complexity in terms of the efficiency or quantum partition bound, which is a lower bound on quantum communication. In the second part of the thesis, our first result is exhibiting a device-independent protocol for a cryptographic task known as encryption with certified deletion, whose security we prove using the parallel repetition theorem for two-round games proved in the first part. Finally, using the interactive direct product result from the first part, we prove that it is possible to do device-independent quantum key distribution even with devices that leak information."],"dc:format.checksum.md5":["e21e4e93d65a94436e3d8d16cdc2a3b1","83b5f37c479c9ca2dab8afbc1ae94251"],"dc:identifier.uri":["https://scholarbank.nus.edu.sg/bitstreams/8fe5e4c3-eec8-46fa-9c72-0ebd14dfe207/download"],"dc:relation.isreferencedby":["https://scholarbank.nus.edu.sg/handle/10635/204942"],"dc:subject":["Query complexity, communication complexity, device-independent cryptography, direct product, composition"],"dc:title":["DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY"],"dc:type":["Thesis"]},"updated_at":"2026-07-24T03:31:26Z"}