Our purpose is to compare how much the F5 algorithm can gain in efficiency compared to the F4 algorithm. This can be achieve as the F5 algorithm uses the concept of signatures to foresee potential useless computation which the F4 algorithm might make represented by zero rows in the reduction of a large matrix. We experimentally show that this is a modest increase in efficiency for the parameters we tested.
Jintai DingUniversity of Cincinnati, OH, USAJoshua DeatonUniversity of Cincinnati, OH, USAVishakhaUniversity of Cincinnati, OH, USABo-Yin YangInstitute of Information Science and Research Center of Information Technology and Innovation, Academia Sinica, 128 Section 2 Academia Road, Taipei 115-29, Taiwan
In 2017, Ward Beullenset al.submitted Lifted Unbalanced Oil andVinegar, which is a modification to the Unbalanced Oil and Vinegar Schemeby Patarin. Previously, Dinget al.proposed the Subfield Differential Attack which prompted a change of parameters by the authors of LUOV for the sec-ond round of the NIST post quantum standardization competition. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the pa-rameter sets put forward. We also show by experimentation that this attack ispractically possible to do in under 210 minutes for the level I security param-eters and not just a theoretical attack. The Nested Subset Differential attack isa large improvement of the Subfield differential attack which can be used inreal world circumstances. Moreover, we will only use what is called the "lifted"structure of LUOV, and our attack can be thought as a development of solving"lifted" quadratic systems.
Jintai DingUniversity of Cincinnati, Ohio, USADoug EmeryUniversity of Cincinnati, Ohio, USAJohannes MuellerSnT, University of Luxembourg, LuxembourgPeter Y. A. RyanSnT, University of Luxembourg, LuxembourgVonn Kee WongUniversity of Cincinnati, Ohio, USA
Anonymous veto networks (AV-nets), originally proposed by Hao and Zielinski (2006), are particularly lightweight protocols for evaluating a veto function in a peer-to-peer network such that anonymity of all protocol participants is preserved. Prior to this work, anonymity in all AV-nets from the literature relied on the decisional Diffie-Hellman (DDH) assumption and can thus be broken by (scalable) quantum computers. In order to defend against this threat, we propose two practical and completely lattice-based AV-nets. The first one is secure against passive and the second one is secure against active adversaries. We prove that anonymity of our AV-nets reduces to the ring learning with errors (RLWE) assumption. As such, our AV-nets are the first ones with post-quantum anonymity. We also provide performance benchmarks to demonstrate their practicality.
Chengdong TaoDing Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, ChinaAlbrecht PetzoldtFAU Erlangen-Nuremberg, Nuremberg, GermanyJintai DingYau Mathematical Center, Tsinghua University, Beijing, China; Ding Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, China; Ding Lab, Beijing Institute of Mathematical Sci. and Applications, Beijing, China
The HFEv- signature scheme is a twenty year old multivariate public key signature scheme. It uses the Minus and the Vinegar modifier on the original HFE scheme. An instance of the HFEv- signature scheme called GeMSS is one of the alternative candidates for signature schemes in the third round of the NIST Post Quantum Crypto (PQC) Standardization Project. In this paper, we propose a new key recovery attack on the HFEv- signature scheme. We show that the Minus modification does not enhance the security of cryptosystems of the HFE family, while the Vinegar modification increases the complexity of our attack only by a polynomial factor. By doing so, we show that the proposed parameters of the GeMSS scheme are not as secure as claimed. Our attack shows that it is very difficult to build a secure and efficient signature scheme on the basis of HFEv-.
In this paper, we present a simple attack on LWE and Ring LWE encryption schemes used directly as Key Encapsulation Mechanisms (KEMs). This attack could work due to the fact that a key mismatch in a KEM is accessible to an adversary. Our method clearly indicates that any LWE or RLWE (or any similar type of construction) encryption directly used as KEM can be broken by modifying our attack method according to the respective cases.