Sampling Hollow Linear Codes and Updatable Public-Key Encryption

This archive contains the code artifacts accompanying [1] accepted at Eurocrypt 2025. It contains the following two files:

• selforthogonal.py: a library for sampling linear codes with a desired hull dimension, implementing the algorithms in Section 3 of [1], and
• parameters.py: a parameter selection script based on the Lattice Estimator [2] for the UPKE scheme presented in Section 5 of [1].

Both depend on SageMath version 10.x [3].

Installation

Provided you have SageMath version 10.x installed, you may also install the Lattice Estimator to run parameters.py, by simply running

git clone https://github.com/malb/lattice-estimator/ estimator

in this directory. Skip this if you only intend to use selforthogonal.py.

Documentation

To get a list of all functions of e.g. selforthogonal.py and their respective documentation, import it as a module in SageMath and run help:

sage: import selforthogonal
sage: help(selforthogonal)

Analogous for parameters.py.

These two files are not meant to be called as standalone programs, although parameters.py will print Table 1 of [1] when called, for those seeking to reproduce it.

Organisation of selforthogonal.py

The library first defines a number of useful functions for:

• sampling random (signed) permutations and monomial matrices,
• computing a generator matrix for the dual and hull of a given linear code,
• algebraically "dehulling" a linear code, that is finding T such that span(A) = hull(span(A)) + span(T),
• computing the (signed) closure of a linear code, etc.

Throughout, a linear code is represented by (one of) its row generator matrices. Next, the algorithms featured in Section 3 of [1] are implemented:

• MaxSols(D,F): computes the maximal number of solutions a smooth conic with discriminant D over the finite field F can have,
• SampleSelfOrthogonal(A,halt): samples a uniformly random self-orthogonal codeword from the linear code generated by A,
• SampleCode(n,k,h,q): samples a uniformly random [n,k]-linear h-hollow code over FF_q.

The function random_selforthogonal_code(n,k,q) is a special case of SampleCode that produces, as the name suggests, a random self-orthogonal linear code, justifying Footnote 12 of [1].

Organisation of parameters.py

The function upke_params() chooses the parameters for the scheme based on a number of options, returning a UPKEParams dataclass. Calling .display() on this object prints out the scheme parameters, along with

• the minimal hull dimension h needed for the scheme to be secure w.r.t. the specified security parameter,
• the ciphertext size in kilobytes, and
• the update token size in kilobytes.

The function table1() uses the above to produce the results presented in Table 1 of [1].

Licenses

The contents of this archive are licensed under the LGPLv3+, a copy of which is provided.

Dependencies:
* The Lattice Estimator [2] is licensed under LGPLv3+.
* The whole Sage software distribution [3] is licensed under GPLv3+, as discussed here.

References

[1] Albrecht, M. R., Benčina, B., Lai, R. W. F.: Hollow LWE: A New Spin, Unbounded Upadatable Encryption from LWE and PCE. In: EUROCRYPT 2025.
[2] Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology 9(3), 169–203 (October 2015), available here
[3] SageMath, the Sage Mathematics Software System. Available here