International Association
for Cryptologic Research

This study proposes a chosen-ciphertext side-channel attack against a lattice-based key encapsulation mechanism (KEM), the third-round candidate of the national institute of standards and technology (NIST) standardization project. Unlike existing attacks that target operations such as inverse NTT and message encoding/decoding, we target Barrett Reduction in the decapsulation phase of CRYSTALS-KYBER to obtain a secret key. We show that a sensitive variable-dependent leakage of Barrett Reduction exposes an entire secret key. The results of experiments conducted on the ARM Cortex-M4 microcontroller accomplish a success rate of 100%. We only need six chosen ciphertexts for KYBER512 and KYBER768 and eight chosen ciphertexts for KYBER1024. We also show that the m4 scheme of the pqm4 library, an implementation with the ARM Cortex-M4 specific optimization (typically in assembly), is vulnerable to the proposed attack. In this scheme, six, nine, and twelve chosen ciphertexts are required for KYBER512, KYBER768, and KYBER1024, respectively.

OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and near-optimal computational performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise.

In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an UNauthenticated Diffie-Hellman exchange. KHAPE uses three messages if the server initiates the exchange or four when the client does (one more than OPAQUE in the latter case).

All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of key-hiding AKE which KHAPE uses as a main component as well as our UC proofs of AKE security for protocols 3DH (a basis of Signal), HMQV and SKEME, that we use as efficient instantiations of KHAPE.

We introduce a new key generation mechanism where users can generate a ``back up key'', securely nested inside the secret key of a signature scheme.

Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the ``back up key'', which is secret, can be used to generate a ``proof of ownership'', i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of ``Proof of Ownership'' and ``Fallback'' as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a $\mbox{W-OTS}^{+}$ signing key as a ``back up key''. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to $\mbox{W-OTS}^{+}$. Finally, we briefly discuss the construction of multiple generations of proofs of ownership.

Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted in a court for violating its service agreement with Alice. Bob is one of the servers and sees this advertisement. On examining the collection scheme closely, Bob concludes that there is no way for Alice to prove anything in a court that he submitted his share. Indeed, if Bob is rational, he might use the cryptographic scheme in the advertisement and submit his share since there are no penalties and no fear of being caught and prosecuted. Can we design a secret sharing scheme which Alice can use to avoid such a scenario?

We introduce a new primitive called as Traceable Secret Sharing to tackle this problem. In particular, a traceable secret sharing scheme guarantees that a cheating server always runs the risk of getting traced and prosecuted by providing a valid evidence (which can be examined in a court of law) implicating its dishonest behavior. We explore various definitional aspects and show how they are highly non-trivial to construct (even ignoring efficiency aspects). We then give an efficient construction of traceable secret sharing assuming the existence of a secure two-party computation protocol. We also show an application of this primitive in constructing traceable protocols for multi-server delegation of computation.

Your Tasks: • Specification of innovative and disruptive crypto & security solutions • Definition of crypto & security algorithms and related IP architectures • Definition of advanced crypto protocols • Definition of crypto & security mechanisms in hardware, firmware, etc. • Specification and review of crypto & security architectures • Detailed attack modeling and security mechanism specification for hardware and software blocks • Advising and training the product and IP teams on design, implementation and test • Root cause analysis of security defects • Technical interface to customers, evaluation labs and to the product development team • Certification support and technical interface with evaluator and certifier Your Profile: • Have a PhD/Master in Cryptography, Security or Mathematics • Very good knowledge of cryptography (incl. symmetric and asymmetric crypto) • Very good knowledge of discrete mathematics, algebra and number theory • Good knowledge of SoCs and/or Secure Element products • Good knowledge of crypto hardware implementation • Strong security background • Have >5 years of experience in embedded security • Used to an independent working style • Be willing to listen and to adapt • Very good communication skills • Be willing to travel

Closing date for applications:

Contact: Ulrich Althen

More information: https://nxp.wd3.myworkdayjobs.com/careers/job/Gratkorn/Principal-Cryptographer--m-f-d-_R-10028227

Event date: 17 December to 19 December 2021
Submission deadline: 8 August 2021
Notification: 12 September 2021

Closing Date 5th September 2021

The Department of Computer Science at the University of Surrey is seeking to appoint two Lecturers / Senior Lecturers in Cyber Security to strengthen its research within the Surrey Centre for Cyber Security (SCCS) and to support the Department’s ambitious strategic growth in this area. The appointments are on a full-time and permanent basis.

Of particular interest are the following research areas: applied cryptography, privacy enhancing technologies (incl. anonymisation, secure multi-party computation, computing on encrypted data), software security (e.g., malware analysis), system security (incl., security of autonomous or cyber-physical systems), security architectures (incl., trusted computing, TEEs), security protocols for blockchain and/or machine learning, or tool-assisted formal verification of security and privacy.

The Department of Computer Science has a world-class reputation in cyber security and regularly publishes at top-tier conferences and journals. The Department is home to Surrey Centre for Cyber Security (SCCS) and Surrey is only one of four institutions in the UK holding recognition from the National Cyber Security Centre as an Academic Centre of Excellence in both Cyber Security Research and in Cyber Security Education (Gold).

SCCS maintains close links with leading industries, the public sector and governmental bodies, leading to a strong heritage of real-world impact. The Department has made significant investment in its facilities with a new 200-seater computer science teaching laboratory, a virtual cloud computing platform, a secure systems facility and an HPC cluster for research.

We are interested in outstanding candidates with a strong record of publications in top-tier cyber security venues and, in particular for the Senior Lecturer post, with an established network of international collaborators from academia and/or industry and experience in attracting sustainable research funding.

Closing date for applications:

Contact:
Head of Department: Dr Mark Manulis (m.manulis@surrey.ac.uk).
Director of SCCS: Prof Steve Schneider (s.schneider@surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=027721

A few research scientist positions are available at the Institute for Infocomm Research (I2R), A*STAR, Singapore. We are looking for capable and responsible scientists to work on and contribute to collaborative/federated/split/multi-party learning (data valuation, privacy, black-box and white-box models, etc.), machine learning, etc. Candidates with experience in privacy-preserving technologies (homomorphic encryption, MPC, differential privacy, etc.) in machine learning, particularly on secure algorithm/protocol design, are preferred. Successful candidates will work with a team to conduct R&D on applications and domains using a secure collaboration learning framework and time-series data. They will also have opportunities to work with local and international collaborators in academia. To apply for the position, please click on the link https://careers.a-star.edu.sg/jobdetails.aspx?ID=4147

Closing date for applications:

Contact: Singee

More information: https://careers.a-star.edu.sg/jobdetails.aspx?ID=4147

Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.

While privacy preserving distributed payment schemes manage to drastically improve user privacy, they come at the cost of generating new regulatory concerns: in a private ledger the transactions cannot be subject to any level of auditing, and thus are not compatible with tracing illegal behaviors. In this work we present MiniLedger, a distributed payment system which not only guarantees the privacy of transactions, but also offers built-in functionalities for various types of audits by any external authority. MiniLedger is the first private and auditable payment system with storage costs independent of the number of transactions. To achieve such a storage improvement, we introduce pruning functionalities for the transaction history while maintaining integrity and auditing. We provide formal security definitions and a number of extensions for various auditing levels. Our evaluation results show that MiniLedger is practical in terms of storage requiring as low as 70KB per participant for 128 bits of security, and depending on the implementation choices, can prune 1 million transactions in less than a second.

Efficient implementation of Boolean masking in terms of low latency has evolved into a hot topic due to the necessity of embedding a physically secure and at-the-same-time fast implementation of cryptographic primitives in e.g., the memory encryption of pervasive devices. Instead of fully minimizing the circuit's area and randomness requirements at the cost of latency, the focus has changed into finding optimal tradeoffs between the circuit area and the execution time. The main latency bottleneck in hardware masking lies in the need for registers to stop the propagation of glitches and maintain non-completeness. Usually, an exponentially growing number of shares (hence an extremely large circuit), as well as a high demand for fresh randomness, are the result of avoiding registers in a securely masked hardware implementation of a block cipher. In this paper, we present several first-order secure and low-latency implementations of PRINCE. In particular, we show how to realize the masked variant of round-based PRINCE with only a single register stage per cipher round. We compare the resulting architectures, based on the popular TI and GLM masking scheme based on the area, latency, and randomness requirements and point out that both designs are suited for specific use cases.

This paper revisits Key-Policy Attribute-Based Encryption, allowing the delegation of keys, traceability of compromised keys and key anonymity, as additional properties. Whereas delegation of rights has been addressed in the seminal paper by Goyal et al? in 2006, introducing KPABE, this nice feature has almost been neglected in all subsequent works in favor of better security levels. However, in multi-device scenarios, this is quite important to allow users to independently authorize their own devices, still with some tracing capabilities and some anonymity properties.

To this aim, we define a new primitive with switchable attributes, in both the ciphertexts and the keys, and new indistinguishability properties. We then provide concrete and efficient instantiations with adaptive security under the sole SXDH assumption in the standard model.

The one more-discrete logarithm assumption (OMDL) underlies the security analysis of identification protocols, blind signature and multi-signature schemes, such as blind Schnorr signatures and the recent MuSig2 multi-signatures. As these schemes produce standard Schnorr signatures, they are compatible with existing systems, e.g. in the context of blockchains. OMDL is moreover assumed for many results on the impossibility of certain security reductions.

Despite its wide use, surprisingly, OMDL is lacking any rigorous analysis; there is not even a proof that it holds in the generic group model (GGM). (We show that a claimed proof is flawed.) In this work we give a formal proof of OMDL in the GGM. We also prove a related assumption, the one-more computational Diffie-Hellman assumption, in the GGM. Our proofs deviate from prior proofs in the GGM and replace the use of the Schwartz-Zippel Lemma by a new argument.

Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from $\{-1, 0, 1\}$, is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP.

In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE.

When expressed in terms of the search space $\mathcal{S}$ for LWE keys, the asymptotic complexity of the representation attack drops from $\mathcal{S}^{0.24}$ (classical) down to $\mathcal{S}^{0.19}$ (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS and NTRU Prime. Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.

We build the first construction of a partially oblivious pseudorandom function (POPRF) that does not rely on bilinear pairings. Our construction can be viewed as combining elements of the 2HashDH OPRF of Jarecki, Kiayias, and Krawczyk with the Dodis-Yampolskiy PRF. We analyze our POPRF's security in the random oracle model via reduction to a new one-more gap strong Diffie-Hellman inversion assumption. The most significant technical challenge is establishing confidence in the new assumption, which requires new proof techniques that enable us to show that its hardness is implied by the $q$-DL assumption in the algebraic group model.

Our new construction is as fast as the current, standards-track OPRF 2HashDH protocol, yet provides a new degree of flexibility useful in a variety of applications. We show how POPRFs can be used to prevent token hoarding attacks against Privacy Pass, reduce key management complexity in the OPAQUE password authenticated key exchange protocol, and ensure stronger security for password breach alerting services.

We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel.

Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems.

Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by Bader et al. (TCC 2015). We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.

In this work we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public-key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing rerandomizable RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek's scheme (which was the first construction of rerandomizable RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of rerandomizable RCCA-secure encryption.

With the development of side-channel attacks, a necessity arises to invent authenticated key exchange protocols in a leakage-resilient manner. Constructing authenticated key exchange protocols using existing cryptographic schemes is an effective method, as such construction can be instantiated with any appropriate scheme in a way that the formal security argument remains valid. In parallel, constructing authenticated key exchange protocols that are proven to be secure in the standard model is more preferred as they rely on real-world assumptions. In this paper, we present a Diffie-Hellman-style construction of a leakage-resilient authenticated key exchange protocol, that can be instantiated with any CCLA2-secure public-key encryption scheme and a function from the pseudo-random function family. Our protocol is proven to be secure in the standard model assuming the hardness of the decisional Diffie-Hellman problem. Furthermore, it is resilient to continuous partial leakage of long-term secret keys, that happens even after the session key is established, while satisfying the security features defined by the eCK security model.

We introduce a novel method for reducing an arbitrary $\delta$-noisy leakage function to a collection of $\epsilon$-random probing leakages. These reductions combined with linear algebra tools are utilized to study the security of linear Boolean masked circuits in a practical and concrete setting. The secret recovery probability (SRP) that measures an adversary's ability to obtain secrets of a masked circuit is used to quantify the security. Leakage data and the parity-check relations imposed by the algorithm's structure are employed to estimate the SRP

Both the reduction method and the SRP metric were used in the previous works. Here, as our main contribution, the SRP evaluation task is decomposed from the given $\mathbb{F}_q$ field to $q-1$ different binary systems indexed with $i$. Where for the $i$th system, the equivalent $\delta_i$-noisy leakage is reduced optimally to a $\epsilon_i$-random probing leakage with $\epsilon_i=2\delta_i$. Each binary system is targeting a particular bit-composition of the secret. The $q-1$ derived $\delta_i\leq \delta$ values are shown to be a good measure for the informativeness of the given $\delta$-noisy leakage function.

Our works here can be considered as an extension of the work of TCC 2016. There, only $ \delta$-noisy leakage from the shares of a secret was considered. Here, we also incorporate the leakages that are introduced by the computations over the shares.

We study masked implementation's security when an adversary randomly probes each of its internal variables, intending to recover non-trivial knowledge about its secrets. We introduce a novel metric called Secret Recovery Probability (SRP) for assessing the informativeness of the probing leakages about the masked secrets. To evaluate SRP, our starting point is to describe the relations of the intermediate variables with a parity equation system where the target secret is an unknown of this system ...