International Association
for Cryptologic Research

We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

Anamorphic Encryption, recently introduced by Persiano, Phan, and Yung (EUROCRYPT 2022) is a new cryptographic paradigm challenging the conventional notion of an adversary. In particular they consider the receiver-anamorphic setting, where a dictator is able to obtain the receiver's secret key of a well-established public-key encryption (PKE) scheme, and they ask the question whether the sender can still embed covert messages in a way which the dictator is completely oblivious to, if sender and receiver share an anamorphic key.

In this work, we identify two definitional limitations of Persiano et al.'s original model. First, they require anamorphic keys and key-pairs to be generated together, so a first modification we propose is to decouple the two processes. We allow for the extension of a regular PKE scheme to an anamorphic one to be possible on the fly, even after the public key of the regular scheme is already in use. Second, in their model the receiver cannot distinguish whether or not a ciphertext contains a covert message, so we propose a natural robustness notion which states that when anamorphically decrypting a regularly encrypted message, the receiver explicitly sees that no covert message is contained. This also eliminates certain attacks possible for the original definition.

Regarding new constructions, we first propose a generic anamorphic extension that achieves robustness for any PKE scheme, but requires synchronization of sender and receiver. We then define a natural property of a PKE scheme, selective randomness recoverability, which allows for a robust anamorphic extension even for unsynchronized parties. We show that the well-established schemes of ElGamal and Cramer-Shoup satisfy this condition. Finally, we propose a generic transformation of any non-robust anamorphic extension into a robust one, and apply it to a synchronized anamorphic extension for RSA-OAEP.

Hierarchical Identity Based Encryption (HIBE) is a well studied, versatile tool used in many cryptographic protocols. Yet, since the performance of all known HIBE constructions is broadly considered prohibitive, some real-world applications avoid relying on HIBE at the expense of security. A prominent example for this is secure messaging: Strongly secure messaging protocols are provably equivalent to Key-Updatable Key Encapsulation Mechanisms (KU-KEMs; Balli et al., Asiacrypt 2020); so far, all KU-KEM constructions rely on adaptive unbounded-depth HIBE (Poettering and Rösler, Jaeger and Stepanovs, both CRYPTO 2018). By weakening security requirements for better efficiency, many messaging protocols dispense with using HIBE.

In this work, we aim to gain better efficiency without sacrificing security. For this, we observe that applications like messaging only need a restricted variant of HIBE for strong security. This variant, that we call Unique-Path Identity Based Encryption (UPIBE), restricts HIBE by requiring that each secret key can delegate at most one subordinate secret key. However, in contrast to fixed secret key delegation in Forward-Secure Public Key Encryption, the delegation in UPIBE, as in HIBE, is uniquely determined by variable identity strings from an exponentially large space. We investigate this mild but surprisingly effective restriction and show that it offers substantial complexity and performance advantages.

More concretely, we generically build bounded-depth UPIBE from only bounded-collusion IBE in the standard model; and we generically build adaptive unbounded-depth UPIBE from only selective bounded-depth HIBE in the random oracle model. These results significantly extend the range of underlying assumptions and efficient instantiations. We conclude with a rigorous performance evaluation of our UPIBE design. Beyond solving challenging open problems by reducing complexity and improving efficiency of KU-KEM and strongly secure messaging protocols, we offer a new definitional perspective on the bounded-collusion setting.

The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel sieving-style information-set decoding (ISD) algorithm for solving the syndrome decoding problem. The essential idea is to keep a list of weight-$2p$ solution vectors to a partial syndrome decoding problem and then create new vectors by finding pairs of vectors that collide in $p$ positions. By increasing the parity-check condition by one position and then iteratively repeating this process, we find the final solution(s). We show that while being competitive in terms of performance, our novel algorithm requires significantly less memory compared to other ISD variants. Also, in the case of problems with very low relative weight, it seems to outperform all previous algorithms. In particular, for code-based candidates BIKE and HQC, the algorithm has lower bit complexity than the previous best results.

We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.

Lyubashevky's signatures are based on the Fiat-Shamir with Aborts paradigm. It transforms an interactive identification protocol that has a non-negligible probability of aborting into a signature by repeating executions until a loop iteration does not trigger an abort. Interaction is removed by replacing the challenge of the verifier by the evaluation of a hash function, modeled as a random oracle in the analysis. The access to the random oracle is classical (ROM), resp. quantum (QROM), if one is interested in security against classical, resp. quantum, adversaries. Most analyses in the literature consider a setting with a bounded number of aborts (i.e., signing fails if no signature is output within a prescribed number of loop iterations), while practical instantiations (e.g., Dilithium) run until a signature is output (i.e., loop iterations are unbounded).

In this work, we emphasize that combining random oracles with loop iterations induces numerous technicalities for analyzing correctness, run-time, and security of the resulting schemes, both in the bounded and unbounded case. As a first contribution, we put light on errors in all existing analyses. We then provide two detailed analyses in the QROM for the bounded case, adapted from Kiltz et al. [EUROCRYPT'18] and Grilo et al. [ASIACRYPT'21]. In the process, we prove the underlying $\Sigma$-protocol to achieve a stronger zero-knowledge property than usually considered for $\Sigma$-protocols with aborts, which enables a corrected analysis. A further contribution is a detailed analysis in the case of unbounded aborts, the latter inducing several additional subtleties.

Properties of quantum mechanics have enabled the emergence of quantum cryptographic protocols achieving important goals which are proven to be impossible classically. Unfortunately, this usually comes at the cost of needing quantum power from every party in the protocol, while arguably a more realistic scenario would be a network of classical clients, classically interacting with a quantum server. In this paper, we focus on copy-protection, which is a quantum primitive that allows a program to be evaluated, but not copied, and has shown interest especially due to its links to other unclonable cryptographic primitives. Our main contribution is to show how to dequantize existing quantum copy-protection from hidden coset states, by giving a construction for classically-instructed remote state preparation for coset states. We also present the first secure copy-protection scheme for point-functions in the plain model, to which our dequantizer can be applied.

The LWE problem is one of the prime candidates for building the most efficient post-quantum secure public key cryptosystems. Many of those schemes, like Kyber, Dilithium or those belonging to the NTRU-family, such as NTRU-HPS, -HRSS, BLISS or GLP, make use of small max norm keys to enhance efficiency. The best attack on these schemes is a hybrid attack, which combines combinatorial techniques and lattice reduction. While lattice reduction is not known to be able to exploit the small max norm choices, May recently showed (Crypto 2021) that such choices allow for more efficient combinatorial attacks.

However, these combinatorial attacks suffer enormous memory requirements, which render them inefficient in realistic attack scenarios and, hence, make their general consideration when assessing security questionable. Therefore, more memory-efficient substitutes for these algorithms are needed. In this work, we provide new combinatorial algorithms for recovering small max norm LWE secrets using only a polynomial amount of memory. We provide analyses of our algorithms for secret key distributions of current NTRU, Kyber and Dilithium variants, showing that our new approach outperforms previous memory-efficient algorithms. For instance, considering uniformly random ternary secrets of length $n$ we improve the best known time complexity for polynomial memory algorithms from $2^{1.063n}$ down-to $2^{0.926n}$. We obtain even larger gains for LWE secrets in $\{-m,\ldots,m\}^n$ with $m=2,3$ as found in Kyber and Dilithium. For example, for uniformly random keys in $\{-2,\ldots,2\}^n$ as is the case for Dilithium we improve the previously best time from $2^{1.742n}$ down-to $2^{1.282n}$.

Our fastest algorithm incorporates various different algorithmic techniques, but at its heart lies a nested collision search procedure inspired by the Nested-Rho technique from Dinur, Dunkelman, Keller and Shamir (Crypto 2016). Additionally, we heavily exploit the representation technique originally introduced in the subset sum context to make our nested approach efficient.

This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security. It reports on a formalization of simulatability in terms of linear algebra properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of erase morphisms. From a theoretical perspective, we shed light into probabilistic definitions of simulatability and matrix-based spectral approaches. This could mean, in practice, that potentially better tools can be built. Readers will find a different, and perhaps less contrived, definition of simulatability, which could enable new forms of reasoning. This work does not cover any practical implementation of the proposed tools, which is left for future work.

The widespread deployment of low-power and handheld devices opens an opportunity to design lightweight authenticated encryption schemes. The schemes so proposed must also prove their resilience under various security notions. Romulus-N1 is an authenticated encryption scheme with associated data based on a tweakable blockcipher, a primary variant of Romulus-N family which is NIST (National Institute of Standards and Technology) lightweight cryptography competition finalist; provides beyond birthday bound security for integrity security in nonce respecting scenario but fails to provide the integrity security in nonce misuse and RUP (release of unverified plaintext) scenarios. In this paper, we propose lynx, a family with $14$ members of 1-pass and rate-1 lightweight authenticated encryption schemes with associated data based on a tweakable blockcipher, that provides birthday bound security for integrity security in both nonce respecting as well as nonce misuse and RUP scenarios and birthday bound security for privacy in nonce respecting scenario. For creating such a family of schemes we propose a family of function $\mathcal{F}$ that provides a total of $72$ cases out of which we show that only $14$ of them can be used for creating authenticated encryption schemes. We provide the implementation of one of the members of lynx family on six different hardware platforms and compare it with Romulus-N1. The comparison clearly shows that the lynx member outperforms Romulus-N1 on all the six platforms.

In this paper we, for the first time, study the question under which circumstances decomposing a round function of a Substitution-Permutation Network is possible uniquely. More precisely, we provide necessary and sufficient criteria for the non-linear layer on when a decomposition is unique. Our results in particular imply that, when cryptographically strong S-boxes are used, the decomposition is indeed unique.

We then apply our findings to the notion of alignment, pointing out that the previous definition allows for primitives that are both aligned and unaligned simultaneously. As a second result, we present experimental data that shows that alignment might only have limited impact. For this, we compare aligned and unaligned versions of the cipher PRESENT.

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In this work we revisit the preimage sampling algorithm proposed by Micciancio and Peikert with different contributions. We first propose a finer analysis of this procedure which results in drastic efficiency gains of up to 50% on the preimage sizes without affecting security. It can thus be used as a drop-in replacement in every construction resorting to it. We then propose a new preimage sampling method which still relies on the trapdoors of Micciancio and Peikert, but that also bridges to the Fiat-Shamir with Aborts signature paradigm by leveraging rejection sampling. It again leads to dramatic gains of up to 75% compared to the original sampling technique. This opens promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. As an application of our new procedure, we give the first lattice-based aggregate signature supporting public aggregation and that achieves relevant compression compared to the concatenation of individual signatures. Our scheme is proven secure in the aggregate chosen-key model coined by Boneh et al. in 2003, based on the well-studied assumptions Module Learning With Errors and Module Short Integer Solution.

GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime $N$ has been found, the only way for another party to independently verify the primality of $N$ used to be by repeating the expensive primality test. To avoid the need for second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime. In this paper, we propose a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can -- parallel to running the primality test for $N$ -- generate an efficiently verifiable proof at a little extra cost certifying that $N$ is not prime. The interactive protocol has statistical soundness and can be made non-interactive using the Fiat-Shamir heuristic.

Our approach is based on a cryptographic primitive called Proof of Exponentiation (PoE) which, for a group $\mathbb{G}$, certifies that a tuple $(x,y,T)\in\mathbb{G}^2\times\mathbb{N}$ satisfies $x^{2^T}=y$ (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol. 2020). In particular, we show how to adapt Pietrzak's PoE at a moderate additional cost to make it a cryptographically-sound certificate of non-primality.

We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm, and show that the heuristic running time is $O(n^{\omega}(C+n)^{1+\varepsilon})$ for lattices of dimension $n$, $\omega\in (2,3]$ bounding the cost of size reduction, matrix multiplication, and QR factorization, and $C$ bounding the log of the condition number of the input basis $B$. This yields a running time of $O\left(n^\omega (p + n)^{1 + \varepsilon}\right)$ for precision $p = O(\log \|B\|_{max})$ in common applications. Our algorithm is fully practical, and we have published our implementation. We experimentally validate our heuristic, give extensive benchmarks against numerous classes of cryptographic lattices, and show that our algorithm significantly outperforms existing implementations.

Cryptography is everywhere in our daily life to ensure the confidentiality and authentication of our communications and the integrity of our records. Although there are strong expectations regarding the security of cryptographic schemes against black-box attackers whose knowledge is restricted to a few inputs or outputs, the security of their implementations is less challenged. However, once implemented on embedded devices, cryptographic schemes become vulnerable to powerful side-channel attacks. The latter additionally exploit the physical leakage (e.g., power consumption) released by the device to recover the manipulated secrets. With cheap equipment, side-channel attacks may yield tremendous damage (e.g., full key recovery) within seconds. Nevertheless, the current security level of countermeasures is not yet close to that achieved in the black-box model.

The community is divided on how to assess the security of cryptographic implementations. From practitioners’ perspective, they need to be confronted with concrete side-channel attacks directly on embedded devices. Conversely, theorists consider that such an empirical approach is not portable and does not yield concrete security levels (e.g., not all attacks can be tested). Therefore, they instead investigate security proofs based on abstract leakage models, although the latter are often too far removed from reality to yield practical security.

The combination of both worlds with a toolbox to generate and verify cryptographic implementations with practical security is the topic of an ERC starting project that is hosted by CryptoExperts. As a member of this project, the candidate will work on the design of new compilers to turn any high-level algorithm into an efficient implementation proven secure for identified concrete devices.

Starting date: around September 2023 (flexible)
Duration: 3 years

Closing date for applications:

Contact: Sonia Belaïd

More information: https://www.cryptoexperts.com/sbelaid/2023_offre-these-erc.pdf

We are seeking an outstanding, highly motivated and enthusiastic PhD student to conduct research related to quantum cyber security. Rapid development of quantum computers poses serious risks to data and communication security. Quantum and post-quantum cryptography technologies provide means to tackle these challenges. In this adventurous experimental PhD project, we will be working on a hybrid solution combining the two technologies.

The successful applicant will be experimentally developing quantum light sources in atomically thin graphene-like materials (Nobel Prize 2010) suitable for quantum communication applications. The PhD student will also be developing hybrid post-quantum secure cryptography protocols based on the experimental outcomes.

The project will involve nanofabrication, optical and electron transport measurements, scanning probe microscopy, instrumentation development and collaborations with academia and industry.

The student will be part of the School of Mathematics, Statistics and Physics with its world-class measurement facilities and cleanrooms, and the Secure and Resilient Systems Research Group part of the accredited centre of excellence in cyber security research, one of only 19 accredited centres of excellence in the UK.

Eligibility Criteria: You must have, or expect to gain, a minimum 2:1 Honours degree or international equivalent in Physics or Materials Science. Solid knowledge of quantum physics and familiarity with Cryptography and Cyber Security are required.

Closing date for applications:

Contact:

Dr Aleksey Kozikov (aleksey.kozikov@newcastle.ac.uk)

Dr Essam Ghadafi (Essam.Ghadafi@newcastle.ac.uk)

More information: https://www.findaphd.com/phds/project/phd-studentship-in-cyber-security-and-resilience-hybrid-quantum-and-post-quantum-technologies-for-security-by-design-solutions/?p155499

Interested in cryptographically assuring the security of computer systems in a post-quantum age?

Confidentiality-preserving security assurance establishes the capacity to certify and prove in security properties of complex system, while keeping details of the system confidential. While the field has advanced in recent years with new digital signature schemes and solution proposals that bind security assurance to underlying hardware attestation, all existing solutions have in common that they can be broken by adversaries with access to a scalable quantum computer. Experts, however, predict that such computing capacity will become available within the next decade. Hence, it will be crucial to establish post-quantum secure confidentiality preserving security assurance.

How can we establish new digital signature schemes that are post-quantum secure and that can realize confidentiality preserving security assurance? What zero-knowledge proof of knowledge techniques will serve us in this environment? How can we prove the security of these schemes with respect to hard mathematical problems secure in face of quantum adversaries?

Applicants should have a strong background in computer science and experience with cryptography. High motivation for independent theoretical/computational work is essential.

Newcastle University Centre of Research Excellence in Cyber Security and Resilience is a cross-faculty environment with 135 members, recognized as a national Academic Centre of Excellence in Cyber Security Research (ACE-CSR). The topic Post-Quantum Secure Confidentiality-Preserving Security Assurance is hosted in the Secure and Resilient Systems Group.

Eligibility Criteria You must have, or expect to gain, a minimum 2:1 Honours degree or international equivalent in a subject relevant to the proposed PhD project (cyber security & resilience, advanced computer science, cryptography). A strong mathematical background is desirable.

Closing date for applications:

Contact:

Prof Thomas Gross (Thomas.gross@newcastle.ac.uk)

Dr Essam Ghadafi (Essam.Ghadafi@newcastle.ac.uk)

More information: https://www.findaphd.com/phds/project/phd-studentship-in-applied-cryptography-post-quantum-secure-confidentiality-preserving-security-assurance/?p155500

We are seeking a highly motivated PhD student to conduct research related to the design of novel provably secure lightweight (hardware-based) cryptographic solutions for authentication and authorization to secure zero-trust networks. The aim is to strengthen security in zero-trust networks by giving devices and users fine-grained control over their resources via designing efficient modular solutions.

You will be part of the Secure and Resilient Systems Research Group part of the accredited centre of excellence in cyber security research, one of only 19 accredited centres of excellence in the UK. You will be working with researchers from both the School of Computing and the School of Engineering.

The supervisory team has strong track records and expertise in cryptography, hardware security, cyber security, and electronic systems design.

You must have, or expect to gain, a minimum 2:1 Honours degree or international equivalent in Computer Science or related subject. Familiarity with and interest in cryptography and cyber security is required.

Closing date for applications:

Contact: Dr Essam Ghadafi (Essam.Ghadafi@newcastle.ac.uk)

More information: https://www.findaphd.com/phds/project/phd-studentship-in-cyber-security-and-resilience-fine-grained-provably-secure-authentication-and-authorization-for-zero-trust-networks/?p155495

We’re looking for a Senior / Cryptographic Engineer to develop and deliver cryptographic engineering solutions for communications protocols of quantum secured communication products. Reporting to the Chief Applications Officer, the Senior / Cryptographic Engineer’s main responsibilities will be: Work with the applications team to design and evaluate modification of existing communications protocols to provide robust security against the threat of quantum computers. Support the team to develop proof of concept implementations that can be evaluated with KETS’ trusted client base. Contribute to the wider cyber security culture within KETS. Design and evaluate modifications to common layer 2/3 communication protocols (e.g. MACsec, MPLS) to incorporate quantum-safe cryptographic primitives. Collaborating with your team to develop prototype implementations of quantum-safe communications protocols. Produce technical design specifications and documentation. Deliver research papers & patents where appropriate. Engage with the wider community (conferences, industry seminars, standards bodies) where appropriate. Supporting the wider team in implementing best practice for secure software development.

Closing date for applications:

Contact: careers@kets-quantum.com

More information: https://ketsquantum.livevacancies.co.uk/#/job/details/29?target=frame

We study certified everlasting secure functional encryption (FE) and many other cryptographic primitives in this work. Certified everlasting security roughly means the following. A receiver possessing a quantum cryptographic object (such as ciphertext) can issue a certificate showing that the receiver has deleted the cryptographic object and information included in the object (such as plaintext) was lost. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded after the deletion. Many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. Hence, certified everlasting security is a nice compromise (intrinsic to quantum).

In this work, we define certified everlasting secure versions of FE, compute-and-compare obfuscation, predicate encryption (PE), secret-key encryption (SKE), public-key encryption (PKE), receiver non-committing encryption (RNCE), and garbled circuits. We also present the following constructions:

- Adaptively certified everlasting secure collusion-resistant public-key FE for all polynomial-size circuits from indistinguishability obfuscation and one-way functions.

- Adaptively certified everlasting secure bounded collusion-resistant public-key FE for $\mathsf{NC}^1$ circuits from standard PKE.

- Certified everlasting secure compute-and-compare obfuscation from standard fully homomorphic encryption and standard compute-and-compare obfuscation

- Adaptively (resp., selectively) certified everlasting secure PE from standard adaptively (resp., selectively) secure attribute-based encryption and certified everlasting secure compute-and-compare obfuscation. - Certified everlasting secure SKE and PKE from standard SKE and PKE, respectively.

- Certified everlasting secure RNCE from standard PKE.

- Certified everlasting secure garbled circuits from standard SKE.