We construct the first blind signature scheme that achieves all of the following properties simultaneously: The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 $$\mathbb {Z} _p$$ -elements. Our scheme starts from a pairing-based non-blind signature scheme (Abe et al., JoC 2023), and uses recent techniques of Chairattana-Apirom, Tessaro, and Zhu (CRYPTO 2024) to replace the pairings used in this scheme with non-interactive zero-knowledge proofs in the random oracle model. This conversion is not generic or straightforward (also because prior works have converted only significantly simpler signature schemes), and we are required to improve upon and innovate existing techniques in several places. As an interesting side note, and unlike previous works, our techniques only require a non-programmable random oracle, and our signature scheme achieves predicate blindness (which means that the user can prove statements about the signed message during the signing process).

Abstract We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (CRYPTO 2013, Springer, 2013). The security loss of our reduction is $$\textbf{O} (k)$$ O(k) (where $$k $$ k is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to “lift” their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.

Abstract In structure-preserving cryptography, every building block shares the same bilinear groups. These groups must be generated for a specific, a priori fixed security level, and thus, it is vital that the security reduction in all involved building blocks is as tight as possible. In this work, we present the first generic construction of structure-preserving signature schemes whose reduction cost is independent of the number of signing queries. Its chosen-message security is almost tightly reduced to the chosen-plaintext security of a structure-preserving public-key encryption scheme and the security of Groth–Sahai proof system. Technically, we adapt the adaptive partitioning technique by Hofheinz (Eurocrypt 2017) to the setting of structure-preserving signature schemes. To achieve a structure-preserving scheme, our new variant of the adaptive partitioning technique relies only on generic group operations in the scheme itself. Interestingly, however, we will use non-generic operations during our security analysis. Instantiated over asymmetric bilinear groups, the security of our concrete scheme is reduced to the external Diffie–Hellman assumption with linear reduction cost in the security parameter, independently of the number of signing queries. The signatures in our schemes consist of a larger number of group elements than those in other non-tight schemes, but can be verified faster, assuming their security reduction loss is compensated by increasing the security parameter to the next standard level.

Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e:Gκ⟶GT for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ GT . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e:G1×⋯×Gκ⟶GT for a collection of $$\kappa +1$$ κ+1 prime-order groups $${\mathbb {G}}_i$$ Gi and $${\mathbb {G}}_T$$ GT , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ ZN+ . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate more random coins. A bit more formally, our goal is to generate n common random coins from a single use of an ideal functionality that gives $$m

We describe CoSP, a general framework for conducting computational soundness proofs of symbolic models and for embedding these proofs into formal calculi. CoSP considers arbitrary equational theories and computational implementations, and it abstracts away many details that are not crucial for proving computational soundness, such as message scheduling, corruption models, and even the internal structure of a protocol. CoSP enables soundness results, in the sense of preservation of trace properties, to be proven in a conceptually modular and generic way: proving x cryptographic primitives sound for y calculi only requires x + y proofs (instead of x • y proofs without this framework), and the process of embedding calculi is conceptually decoupled from computational soundness proofs of cryptographic primitives. We exemplify the usefulness of CoSP by proving the first computational soundness result for the full-fledged applied π-calculus under active attacks. Concretely, we embed the applied π-calculus into CoSP and give a sound implementation of public-key encryption and digital signatures.

We elaborate on the problem of polynomial runtime in simulatability definitions for multi-party computation. First, the need for a new definition is demonstrated by showing which problems occur with common definitions of polynomial runtime. Then, we give a definition which captures in an intuitive manner what it means for a protocol or an adversary to have polynomial runtime. We show that this notion is suitable for simulatability definitions for multi-party computation. In particular, a composition theorem is shown for this notion.

Simulatable security is a security notion for multi-party protocols that implies strong composability features. The main definitional flavours of simulatable security are standard simulatability, universal simulatability, and black-box simulatability. All three come in "computational," "statistical" and "perfect" subflavours indicating the considered adversarial power. Universal and black-box simulatability, in all of their subflavours, are already known to guarantee that the concurrent composition even of a polynomial number of secure protocols stays secure. We show that computational standard simulatability does not allow for secure concurrent composition of polynomially many protocols, but we also show that statistical standard simulatability does. The first result assumes the existence of an interesting cryptographic tool (namely time-lock puzzles), and its proof employs a cryptographic multi-party computation in an interesting and unconventional way

We elaborate on the problem of polynomial runtime in simulatability definitions for multiparty computation. First, the need for a new definition is demonstrated by showing which problems occur with common definitions of polynomial runtime. Then, we give a definition which captures in an intuitive manner what it means for a protocol or an adversary to have polynomial runtime. We show that this notion is suitable for simulatability definitions for multiparty computation. In particular, a composition theorem is shown for this notion.