International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alper Cakan

Publications

Year
Venue
Title
2024
TCC
Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World
Can an adversary hack into our computer and steal sensitive data such as cryptographic keys? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect hacking attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world? We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the leakage-resilient cryptography literature. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against. As a notable example, the most well-studied leakage model is that of bounded leakage, where it is assumed that an adversary learns at most l bits of leakage on secret components, for some leakage bound l. Although this leakage bound is necessary, many real-world side-channel attacks cannot be captured by bounded leakage. In this work, we design cryptographic schemes that provide guarantees against arbitrary side-channel attacks: • Using techniques from unclonable quantum cryptography, we design several basic leakage- resilient primitives, such as public- and private-key encryption, (weak) pseudorandom func- tions, digital signatures and quantum money schemes which remain secure under (polyno- mially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classi- cal information. Notably, the leakage-resilience of our schemes holds even in the stronger “LOCC leakage” model where the adversary can obtain adaptive leakage for (polynomially) unbounded number of rounds. • What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack? What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? We initiate the study of intrusion- detection in the quantum setting, where one would like to detect if security has been compromised even in the face of an arbitrary intruder attack which can leak and tamper with classical as well as quantum data. We design cryptographic schemes supporting intrusion detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion
2024
TCC
Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography
Alper Cakan Vipul Goyal
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program or functionality in a quantum state such that a user in possession of k copies cannot create k + 1 copies, for any k. Introduced by Aaronson (CCC’09) over a decade ago, copy protection has proven to be notoriously hard to achieve. Previous work has been able to achieve copy-protection for various functionalities only in restricted models: (i) in the bounded collusion setting where k → k + 1 security is achieved for a-priori fixed collusion bound k (in the plain model with the same computational assumptions as ours, by Liu, Liu, Qian, Zhandry [TCC’22]), or, (ii) only k → 2k security is achieved (relative to a structured quantum oracle, by Aaronson [CCC’09]). In this work, we give the first unbounded collusion-resistant (i.e. multiple-copy secure) copy- protection schemes, answering the long-standing open question of constructing such schemes, raised by multiple previous works starting with Aaronson (CCC’09). More specifically, we obtain the following results. - We construct (i) public-keyencryption,(ii) public-keyfunctionalencryption,(iii) signature and (iv) pseudorandom function schemes whose keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure iO and LWE. - We show that any unlearnable functionality can be copy-protected against unbounded collusions, relative to a classical oracle. - As a corollary of our results, we rule out the existence of hyperefficient quantum shadow tomography and hence answer an open question by Aaronson (STOC’18). We obtain our results through a novel technique which uses identity-based encryption to construct multiple copy secure copy-protection schemes from 1-copy → 2-copy secure schemes. We believe our technique is of independent interest. Along the way, we also obtain the following results. - We define and prove the security of new collusion-resistant monogamy-of-entanglement games for coset states. - We construct a classical puncturable functional encryption scheme whose master secret key can be punctured at all functions f such that f(m0) ̸= f(m1). This might also be of independent interest.