Paper 2019/1122

Exploring Trade-offs in Batch Bounded Distance Decoding

Martin R. Albrecht, Benjamin R. Curtis, and Thomas Wunderer


Algorithms for solving the Bounded Distance Decoding problem (BDD) are used for estimating the security of lattice-based cryptographic primitives, since these algorithms can be employed to solve variants of the Learning with Errors problem (LWE). In certain parameter regimes where the target vector is small and/or sparse, batches of BDD instances emerge from a combinatorial approach where several components of the target vector are guessed before decoding. In this work we explore trade-offs in solving ``Batch-BDD'', and apply our techniques to the small-secret Learning with Errors problem. We compare our techniques to previous works which solve batches of BDD instances, such as the hybrid lattice-reduction and meet-in-the-middle attack. Our results are a mixed bag. We show that, in the ``enumeration setting'' and with BKZ reduction, our techniques outperform a variant of the hybrid attack which does not consider time-memory trade-offs in the guessing phase for certain Round5 (17-bits out of 466), Round5-IoT (19-bits out of 240), and NTRU LPrime (23-bits out of 385) parameter sets. On the other hand, our techniques do not outperform the Hybrid Attack under standard, albeit unrealistic, assumptions. Finally, as expected, our techniques do not improve on previous works in the ``sieving setting'' (under standard assumptions) where combinatorial attacks in general do not perform well.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Selected Areas in Cryptography (SAC) 2019
Bounded Distance DecodingLearning with ErrorsCryptanalysisHybrid Attack
Contact author(s)
benjamin curtis 2015 @ rhul ac uk
2019-10-01: received
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Benjamin R.  Curtis and Thomas Wunderer},
      title = {Exploring Trade-offs in Batch Bounded Distance Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1122},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.