Subgroup decision techniques on cryptographic groups and pairings have been critical for numerous applications. Originally conceived in the composite-order setting, there is a large body of work showing how to instantiate subgroup decision techniques in the prime-order setting as well. In this work, we demonstrate the first barrier to this research program, by demonstrating an important setting where composite-order techniques cannot be replicated in the prime-order setting.

In particular, we focus on the case of q-type assumptions, which are ubiquitous in group- and pairing-based cryptography, but unfortunately are less desirable than the more well-understood static assumptions. Subgroup decision techniques have had great success in removing q-type assumptions, even allowing q-type assumptions to be generically based on static assumptions on composite-order groups. Our main result shows that the same likely does not hold in the prime order setting. Namely, we show that a large class of q-type assumptions, including the security definition of a number of cryptosystems, cannot be proven secure in a black box way from any static assumption.

@inproceedings{C:LuZha24,
    author =        {George Lu and Mark Zhandry},
    booktitle =     {CRYPTO~2024, Part~V},
    editor =        {Leonid Reyzin and Douglas Stebila},
    month =         aug,
    pages =         {46--74},
    publisher =     {Springer, Cham},
    series =        {{LNCS}},
    title =         {Limits on the Power of Prime-Order Groups: Separating
                     {Q}-Type from Static Assumptions},
    volume =        {14924},
    year =          {2024}
}

Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on telegraphing, or sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is telegraphable if and only if it is clonable. Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and quantum oracles relative to which these states are efficiently clonable but not efficiently telegraphable. Given that the opposite scenario is impossible (states that can be telegraphed can always trivially be cloned), this gives the most complete quantum oracle separation possible between these two important no-go properties. We additionally study the complexity class clonableQMA, a subset of QMA whose witnesses are efficiently clonable. As a consequence of our main result, we give a quantum oracle separation between clonableQMA and the class QCMA, whose witnesses are restricted to classical strings. We also propose a candidate oracle-free promise problem separating these classes. We finally demonstrate an application of clonable-but-not-telegraphable states to cryptography, by showing how such states can be used to protect against key exfiltration.

@InProceedings{ITCS:NehZha24,
    author =    {Nehoran, Barak and Zhandry, Mark},
    title =     {A Computational Separation Between Quantum 
                 No-Cloning and No-Telegraphing},
    booktitle = {15th Innovations in Theoretical Computer 
                 Science Conference (ITCS 2024)},
    pages =     {82:1--82:23},
    series =    {Leibniz International Proceedings in Informatics (LIPIcs)},
    year =      {2024},
    volume =    {287},
    editor =    {Guruswami, Venkatesan},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    address =   {Dagstuhl, Germany}
}

The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications.

In this work, we ask: which heuristics are closer to reality? Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly "milder" heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.

@inproceedings{AC:ZhaZha23,
    author =        {Cong Zhang and Mark Zhandry},
    booktitle =     {ASIACRYPT~2023, Part~VI},
    editor =        {Jian Guo and Ron Steinfeld},
    month =         dec,
    pages =         {390--419},
    publisher =     {Springer, Singapore},
    series =        {{LNCS}},
    title =         {The Relationship Between Idealized Models Under 
                     Computationally Bounded Adversaries},
    volume =        {14443},
    year =          {2023}
}

We give the first black box lower bound for isogeny-based protocols that can be described as group actions. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be Ω(λ²/\logλ). Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

@inproceedings{EC:BonGuaZha23,
    author =        {Dan Boneh and Jiaxin Guan and Mark Zhandry},
    booktitle =     {EUROCRYPT~2023, Part~V},
    editor =        {Carmit Hazay and Martijn Stam},
    month =         apr,
    pages =         {507--531},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {A Lower Bound on the Length of Signatures Based on
                     Group Actions and Generic Isogenies},
    volume =        {14008},
    year =          {2023},
}

Generic groups are an important tool for analyzing the feasibility and in-feasibility of group-based cryptosystems. There are two distinct wide-spread versions of generic groups, Shoup's and Maurer's, the main difference being whether or not group elements are given explicit labels. The two models are often treated as equivalent. In this work, however, we demonstrate that the models are in fact quite different, and care is needed when stating generic group results:

• We show that numerous textbook constructions are not captured by Maurer, but are captured by Shoup. In the other direction, any construction captured by Maurer is captured by Shoup.

• For constructions that exist in both models, we show that security is equivalent for "single stage" games, but Shoup security is strictly stronger than Maurer security for some "multi-stage" games.

• The existing generic group un-instantiability results do not apply to Maurer. We fill this gap with a new un-instantiability result.

• We explain how the known black box separations between generic groups and identity-based encryption do not fully apply to Shoup, and resolve this by providing such a separation.

• We give a new un-instantiability result for the algebraic group model.

@inproceedings{C:Zhandry22b,
    author =        {Mark Zhandry},
    booktitle =     {CRYPTO~2022, Part~III},
    editor =        {Yevgeniy Dodis and Thomas Shrimpton},
    month =         aug,
    pages =         {66--96},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {To Label, or Not To Label (in Generic Groups)},
    volume =        {13509},
    year =          {2022}
}

An Order-Revealing Encryption (ORE) scheme gives a public procedure by which two ciphertext can be compared to reveal the order of their underlying plaintexts. The ideal security notion for ORE is that only the order is revealed — anything else, such as the distance between plaintexts, is hidden. The only known constructions of ORE achieving such ideal security are based on cryptographic multilinear maps, and are currently too impractical for real-world applications. In this work, we give evidence that building ORE from weaker tools may be hard. Indeed, we show black-box separations between ORE and most symmetric-key primitives, as well as public key encryption and anything else implied by generic groups in a black-box way. Thus, any construction of ORE must either (1) achieve weaker notions of security, (2) be based on more complicated cryptographic tools, or (3) require non-black-box techniques. This suggests that any ORE achieving ideal security will likely be somewhat inefficient.

Central to our proof is an proof of impossibility for something we call information theoretic ORE, which has connections to tournament graphs and a theorem by Erdős. This impossibility proof will be useful for proving other black box separations for ORE.

@inproceedings{TCC:ZhaZha18,
    author =        {Mark Zhandry and Cong Zhang},
    booktitle =     {TCC~2018, Part~II},
    editor =        {Amos Beimel and Stefan Dziembowski},
    month =         nov,
    pages =         {129--158},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Impossibility of Order-Revealing Encryption in
                     Idealized Models},
    volume =        {11240},
    year =          {2018}
}