More Like this

1. The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-rewinding Proofs for Schnorr Identification and Signatures.

   Bellare, Mihir; Dai, Wei (December 2020, Progress in Cryptology - INDOCRYPT 2020 - 21st International Conference on Cryptology in India, Proceedings. Lecture Notes in Computer Science, Springer)

   Bhargavan, Karthikeyan; Oswald, Elisabeth; Prabhakaran, Manoj (Ed.)

   We introduce the Multi-Base Discrete Logarithm (MBDL) problem. We use this to give reductions, for Schnorr and Okamoto identification and signatures, that are non-rewinding and, by avoiding the notorious square-root loss, tighter than the classical ones from the Discrete Logarithm (DL) problem. This fills a well-known theoretical and practical gap regarding the security of these schemes. We show that not only is the MBDL problem hard in the generic group model, but with a bound that matches that for DL, so that our new reductions justify the security of these primitives for group sizes in actual use. 

   more » « less
2. Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key Exchange

   https://doi.org/10.1007/978-981-96-0888-1_11  

   Bellare, Mihir; Riepel, Doreen; Tessaro, Stefano; Zhang, Yizhao (December 2024, Springer Nature Singapore)

   In the multi-user with corruptions (muc) setting there are n users, and the goal is to prove that, even in the face of an adversary that adaptively corrupts users to expose their keys, un-corrupted users retain security. This can be considered for many primitives including signatures and encryption. Proofs of muc security, while possible, generally suffer a factor n loss in tightness, which can be large. This paper gives new proofs where this factor is reduced to the number c of corruptions, which in practice is much smaller than n. We refer to this as corruption-parametrized muc (cp-muc) security. We give a general result showing it for a class of games that we call local. We apply this to get cp-muc security for signature schemes (including ones in standards and in TLS 1.3) and some forms of public-key and symmetric encryption. Then we give dedicated cp-muc security proofs for some important schemes whose underlying games are not local, including the Hashed ElGamal and Fujisaki-Okamoto KEMs and authenticated key exchange. Finally, we give negative results to show optimality of our bounds. 

   more » « less
3. 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
4. Public-Key Encryption Resistant to Parameter Subversion and Its Realization from Efficiently-Embeddable Groups

   Auerbach, Benedikt; Bellare, Mihir; Kiltz, Eike (March 2018, Public-Key Cryptography – PKC 2018. PKC 2018. Lecture Notes in Computer Science, vol 10769. Springer, Cham)

   We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves. 

   more » « less
5. Time-Varying Metamaterial-Enabled Directional Modulation Schemes for Physical Layer Security in Wireless Communication Links

   https://doi.org/10.1145/3513088  

   Nooraiepour, Alireza; Vosoughitabar, Shaghayegh; Wu, Chung-Tse Michael; Bajwa, Waheed U.; Mandayam, Narayan B. (January 2022, ACM Journal on Emerging Technologies in Computing Systems)

   Novel transmission schemes, enabled by recent advances in the fields of metamaterial (MTM), leaky-wave antenna (LWA) and directional modulation, are proposed for enhancing the physical layer (PHY) security. MTM-LWAs, which offer compact, integrated, and cost-effective alternatives to the classic phased-array architectures, are particularly of interest for emerging wireless communication systems including Internet-of-Things (IoT). The proposed secure schemes are devised to accomplish the functionalities of directional modulation (DM) transmitters for orthogonal frequency-division multiplexing (OFDM) and non-contiguous (NC) OFDM transmissions, while enjoying the implementation benefits of MTM-LWAs. Specifically, transmitter architectures based on the idea of time-modulated MTM-LWA have been put forth as a promising solution for PHY security for the first time. The PHY security for the proposed schemes are investigated from the point of view of both passive and active attacks where an adversary aims to decode secret information and feed spurious data to the legitimate receiver, respectively. Numerical simulations reveal that even when the adversary employs sophisticated state-of-the-art deep learning based attacks, the proposed transmission schemes are resistant to these attacks and reliably guarantee system security. 

   more » « less