A Computational Separation Between Quantum Nocloning and Notelegraphing






Two of the fundamental nogo theorems of quantum information are the nocloning
theorem (that it is impossible to make copies of general quantum states) and the
noteleportation theorem (the prohibition on telegraphing, or sending quantum states
over classical channels without preshared 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 nogo 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 oraclefree promise
problem separating these classes. We finally demonstrate an application of
clonablebutnottelegraphable states to cryptography, by showing how such states can
be used to protect against key exfiltration.
@inproceedings{ITCS:NehZha24,
author = {Barak Nehoran and Mark Zhandry},
booktitle = {ITCS 2024},
title = {A Computational Separation Between Quantum Nocloning
and Notelegraphing},
note = {\url{https://arxiv.org/abs/2302.01858}},
year = {2024}
}

The Relationship Between Idealized Models Under Computationally Bounded Adversaries






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 realworld
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 = {Mark Zhandry and Cong Zhang},
booktitle = {ASIACRYPT 2023},
title = {The Relationship Between Idealized Models Under
Computationally Bounded Adversaries},
year = {2023}
}

A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies






We give the first black box lower bound for isogenybased 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 nonabelian) group action, the signature length
must be Ω(λ^{2}/\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 = {507531},
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},
}

To Label, or Not To Label (in Generic Groups)






Generic groups are an important tool for analyzing the feasibility and infeasibility
of groupbased cryptosystems. There are two distinct widespread 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 "multistage" games.
• The existing generic group uninstantiability results do not apply to Maurer.
We fill this gap with a new uninstantiability result.
• We explain how the known black box separations between generic groups and
identitybased encryption do not fully apply to Shoup, and resolve this by providing
such a separation.
• We give a new uninstantiability 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 = {6696},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {To Label, or Not To Label (in Generic Groups)},
volume = {13509},
year = {2022}
}

Impossibility of OrderRevealing Encryption in Idealized Models






An OrderRevealing 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 realworld applications. In this work, we give
evidence that building ORE from weaker tools may be hard. Indeed, we show blackbox
separations between ORE and most symmetrickey primitives, as well as public key
encryption and anything else implied by generic groups in a blackbox 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 nonblackbox 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 = {129158},
publisher = {Springer, Heidelberg},
series = {{LNCS}},
title = {Impossibility of OrderRevealing Encryption in
Idealized Models},
volume = {11240},
year = {2018}
}
