CWI Cryptology Group

Abstract: We initiate the study of basing the hardness of hinted ISIS problems (i.e. with trapdoor information, or ‘hints’) on the previously conjectured space-time hardness of lattice problems without hints. We present two main results. 1. If there exists an efficient algorithm for hinted ISIS that outputs solutions a constant factor longer than the hints, then there exists a single-exponential time and polynomial memory zero-centred spherical Gaussian sampler solving hinted SIS with norm a constant factor shorter than the hints. 2. Assume the existence of a chain of algorithms for hinted ISIS each taking as input Gaussian hints whose norms decrease by a constant factor at each step in the chain, then there exists a single-exponential time and polynomial memory algorithm for SIS with norm a quasilinear factor from optimal. The existence of such hinted ISIS solvers implies single-exponential time and polynomial memory algorithms for worst-case lattice problems, contradicting a conjecture by Lombardi and Vaikuntanathan (CRYPTO’20) and all known algorithms. This suggests that hinted ISIS is hard. Apart from advancing our understanding of hinted lattice problems, an immediate consequence is that signing the same message twice in GPV-style [Gentry–Peikert–Vaikuntanathan, STOC’08] schemes (without salting or derandomisation) likely does not compromise unforgeability. Also, cryptanalytic attempts on the One-More-ISIS problem [Agrawal–Kirshanova–Stehlé-Yadav, CCS’22] likely will need to overcome the conjectured space-time hardness of lattices.

Abstract: A central challenge in quantum algorithm analysis and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, a random permutation, a random unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? Classically, an important tool for this is lazy sampling, where the oracle does not commit to the full group element at the beginning, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles), which are quantum data structures that allow such on-the-fly simulation for quantum queries. Compressed oracles were originally introduced by Zhandry (CRYPTO '19) for random functions, were generalized to random unitaries by Ma-Huang (STOC '25) and to permutations by Carolan (STOC '26), and have been employed to great effect in security proofs and query complexity lower bounds due to their interpretability. In this work, we define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of U(N). Our path-recording oracle stores superpositions of t input-output pairs |(x₁, y₁), …, (xₜ, yₜ)⟩, which encode a Feynman path explored by the algorithm and thus transparently record the information that the algorithm may have learned from its queries. Our compressed oracle builds on a recent work of Grinko and Yoshida (QIP '26), who proposed a different kind of general-purpose compressed oracle without clear interpretability. Crucially for applications, we derive an operationally useful mathematical description of our update procedure in terms of the commutant of the group's tensor power representation. One powerful feature of our path-recording oracle is that it enables direct comparisons between compressed oracles for different groups, which gives a new technique for proving pseudorandomness results. For our main application, we formally relate the S_N and U(N) compressed oracles, yielding what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford. This improves on the prior "PFC" construction of (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25). Based on joint work with Ben Foxman, Alex Lombardi, Fermi Ma, and John Wright

Abstract: The Lattice Isomorphism Problem asks whether two given lattices L1 and L2 are related by an orthogonal linear transformation. Haviv and Regev gave a seminal nO(n)-time algorithm for this problem based on an isolation lemma (SODA 2014). We give algorithms for the decision, search, and all-isomorphisms versions of the problem running in time nn+o(n) times a polynomial in the input size. The main new ingredient is a Gaussian heat argument over convex bodies generated by shortest vectors: for w ∼ DL∗,s, the vector w canonically determines n−o(n) independent shortest vectors, leaving a residual instance of rank o(n). The remaining residual dimensions are handled by an no(n)-time canonicalizer obtained by adapting the Haviv–Regev algorithm. We then combine this canonicalizer with a birthday argument to recover all isomorphisms. For the all-isomorphisms version, this bound is asymptotically optimal in the worst case up to an no(n) factor. As an extension, we also give, in the QRAM model, a quantum variant running in time n 2 3 n+o(n). It outputs a representative isomorphism together with generators for the automorphism group, thereby providing a compact description of the entire isomorphism coset.

Abstract: Vector Commitments allow parties to commit to an (ordered) vector and to later succinctly open it at any desired position. In plain (i.e., known order and pairing-free) prime-order groups, all state-of-the-art constructions rely on the combination of a generalized Pedersen commitment and an inner product argument. This includes the celebrated constructions of Bootle et al. (EUROCRYPT 2016) and Bünz et al. (S\&P 2018) and subsequent improvements. All of these achieve proofs consisting of $\Theta(\log n)$ group elements, and further provide useful properties including malleability, subvector opening and transparent setup. However, breaking the $O(\log n)$ barrier in the plain discrete logarithm setting has proven to be a hard problem. This is in stark contrast with other settings, e.g. from pairing-friendly groups or groups of unknown order, where constructions with constant-size commitment and openings have been known for over a decade. In this work we investigate whether this limitation is inherent to constructions based on prime-order groups. Specifically we prove new lower bounds for any accumulator (a weaker object than vector commitments, thus making our result more general), with interactive public-coin membership proof in Maurer's Generic Group Model. An implication of our result is that in such setting at least one of the following must occur: (i) the commitment has super-constant size; (ii) the opening proof contains $\Omega(\log n)$ group elements; (iii) the opening proof has length $n^{1-o(1)}$. Our bound further extends to primitives that directly imply accumulators/VC including polynomial/functional commitments and inner product arguments.

Abstract:  Blind Signature schemes allow a user to obtain a digital signature on a message, without revealing the actual message to the signer. Non-Interactive Blind Signatures are a recently introduced variant, in which the signer can generate a blinded signature for a user on a random message, without requiring any interaction between the two parties. In this thesis, we investigate if existing impossibility results for Blind Signatures also apply to the Non-Interactive case. To this end, we first introduce a new scheme called Random-Message Blind Signatures, which is implied by both regular and Non-Interactive Blind Signatures. We then use this to show that (1) Non-Interactive Blind Signatures cannot be constructed in a black-box way from random oracles and (2) Non-Interactive Blind Signatures that make at most a logarithmic amount of random oracle queries cannot be constructed in a black-box way from random oracles and pairing-free groups.