Aug 2026· IACR Cryptology ePrint Archive· Vol 2026, pp. 906· 1 citation· 30 references
Computer Science
TL;DR
This work shows that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold, and extends the analysis to the assumption used in the security proof in the (quantum) random oracle model.
Abstract
PRISM (PKC25) is a hash-and-sign signature scheme whose security relies on the hardness of computing large-prime-degree isogenies originating from a curve of unknown endomorphism ring. In PRISM, the degree of such isogenies is obtained by hashing messages onto a set of large odd integers that pass a primality test.
In this work, we investigate the impact of the choice of primality test on the security of PRISM. We first show that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold. We then extend our analysis to the assumption used in the security proof in the (quantum) random oracle model. In this setting, we argue that the Miller-Rabin test suffices and estimate the minimal number of iterations required for PRISM to achieve the desired security level, thus minimising signing costs.
It is shown that in the absence of inner collisions, the probability of finding x preimages decreases exponentially with x, which means that increasing x strengthens security only while direct multi-preimage search remains the dominant attack strategy.
The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutati...
It is shown that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits, and (b) collision-resistant hash functions, and (c) SNARGs for $\mathsf{P}$.
This study proposes a novel signcryption scheme based on the algebraic structure of the group ring and proves its provable security, and shows that the security of the scheme relies on the intractability of two hard problems, i.e., bilinear Diffie–Hellman inversion in group ring and bilinear strong Diffie–Hellman assum...
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, wh...
Zvika Brakerski, Andrew Huang, Y. Kalai et al.· 0 citations
We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt''assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state g...
James Bartusek, Giulio Malavolta· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
