2022
|
May, Alexander; Zweydinger, Floyd Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing Inproceedings 35th IEEE Computer Security Foundations Symposium, pp. 11, IEEE, 2022. Links | BibTeX @inproceedings{May2022,
title = {Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing},
author = {Alexander May and Floyd Zweydinger},
url = {https://iblockchain-projekt.de/wp-content/uploads/2021/08/2021-645.pdf
https://eprint.iacr.org/2021/645
https://www.ieee-security.org/TC/CSF2022/index.html},
year = {2022},
date = {2022-08-01},
booktitle = {35th IEEE Computer Security Foundations Symposium},
pages = {11},
publisher = {IEEE},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
|
Esser, Andre; Zweydinger, Floyd; May, Alexander McEliece needs a Break -- Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD Inproceedings Eurocrypt 2022 , IACR, 2022. Abstract | Links | BibTeX @inproceedings{Esser2022,
title = {McEliece needs a Break -- Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD },
author = {Andre Esser and Floyd Zweydinger and Alexander May },
url = {https://eprint.iacr.org/2021/1634},
year = {2022},
date = {2022-05-30},
booktitle = {Eurocrypt 2022 },
publisher = {IACR},
abstract = {With the recent shift to post-quantum algorithms it becomes increasingly important to provide precise bit-security estimates for code-based cryptography such as McEliece and quasi-cyclic schemes like BIKE and HQC. While there has been significant progress on information set decoding (ISD) algorithms within the last decade, it is still unclear to which extent this affects current cryptographic security estimates.
We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938).
Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST's standardization process.
For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC.
For the proposed McEliece round-3 parameter sets of 192 and 256 bit, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
With the recent shift to post-quantum algorithms it becomes increasingly important to provide precise bit-security estimates for code-based cryptography such as McEliece and quasi-cyclic schemes like BIKE and HQC. While there has been significant progress on information set decoding (ISD) algorithms within the last decade, it is still unclear to which extent this affects current cryptographic security estimates.
We provide the first concrete implementations for representation-based ISD, such as May-Meurer-Thomae (MMT) or Becker-Joux-May-Meurer (BJMM), that are parameter-optimized for the McEliece and quasi-cyclic setting. Although MMT and BJMM consume more memory than naive ISD algorithms like Prange, we demonstrate that these algorithms lead to significant speedups for practical cryptanalysis on medium-sized instances (around 60 bit). More concretely, we provide data for the record computations of McEliece-1223 and McEliece-1284 (old record: 1161), and for the quasi-cyclic setting up to code length 2918 (before: 1938).
Based on our record computations we extrapolate to the bit-security level of the proposed BIKE, HQC and McEliece parameters in NIST's standardization process.
For BIKE/HQC, we also show how to transfer the Decoding-One-Out-of-Many (DOOM) technique to MMT/BJMM. Although we achieve significant DOOM speedups, our estimates confirm the bit-security levels of BIKE and HQC.
For the proposed McEliece round-3 parameter sets of 192 and 256 bit, however, our extrapolation indicates a security level overestimate by roughly 20 and 10 bits, respectively, i.e., the high-security McEliece instantiations may be a bit less secure than desired. |
2021
|
Faust, Sebastian; Hazay, Carmit; Kretzler, David; Schlosser, Benjamin Financially Backed Covert Security Inproceedings Public-Key Cryptography - (PKC) 2022 - 25th {IACR} International Conference on Practice and Theory of Public Key Cryptography, Virtual Event,
May 07-11, 2021, Proceedings, 2021. Links | BibTeX @inproceedings{cryptoeprint:2021:1652,
title = {Financially Backed Covert Security},
author = {Sebastian Faust and Carmit Hazay and David Kretzler and Benjamin Schlosser},
url = {https://eprint.iacr.org/2021/1652.pdf},
year = {2021},
date = {2021-12-16},
booktitle = {Public-Key Cryptography - (PKC) 2022 - 25th {IACR} International Conference on Practice and Theory of Public Key Cryptography, Virtual Event,
May 07-11, 2021, Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
|
Das, Poulami; Erwig, Andreas; Faust, Sebastian; Loss, Julian; Riahi, Siavash The Exact Security of BIP32 Wallets Inproceedings CCS ’21- Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2021. BibTeX @inproceedings{Das2021,
title = {The Exact Security of BIP32 Wallets},
author = {Poulami Das and Andreas Erwig and Sebastian Faust and Julian Loss and Siavash Riahi
},
year = {2021},
date = {2021-11-15},
booktitle = {CCS ’21- Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security},
publisher = {ACM},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
|
Döttling, Nico; Hartmann, Dominik; Hofheinz, Dennis; Kiltz, Eike; Schäge, Sven; Ursu, Bogdan On the Impossibility of Purely Algebraic Signatures Inproceedings Theory of Cryptography (TCC 2021), Springer International Publishing, 2021. Abstract | Links | BibTeX @inproceedings{Döttling2021,
title = {On the Impossibility of Purely Algebraic Signatures},
author = {Nico Döttling and Dominik Hartmann and Dennis Hofheinz and Eike Kiltz and Sven Schäge and Bogdan Ursu},
url = {https://eprint.iacr.org/2021/738},
year = {2021},
date = {2021-11-08},
booktitle = {Theory of Cryptography (TCC 2021)},
publisher = {Springer International Publishing},
abstract = {The existence of one-way functions implies secure digital signatures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes.
Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show: - the insecurity of all signature schemes in Maurer's generic group model (in pairing-free groups), as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions. - the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.
We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures. },
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The existence of one-way functions implies secure digital signatures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes.
Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show: - the insecurity of all signature schemes in Maurer's generic group model (in pairing-free groups), as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions. - the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.
We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures. |