International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ward Beullens

Publications

Year
Venue
Title
2021
EUROCRYPT
Improved cryptanalysis of UOV and Rainbow
Ward Beullens
The contributions of this paper are twofold. First, we simplify the description of the Unbalanced Oil and Vinegar scheme (UOV) and its Rainbow variant, which makes it easier to understand the scheme and the existing attacks. We hope that this will make UOV and Rainbow more approachable for cryptanalysts. Secondly, we give two new attacks against the UOV and Rainbow signature schemes; the intersection attack that applies to both UOV and Rainbow and the rectangular MinRank attack that applies only to Rainbow. Our attacks are more powerful than existing attacks. In particular, we estimate that compared to previously known attacks, our new attacks reduce the cost of a key recovery by a factor of 2^17, 2^53, and 2^73 for the parameter sets submitted to the second round of the NIST PQC standardization project targeting the security levels I, III, and V respectively. For the third round parameters, the cost is reduced by a factor of 2^20, 2^40, and 2^55 respectively. This means all these parameter sets fall short of the security requirements set out by NIST.
2020
EUROCRYPT
Sigma protocols for MQ, PKP and SIS, and fishy signature schemes 📺
Ward Beullens
This work presents sigma protocols to prove knowledge of: - a solution to a system of quadratic polynomials, - a solution to an instance of the Permuted Kernel Problem and - a witness for a variety of lattice statements (including SIS). Our sigma protocols have soundness error 1/q', where q' is any number bounded by the size of the underlying finite field. This is much better than existing proofs, which have soundness error 2/3 or (q'+1)/2q'. The prover and verifier time our proofs are O(q'). We achieve this by first constructing so-called sigma protocols with helper, which are sigma protocols where the prover and the verifier are assisted by a trusted third party, and then eliminating the helper from the proof with a "cut-and-choose" protocol. We apply the Fiat-Shamir transform to obtain signature schemes with security proof in the QROM. We show that the resulting signature schemes, which we call the "MUltivariate quaDratic FIat-SHamir" scheme (MUDFISH) and the "ShUffled Solution to Homogeneous linear SYstem FIat-SHamir" scheme (SUSHSYFISH), are more efficient than existing signatures based on the MQ problem and the Permuted Kernel Problem. Our proof system can be used to improve the efficiency of applications relying on (generalizations of) Stern's protocol. We show that the proof size of our SIS proof is smaller than that of Stern's protocol by an order of magnitude and that our proof is more efficient than existing post-quantum secure SIS proofs.
2020
TOSC
Cryptanalysis of the Legendre PRF and Generalizations 📺
The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain.This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from O(< (p log p/M) to O(p log2 p/M2) Legendre symbol evaluations when M ≤ 4√ p log2 p queries are available. The practical relevance of our improved attack is demonstrated by breaking three concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.
2020
ASIACRYPT
Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices 📺
We construct efficient ring signatures (RS) from isogeny and lattice assumptions. Our ring signatures are based on a logarithmic OR proof for group actions. We instantiate this group action by either the CSIDH group action or an MLWE-based group action to obtain our isogeny-based or lattice-based RS scheme, respectively. Even though the OR proof has a binary challenge space and therefore requires a number of repetitions which is linear in the security parameter, the sizes of our ring signatures are small and scale better with the ring size N than previously known post-quantum ring signatures. We also construct linkable ring signatures (LRS) that are almost as efficient as the non-linkable variants. The isogeny-based scheme produces signatures whose size is an order of magnitude smaller than all previously known logarithmic post-quantum ring signatures, but it is relatively slow (e.g. 5.5 KB signatures and 79 s signing time for rings with 8 members). In comparison, the lattice-based construction is much faster, but has larger signatures (e.g. 30 KB signatures and 90 ms signing time for the same ring size). For small ring sizes our lattice-based ring signatures are slightly larger than state-of-the- art schemes, but they are smaller for ring sizes larger than N approximately 1024.
2019
PKC
Obfuscating Simple Functionalities from Knowledge Assumptions
Ward Beullens Hoeteck Wee
This paper shows how to obfuscate several simple functionalities from a new Knowledge of OrthogonALity Assumption (KOALA) in cyclic groups which is shown to hold in the Generic Group Model. Specifically, we give simpler and stronger security proofs for obfuscation schemes for point functions, general-output point functions and pattern matching with wildcards. We also revisit the work of Bishop et al. (CRYPTO 2018) on obfuscating the pattern matching with wildcards functionality. We improve upon the construction and the analysis in several ways:attacks and stronger guarantees: We show that the construction achieves virtual black-box security for a simulator that runs in time roughly $$2^{n/2}$$, as well as distributional security for larger classes of distributions. We give attacks that show that our results are tight.weaker assumptions: We prove security under KOALA.better efficiency: We also provide a construction that outputs $$n+1$$ instead of 2n group elements. We obtain our results by first obfuscating a simpler “big subset functionality”, for which we establish full virtual black-box security; this yields a simpler and more modular analysis for pattern matching. Finally, we extend our distinguishing attacks to a large class of simple linear-in-the-exponent schemes.
2019
ASIACRYPT
CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations
In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first sketched by Stolbunov. We further optimize the scheme using multiple public keys and Merkle trees, following an idea by De Feo and Galbraith. We also show that including quadratic twists allows to cut the public key size in half for free. Optimizing for signature size, our implementation takes 390 ms to sign/verify and results in signatures of 263 bytes, at the expense of a large public key. This is 300 times faster and over 3 times smaller than an optimized version of SeaSign for the same parameter set. Optimizing for public key and signature size combined, results in a total size of 1468 bytes, which is smaller than any other post-quantum signature scheme at the 128-bit security level.
2018
ASIACRYPT
Practical Attacks Against the Walnut Digital Signature Scheme
Ward Beullens Simon R. Blackburn
Recently, NIST started the process of standardizing quantum-resistant public-key cryptographic algorithms. WalnutDSA, the subject of this paper, is one of the 20 proposed signature schemes that are being considered for standardization. Walnut relies on a one-way function called E-Multiplication, which has a rich algebraic structure. This paper shows that this structure can be exploited to launch several practical attacks against the Walnut cryptosystem. The attacks work very well in practice; it is possible to forge signatures and compute equivalent secret keys for the 128-bit and 256-bit security parameters submitted to NIST in less than a second and in less than a minute respectively.