International Association
for Cryptologic Research

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.

Machine Learning (ML) is almost ubiquitously used in multiple disciplines nowadays. Recently, we have seen its usage in the realm of differential distinguishers for symmetric key ciphers. In this work, we explore the possibility of a number of ciphers with respect to various ML-based distinguishers.

We show new distinguishers on the unkeyed and round reduced version of SPECK-32, SPECK-128, ASCON, SIMECK-32, SIMECK-64 and SKINNY-128. We explore multiple avenues in the process. In summary, we use neural network as well as support vector machine in various settings (such as varying the activation function), apart from experimenting with a number of input difference tuples. Among other results, we show a distinguisher of 8-round SPECK-32 that works with practical data complexity (most of the experiments take a few hours on a personal computer).

A private puncturable pseudorandom function (PRF) enables one to create a constrained version of a PRF key, which can be used to evaluate the PRF at all but some punctured points. In addition, the constrained key reveals no information about the punctured points and the PRF values on them. Existing constructions of private puncturable PRFs are only proven to be secure against a restricted adversary that must commit to the punctured points before viewing any information. It is an open problem to achieve the more natural adaptive security, where the adversary can make all its choices on-the-fly.

In this work, we solve the problem by constructing an adaptively secure private puncturable PRF from standard lattice assumptions. To achieve this goal, we present a new primitive called explainable hash, which allows one to reprogram the hash function on a given input. The new primitive may find further applications in constructing more cryptographic schemes with adaptive security. Besides, our construction has collusion resistant pseudorandomness, which requires that even given multiple constrained keys, no one could learn the values of the PRF at the punctured points. Private puncturable PRFs with collusion resistant pseudorandomness were only known from multilinear maps or indistinguishability obfuscations in previous works, and we provide the first solution from standard lattice assumptions.

Unconditionally secure broadcast is feasible among parties connected by pairwise secure links only if there is a strict two-thirds majority of honest parties when no additional resources are available. This limitation may be circumvented when the parties have recourse to additional resources such as correlated randomness. Fitzi, Wolf, and Wullschleger (CRYPTO 2004) attempted to characterize the conditions on correlated randomness shared among three parties which would enable them to realize broadcast. Due to a gap in their impossibility argument, it turns out that their characterization is incorrect. Using a novel construction we show that broadcast is feasible under a considerably larger class of correlations. In fact, we realize pseudo-signatures, which are information theoretic counterparts of digital signatures using which unconditionally secure broadcast may be obtained. We also obtain a matching impossibility result thereby characterizing the class of correlations on which three-party broadcast (and pseudo-signatures) can be based. Our impossibility proof, which extends the well-know argument of Fischer, Lynch and Merritt (Distr. Comp., 1986) to the case where parties observe correlated randomness, maybe of independent interest.

Partially Oblivious Pseudorandom Functions (POPRFs) are 2-party protocols that allow a client to learn pseudorandom function (PRF) evaluations on inputs of its choice from a server. The client submits two inputs, one public and one private. The security properties ensure that the server cannot learn the private input and the client cannot learn more than one evaluation per POPRF query. POPRFs have many applications including password-based key exchange and privacy-preserving authentication mechanisms. However, most constructions are based on classical assumptions and those with post-quantum security suffer from large efficiency drawbacks.

In this work, we construct a novel POPRF from lattice assumptions and the "Crypto Dark Matter" PRF candidate (TCC'18) in the random oracle model. At a conceptual level, our scheme exploits the alignment of this family of PRF candidates, relying on mixed modulus computations, and programmable bootstrapping in the "3rd gen" torus-fully homomorphic encryption scheme (TFHE). We show that our construction achieves malicious client security based on circuit-private FHE, and client privacy from the semantic security of the FHE scheme. We further explore a heuristic approach to extend our scheme to support verifiability based on the difficulty of computing cheating circuits in low depth. This would yield a verifiable (P)OPRF. We provide a proof-of-concept implementation and benchmarks of our construction using the "Concrete" TFHE software library. For the core online OPRF functionality, client operations take only a few milliseconds, while server evaluation takes less than 3 seconds.

Homomorphic Encryption~(HE) is used in many fields including information storage, data protection, privacy preservation, blockchain, and authentication. HE allows an untrusted third party to perform algebraic operations on encrypted data. Protecting the results of HE against accidental or malicious tampering attacks is still an open research challenge. In this paper, we introduce a lightweight technique that allows a data owner to verify the integrity of HE results performed in the cloud. The proposed method is quick, simple, and applicable, as it depends on adding a single digit to the encrypted message before storing it in the cloud. This digit represents verification proof and it is later used to ensure a verifiable HE. Our technique can be integrated with any HE scheme that uses encryption with non-isolated plaintext.

Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons. Originally suggested by Abdalla and Bellare, there are several proposals on how to perform this internal re-keying mechanism. For example, Liliya et al. offered the CryptoPro Key Meshing (CPKM) to be used together with GOST 28147-89 (known as the GOST block cipher). Later, ISO and the IETF adopted the Advanced CryptoPro Key Meshing (ACKPM) in ISO 10116 and RFC 8645, respectively. In this paper, we study the security of ACPKM and CPKM. We show that the internal re-keying suffers from an entropy loss in successive repetitions of the re- keying mechanism. We show some attacks based on this issue. The most prominent one has time and data complexities of $O(2^{\kappa/2} )$ and success rate of $O(2^{−\kappa/4} )$ for a $\kappa$-bit key. Furthermore, we show that a malicious block cipher designer or a faulty implementation can exploit the ACPKM (or the original CPKM) mechanism to significantly hinder the security of a protocol employing ACPKM (or CPKM). Namely, we show that in such cases, the entropy of the re-keyed key can be greatly reduced.

The no-cloning principle of quantum mechanics enables us to achieve amazing unclonable cryptographic primitives, which is impossible in classical cryptography. However, the security definitions for unclonable cryptography are tricky. Achieving desirable security notions for unclonability is a challenging task. In particular, there is no indistinguishable-secure unclonable encryption and quantum copy-protection for single-bit output point functions in the standard model. To tackle this problem, we introduce and study relaxed but meaningful security notions for unclonable cryptography in this work. We call the new security notion one-out-of-many unclonable security.

We obtain the following results. - We show that one-time strong anti-piracy secure secret key single-decryptor encryption (SDE) implies one-out-of-many indistinguishable-secure unclonable encryption. - We construct a one-time strong anti-piracy secure secret key SDE scheme in the standard model from the LWE assumption. - We construct one-out-of-many copy-protection for single-bit output point functions from one-out-of-many indistinguishable-secure unclonable encryption and the LWE assumption. - We construct one-out-of-many unclonable predicate encryption (PE) from one-out-of-many indistinguishable-secure unclonable encryption and the LWE assumption.

Thus, we obtain one-out-of-many indistinguishable-secure unclonable encryption, one-out-of-many copy-protection for single-bit output point functions, and one-out-of-many unclonable PE in the standard model from the LWE assumption. In addition, our one-time SDE scheme is the first SDE scheme that does not rely on any oracle heuristics and strong assumptions such as indistinguishability obfuscation and witness encryption.

Current messaging protocols are incapable of detecting active man-in-the-middle threats. Even common continuous key agreement protocols such as Signal, which offers forward secrecy and post-compromise security, are dependent on the adversary being passive immediately following state compromise, and healing guarantees are lost if the attacker is not. This work offers the first solution for detecting active man-in-the-middle attacks on such protocols by extending authentication beyond the initial public keys and binding it to the entire continuous key agreement. In this, any adversarial fork is identifiable to the protocol participants. We provide a modular construction generic for application with any continuous key agreement protocol, a specific construction for application to Signal, and security analysis. The modularity of our solution enables it to be seamlessly adopted by any continuous key agreement protocol.

The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space.

In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In our model, the existence of IDs can be directly obtained by checking whether the model has a solution. In addition, our tool can also detect any contradictions between input and output differences by changing the position of the contradictions. Our method is confirmed by applying it to several block ciphers, and our results show that we can find 6-, 13-, and 12-round IDs for Midori-64, CRAFT, and SKINNY-64 within a few seconds, respectively. Moreover, by carefully analyzing the key schedule of Midori-64, we propose an equivalent key transform technique and construct a complete MILP model for an 11-round impossible differential attack (IDA) on Midori-64 to search for the minimum number of keys to be guessed. Based on our automatic technique, we present a new 11-round IDA on Midori-64, where 23 nibbles of keys need to be guessed, which reduces the time complexity compared to previous work. The time and data complexity of our attack are $2^{116.59}$ and $2^{60}$, respectively. To the best of our knowledge, this is the best IDA on Midori-64 at present.

Virtually all modern blockciphers are iterated. In this paper, we ask: to construct a secure iterated blockcipher "non-trivially", how many calls to random functions and permutations are necessary?

When security means indistinguishability from a random permutation, optimality is achieved by the Even-Mansour scheme using 1 call to a public permutation. We seek for the arguably strongest security indifferentiability from an ideal cipher, a notion introduced by Maurer et al. (TCC 2004) and popularized by Coron et al. (JoC, 2014).

We provide the first generic negative result/lower bounds: when the key is not too short, no iterated blockcipher making 3 calls is (statistically) indifferentiable. This proves optimality for a 4-call positive result of Guo et al. (Eprint 2016). Furthermore, using 1 or 2 calls, even indifferentiable iterated blockciphers with polynomial keyspace are impossible.

To prove this, we develop an abstraction of idealized iterated blockciphers and establish various basic properties, and apply Extremal Graph Theory results to prove the existence of certain (generalized) non-random properties such as the boomerang and yoyo.

An oblivious pseudorandom function, or OPRF, is an important primitive that is used to build many advanced cryptographic protocols. Despite its relevance, very few post-quantum solutions exist.

In this work, we propose a novel OPRF protocol that is post-quantum, verifiable, round-optimal, and moderately compact. Our protocol is based on a previous SIDH-based construction by Boneh, Kogan, and Woo, which was later shown to be insecure due to an attack on its one-more unpredictability. We first propose an efficient countermeasure against this attack by redefining the PRF function to use irrational isogenies. This prevents a malicious user from independently evaluating the PRF. The SIDH-based construction by Boneh, Kogan, and Woo is also vulnerable to the recent attacks on SIDH. We thus demonstrate how to efficiently incorporate the countermeasures against such attacks to obtain a secure OPRF protocol. To achieve this, we also propose the first proof of isogeny knowledge that is compatible with masked torsion points, which may be of independent interest. Lastly, we design a novel non-interactive proof of knowledge of parallel isogenies, which reduces the number of communication rounds of the OPRF to the theoretically-optimal two. Putting everything together, we obtain the most compact post-quantum verifiable OPRF protocol.

Falcon is one of the three post-quantum signature schemes selected for standardization by NIST. Due to its low bandwidth and high efficiency, Falcon is seen as an attractive option for quantum-safe embedded systems. In this work, we study Falcon's side-channel resistance by analysing its Gaussian samplers. Our results are mainly twofold.

The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. (CHES 2022). Instead of resorting to the fourth moment as in former parallelepiped-learning attacks, we work with the second order statistics covariance and use its spectral decomposition to recover the secret information. Our approach substantially reduces the requirement for measurements and computation resources: $220\,000$ traces is sufficient to recover the secret key of Falcon 512 within half an hour with a probability of $\approx 25\%$. As a comparison, even with $10^6$ traces, the former attack still needs about 1000 hours CPU time of lattice reduction for a full key recovery. In addition, our approach is robust to inaccurate leakage classification, which is another advantage over parallelepiped-learning attacks.

Our second result is a practical power analysis targeting the integer Gaussian sampler of Falcon. The analysis relies on the leakage of random sign flip within the integer Gaussian sampling. This leakage was exposed in 2018 by Kim and Hong, but it is not considered in Falcon's implementation and unexploited for side channel analysis until now. We identify the leakage within the reference implementation of Falcon on an ARM Cortex-M4 STM32F407IGT6 microprocessor. We also show that this single bit of leakage is in effect enough for practical key recovery: with $170\,000$ traces one can fully recover the key of Falcon-512 within half an hour. Furthermore, combining the sign leakage and the aforementioned leakage, one can recover the key with only $45\,000$ signature measurements in a short time.

As a by-product, we also extend our power analysis to Mitaka which is a recent variant of Falcon. The same leakages exist within the integer Gaussian samplers of Mitaka, and they can also be used to mount key recovery attacks. Nevertheless, the key recovery in Mitaka requires much more traces than it does in Falcon, due to their different lattice Gaussian samplers.

Verifiable random functions (VRFs) are essentially pseudorandom functions for which selected outputs can be proved correct and unique, without compromising the security of other outputs. VRFs have numerous applications across cryptography, and in particular they have recently been used to implement committee selection in the Algorand protocol.

Elliptic Curve VRF (ECVRF) is an elegant construction, originally due to Papadopoulos et al., that is now under consideration by the Internet Research Task Force. Prior work proved that ECVRF possesses the main desired security properties of a VRF, under suitable assumptions. However, several recent versions of ECVRF include changes that make some of these proofs inapplicable. Moreover, the prior analysis holds only for *classical* attackers, in the random-oracle model (ROM); it says nothing about whether any of the desired properties hold against *quantum* attacks, in the quantumly accessible ROM. We note that certain important properties of ECVRF, like uniqueness, do *not* rely on assumptions that are known to be broken by quantum computers, so it is plausible that these properties could hold even in the quantum setting.

This work provides a multi-faceted security analysis of recent versions of ECVRF, in both the classical and quantum settings. First, we motivate and formally define new security properties for VRFs, like non-malleability and binding, and prove that recent versions of ECVRF satisfy them (under standard assumptions). Second, we identify a subtle obstruction in proving that recent versions of ECVRF have *uniqueness* via prior indifferentiability definitions and theorems, even in the classical setting. Third, we fill this gap by defining a stronger notion called *relative indifferentiability*, and extend prior work to show that a standard domain extender used in ECVRF satisfies this notion, in both the classical and quantum settings. This final contribution is of independent interest and we believe it should be applicable elsewhere.