International Association
for Cryptologic Research

We construct the first blind signature scheme that achieves all of the following properties simultaneously: — it is tightly secure under a standard (i.e., non-interactive, non-q-type) computational assumption, — it does not require pairings, — it does not rely on generic, non-black-box techniques (like generic NIZK proofs). The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 Zp-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).

The hardness of Kolmogorov complexity is intricately connected to the existence of oneway functions and derandomization. An important and elegant notion is Levin’s version of Kolmogorov complexity, Kt, and its decisional variant, MKtP. The question whether MKtP can be computed in polynomial time is particularly interesting because it is not subject to known technical barriers such as algebrization or natural proofs that would explain the lack of a proof for MKtP ∉ P. We take a major step towards proving MKtP ∉ P by developing a novel yet simple diagonalization technique to show unconditionally that MKtP ∉ DTIME[O(n)], i.e., no deterministic algorithm can solve MKtP on every instance. This allows us to affirm a conjecture by Ren and Santhanam [STACS22] about a non-halting variant of Kt complexity. Additionally, we give conditional lower bounds for MKtP that tolerate either more runtime or one-sided error.

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions. In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.