More Like this

1. On Quantum Chosen-Ciphertext Attacks and Learning with Errors

   Alagic, Gorjan ; Jeffery, Stacey ; Ozols, Maris ; Poremba, Alexander ( January 2019 , Theory of Quantum Computing, Communication, and Cryptography 2019)

   Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong "quantum access" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones. 

   more » « less
2. Bounded Collusion ABE for TMs from IBE

   https://doi.org/yes10.1007/978-3-030-92068-5_13  

   Goyal, Rishab ; Syed, Ridwan ; Waters, Brent ( December 2021 , Asiacrypt 2021)

   We give an attribute-based encryption system for Turing Machines that is provably secure assuming only the existence of identity-based encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search Diffie-Hellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine before declaring a challenge string that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an a-priori bounded number of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of non-committing encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this non-committing encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from single-key adaptive security to -key adaptive security. 

   more » « less
3. Efficient Schemes for Committing Authenticated Encryption

   https://doi.org/10.1007/978-3-031-07085-3_29  

   Bellare, Mihir ; Hoang, Viet Tung ( January 2022 , Annual International Conference on the Theory and Applications of Cryptology and Information Security (EUROCRYPT 2022))

   This paper provides efficient authenticated-encryption (AE) schemes in which a ciphertext is a commitment to the key. These are extended, at minimal additional cost, to schemes where the ciphertext is a commitment to all encryption inputs, meaning key, nonce, associated data and message. Our primary schemes are modifications of GCM (for basic, unique-nonce AE security) and AES-GCM-SIV (for misuse-resistant AE security) and add both forms of commitment without any increase in ciphertext size. We also give more generic, but somewhat more costly, solutions. 

   more » « less
4. Pseudorandom Isometries

   Ananth, Prabhanjan ; Gulati, Aditya ; Kaleoglu, Fatih ; Lin, Yao-Ting ( April 2024 , Springer Nature)

   We introduce a new notion called Q-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an n-qubit state to an (n+m)-qubit state in an isometric manner. In terms of security, we require that the output of a q-fold PRI on \rho, for \rho \in Q, for any polynomial q, should be computationally indistinguishable from the output of a q-fold Haar isometry on \rho. By fine-tuning Q, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of Q-secure pseudorandom isometries (PRI) for different interesting settings of Q. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments. 

   more » « less
5. Unidirectional Updatable Encryption and Proxy Re-encryption from DDH

   https://doi.org/10.1007/978-3-031-31371-4_13  

   Miao, Peihan ; Patranabis, Sikhar ; Watson, Gaven ( May 2023 , IACR International Conference on Public-Key Cryptography – PKC 2023)

   Boldyreva, Alexandra ; Kolesnikov, Vladimir (Ed.)

   Updatable Encryption (UE) and Proxy Re-encryption (PRE) allow re-encrypting a ciphertext from one key to another in the symmetric-key and public-key settings, respectively, without decryption. A longstanding open question has been the following: do unidirectional UE and PRE schemes (where ciphertext re-encryption is permitted in only one direction) necessarily require stronger/more structured assumptions as compared to their bidirectional counterparts? Known constructions of UE and PRE seem to exemplify this “gap” – while bidirectional schemes can be realized as relatively simple extensions of public-key encryption from standard assumptions such as DDH or LWE, unidirectional schemes typically rely on stronger assumptions such as FHE or indistinguishability obfuscation (iO), or highly structured cryptographic tools such as bilinear maps or lattice trapdoors. In this paper, we bridge this gap by showing the first feasibility results for realizing unidirectional UE and PRE from a new generic primitive that we call Key and Plaintext Homomorphic Encryption (KPHE) – a public-key encryption scheme that supports additive homomorphisms on its plaintext and key spaces simultaneously. We show that KPHE can be instantiated from DDH. This yields the first constructions of unidirectional UE and PRE from DDH. Our constructions achieve the strongest notions of post-compromise security in the standard model. Our UE schemes also achieve “backwards-leak directionality” of key updates (a notion we discuss is equivalent, from a security perspective, to that of unidirectionality with no-key updates). Our results establish (somewhat surprisingly) that unidirectional UE and PRE schemes satisfying such strong security notions do not, in fact, require stronger/more structured cryptographic assumptions as compared to bidirectional schemes. 

   more » « less