Abstract The Fiat–Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent constructions use it for multi-round protocols. However, in general the soundness error of the Fiat–Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of $$(k_1,\dots ,k_\mu )$$ ( k 1 , ⋯ , k μ ) -special-sound $$\varSigma $$ Σ -protocols, which is a natural multi-round generalization of the well-known class of special-sound protocols, the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal. A natural next question is whether this positive result extends to the Fiat–Shamir transformation of so-called $$(\varGamma _1,\dots ,\varGamma _\mu )$$ ( Γ 1 , ⋯ , Γ μ ) -special-sound protocols. This notion was recently defined and analyzed in the interactive case; it captures a larger class of protocols, namely where the special-soundness property is characterized by a general access structure, rather than a threshold. We show in this work that this is indeed the case. Concretely, we show that the Fiat–Shamir transformation of any $$(\varGamma _1, \ldots , \varGamma _\mu )$$ ( Γ 1 , … , Γ μ ) -special-sound interactive proof is knowledge sound under the same condition on $$\varGamma _1,\dots ,\varGamma _\mu $$ Γ 1 , ⋯ , Γ μ for which the original interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random oracle queries and independent of the number of rounds. In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for $$(k_1,\dots ,k_\mu )$$ ( k 1 , ⋯ , k μ ) -special-sound protocols, which is based on an extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round analysis. Thus, new techniques are necessary to handle the above complications.

One-round secure computation is generally believed impossible due to the residual function attack : any honest-but-curious participant can replay the protocol in their head changing their input, and learn, in this way, a new output. Inputless functionalities are among the few that are immune to this problem. This paper studies one-round, multi-party computation protocols (MPC) that implement the most natural inputless functionality: one that generates a random sample from a fixed distribution. These are called distributed samplers . At Eurocrypt 2022, Abram, Scholl and Yakoubov showed how to build this primitive in the semi-honest model with dishonest majority. In this work, we give a lower bound for constructing distributed samplers with a malicious adversary in the standard model. More in detail, we show that for any construction in the stand-alone model with black-box simulation, even with a CRS and honest majority, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Our proof is based on an entropic argument, drawing a new connection between computationally secure MPC, information theory and learning theory.

Abstract The celebrated Fiat–Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $$\varSigma $$ Σ -protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $$(2\mu + 1)$$ (2μ+1) -move protocol is, in general, approximately $$Q^\mu $$ Qμ , whereQis the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $$\mu $$ μ -fold sequential repetition of $$\varSigma $$ Σ -protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for $$(k_1, \ldots , k_\mu )$$ (k1,…,kμ) -special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly inQ, instead of $$Q^\mu $$ Qμ . On the negative side, we show that fort-foldparallel repetitionsof typical $$(k_1, \ldots , k_\mu )$$ (k1,…,kμ) -special-sound protocols with $$t \ge \mu $$ t≥μ (and assuming for simplicity thattandQare integer multiples of $$\mu $$ μ ), there is an attack that results in a security loss of approximately $$\frac{1}{2} Q^\mu /\mu ^{\mu +t}$$ 12Qμ/μμ+t .

We prove a general relation between adaptive and non-adaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its “information content”. Since adaptivity is notoriously difficult to handle in the analysis of (quantum) cryptographic protocols, this gives us a very powerful tool: as long as we have enough control over the side information, it is sufficient to restrict ourselves to non-adaptive attacks. We demonstrate the usefulness of this methodology with two examples. The first is a quantum bit commitment scheme based on 1-bit cut-and-choose . Since bit commitment implies oblivious transfer (in the quantum setting), and oblivious transfer is universal for two-party computation, this implies the universality of 1-bit cut-and-choose, and thus solves the main open problem of [ 9 ]. The second example is a quantum bit commitment scheme proposed in 1993 by Brassard et al . It was originally suggested as an unconditionally secure scheme, back when this was thought to be possible. We partly restore the scheme by proving it secure in (a variant of) the bounded quantum storage model. In both examples, the fact that the adversary holds quantum side information obstructs a direct analysis of the scheme, and we circumvent it by analyzing a non-adaptive version, which can be done by means of known techniques, and applying our main result. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems $A$ and $B$ of a (possibly) unknown quantum state $|\psi\rangle \in {\cal H}_A \otimes {\cal H}_B$. Their goal is to calculate and share a new state $|\varphi\rangle = U|\psi\rangle$, where $U$ is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state $|\varphi'\rangle$ that coincides with $|\varphi\rangle = U|\psi\rangle$ up to local operations on $A$ and on $B$, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

The Rényi entropy of general order unifies the well-known Shannon entropy with several other entropy notions, like the min-entropy or collision entropy. In contrast to the Shannon entropy, there seems to be no commonly accepted definition for the conditional Rényi entropy: several versions have been proposed and used in the literature. In this paper, we reconsider the definition for the conditional Rényi entropy of general order as proposed by Arimoto in the seventies. We show that this particular notion satisfies several natural properties. In particular, we show that it satisfies monotonicity under conditioning, meaning that conditioning can only reduce the entropy, and (a weak form of) chain rule, which implies that the decrease in entropy due to conditioning is bounded by the number of bits one conditions on. None of the other suggestions for the conditional Rényi entropy satisfies both these properties. Finally, we show a natural interpretation of the conditional Rényi entropy in terms of (unconditional) Rényi divergence, and we show consistency with a recently proposed notion of conditional Rényi entropy in the quantum setting.

We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}n x {0,1}n -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y).

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient and noninteractive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.