International Association
for Cryptologic Research

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: SPIX and SpoC. We improve the number of rounds with respect to the previously known best results. We improve the techniques used for solving the inbound part and we relax the output conditions in order to extend the previous attacks.

The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

We propose a generic construction of 2-pass authenticated key exchange (AKE) scheme with explicit authentication from key encapsulation mechanism (KEM) and signature (SIG) schemes. We improve the security model due to Gjosteen and Jager [Crypto2018] to a stronger one. In the strong model, if a replayed message is accepted by some user, the authentication of AKE is broken. We define a new security notion named ''IND-mCPA with adaptive reveals'' for KEM. When the underlying KEM has such a security and SIG has unforgeability with adaptive corruptions, our construction of AKE equipped with counters as states is secure in the strong model, and stateless AKE without counter is secure in the traditional model. We also present a KEM possessing tight ''IND-mCPA security with adaptive reveals'' from the Computation Diffie-Hellman assumption in the random oracle model. When the generic construction of AKE is instantiated with the KEM and the available SIG by Gjosteen and Jager [Crypto2018], we obtain the first practical 2-pass AKE with tight security and explicit authentication. In addition, the integration of the tightly IND-mCCA secure KEM (derived from PKE by Han et al. [Crypto2019]) and the tightly secure SIG by Bader et al. [TCC2015] results in the first tightly secure 2-pass AKE with explicit authentication in the standard model.

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth.

In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (ePrint, 2020). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters' sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the $k$-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.'s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.'s scheme in the sense of the sizes of master public/secret keys.

The Department of Computer Science at the University of Surrey is seeking to recruit a full-time researcher to the Surrey Centre for Cyber Security.

The successful candidate will work on cyber security for Decentralisation in the Digital Economy through technologies such as Distributed Ledgers, and with a focus on self-sovereign identity and the human focused aspects of cyber security.

The project will concentrate on developing protocols and architectures for cyber security in decentralized systems for content provenance and content brokering, the initial scenarios to be considered by the project, and builds on Surrey’s previous work on Distributed Ledger Technologies. The project is within the new multidisciplinary and collaborative EPSRC DE Centre in the Decentralised Digital Economy led by Surrey.

The Department of Computer Science within the Faculty of Engineering and Physical Sciences has an international reputation for research and teaching. Security research in the department is focused within the Surrey Centre for Cyber Security, with Surrey recognized by the National Cyber Security Centre as an Academic Centre of Excellence in Cyber Security Research. Our research concentrates on protocol analysis, security verification, trusted computing, data privacy, access control, privacy preserving security, cryptography, distributed ledger technologies, digital forensics and human-centred computing.

The position offers the platform for the research fellow to work within a group and develop skills to become an independent researcher. The successful candidate will work under the direction of Professor Steve Schneider. The project is also collaborative with other Surrey research centres, with the University of Edinburgh and with the Digital Catapult.

We are looking for applicants that demonstrate strong research and analytical skills, have strong communication skills and enthusiasm for developing their own research ideas. Applicants should also have skills in software engineering for web applications, and an understanding of cyber security. Knowledge of Distributed Ledger Technologies would be an advantage

Closing date for applications:

Contact: Professor Steve Schneider: s.schneider@surrey.ac.uk

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

The 2020 TCC Test-of-Time Award goes to  Zuzana Trubini and Martin Hirt, for their TCC 2008 paper "Perfectly-Secure MPC with Linear Communication Complexity ". 

The award committee recognizes this paper “for introducing hyper-invertible matrices to perfectly secure multiparty computation, thus enabling significant efficiency improvements and, eventually, constructions with minimal communication complexity." 

The TCC Test of Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other areas of cryptography, theory, and beyond. The inaugural TCC Test of Time Award was given in TCC 2015 for papers published no later than TCC 2007.

In 2013, Tao et al. introduced the ABC Simple Matrix Encryption Scheme, a multivariate public key encryption scheme. The scheme boasts great efficiency in encryption and decryption, though it suffers from very large public keys. It was quickly noted that the original proposal, utilizing square matrices, suffered from a very bad decryption failure rate. As a consequence, the designers later published updated parameters, replacing the square matrices with rectangular matrices and altering other parameters to avoid the cryptanalysis of the original scheme presented in 2014 by Moody et al.

In this work, we show that making the matrices rectangular, while decreasing the decryption failure rate, actually, and ironically, diminishes security. We show that the combinatorial rank methods employed in the original attack of Moody et al. can be enhanced by the same added degrees of freedom that reduce the decryption failure rate. Moreover, and quite interestingly, if the decryption failure rate is still reasonably high, as exhibited by the proposed parameters, we are able to mount a reaction attack to further enhance the combinatorial rank methods. To our knowledge this is the first instance of a reaction attack creating a significant advantage in this context.

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with an attribute vector and a receiver holding a secret-key associated to a predicate vector can recover the message from the ciphertext if the inner product between the attribute and predicate vectors is non-zero. The main focus is to hide messages in most of the existing NIPEs and the associated attribute is trivially included in the ciphertext. In this work, we investigate the design of NIPEs that are capable of hiding attributes along with messages and secure against active adversaries. In particular, we describe a generic ransformation of an attribute-hiding chosen-ciphertext attack (CCA) secure NIPE from an inner product functional encryption (IPFE) and a quasi-adaptive non-interactive zero-knowledge (QANIZK) proof system. This leads us to a set of attribute-hiding NIPEs (AHNIPE) with security based on several assumptions such as plain Decisional Diffie-Hellman (DDH), Learning With Errors (LWE) and Decision Composite Reciprocity (DCR). Furthermore, we build a more efficient and concrete construction of a CCA secure AHNIPE the security of which can be based on DDH and Kernel Matrix Diffie-Hellman (KerMDH) assumptions. As DDH implies the computational KerMDH assumption, the latter construction achieves a CCA secure AHNIPE from minimal assumption to date. We explore a few applications of AHNIPE. More specifically, we show that AHNIPE directly implies an anonymous identity-based revocation (IBR) scheme. Consequently, we get the first CCA secure IBR solely based on plain DDH assumption in the standard model, improving the security of any previous anonymous CCA secure IBR scheme which is proven secure relying on pairing-based assumptions in the random oracle model. Moreover, we add a tracing algorithm to our anonymous IBR scheme to convert it into an efficient anonymous trace and revoked scheme with CCA security.

Chameleon-hashes are collision-resistant hash-functions parametrized by a public key. If the corresponding secret key is known, arbitrary collisions for the hash can be found. Recently, Derler et al. (PKC '20) introduced the notion of fully collision-resistant chameleon-hashes. Full collision-resistance requires the intractability of finding collisions, even with full-adaptive access to a collision-finding oracle. Their construction combines simulation-sound extractable (SSE) NIZKs with perfectly correct IND-CPA secure public-key encryption (PKE) schemes.

We show that, instead of perfectly correct PKE, non-interactive commitment schemes are sufficient. For the first time, this gives rise to efficient instantiations from plausible post-quantum assumptions and thus candidates of chameleon-hashes with strong collision-resistance guarantees and long-term security guarantees. On the more theoretical side, our results relax the requirement to not being dependent on public-key encryption.

Event date: 11 December 2020
Submission deadline: 2 October 2020
Notification: 23 October 2020

**Senior Cryptography Researchers have a responsibility to help grow NCC Group Cryptography Services. They will be key contributors to project delivery and research (we have an entire division dedicated to Research and your bonus includes doing research during company hours) at NCC Group Cryptography Services. **Activities and Responsibilities (include): • Delivery of consultancy projects within Cryptography Services • Research and tool development in Cryptography Services • External delivery of client-facing and public speaking events in Cryptography Services • Assistance with sales support for Cryptography Services • Mentoring and leadership for staff at NCC Group **Skills and Experience: Blockchain Security experience is a requirement. The amount of experience with this is flexible. Minimum of five (5) years of experience in Cryptography disciplines with focus areas including some of the following: • Cryptographic Analysis and Review • Elliptic Curve Cryptography • Finite Field Cryptography • Symmetric Cryptography and Hashes • Post-quantum Cryptography • Cryptanalysis of Novel Cryptosystems • Implementation Review of Cryptographic Primitives • Key Management Design and Implementation Review

Closing date for applications:

Contact: Danielle Owen

More information: https://nccgroup.wd3.myworkdayjobs.com/NCC_Group/job/USA-Remote---Eastern-Time/Senior-Cryptography-Researcher_R3223

We are looking for a PhD student and a Post-Doc in the area of (applied crypto) and/or side-channels.

The PhD post can be in any (fun) area of crypto; the candidate will be supervised by Elisabeth Oswald, and as co-supervisors A. Roy and E. Andreeva are potentially available.

The Post-Doc is related to ERC funding and therefore will work in the area of side channels; our areas of interest here are techniques for secure software development, and RISC-V.

Both posts are available immediately. The salary is around 32k per annum for the PhD student and 35k upwards (depending on prior experience) for the Post-Doc. Further information about the group is under www.cybersecurityresearch.at

Closing date for applications:

Contact: Elisabeth Oswald (firstname.lastname@aau.at)

More information: http://www.cybersecurityresearch.at

Ascon-p is the core building block of Ascon, the winner in the lightweight category of the CAESAR competition. With ISAP, another Ascon-p-based AEAD scheme is currently competing in the 2nd round of the NIST lightweight cryptography standardization project. In contrast to Ascon, ISAP focuses on providing hardening/protection against a large class of implementation attacks, such as DPA, DFA, SFA, and SIFA, entirely on mode-level. Consequently, Ascon-p can be used to realize a wide range of cryptographic computations such as authenticated encryption, hashing, pseudorandom number generation, with or without the need for implementation security, which makes it the perfect choice for lightweight cryptography on embedded devices.

In this paper, we implement Ascon-p as an instruction extension for RISC-V that is tightly coupled to the processors register file and thus does not require any dedicated registers. This single instruction allows us to realize all cryptographic computations that typically occur on embedded devices with high performance. More concretely, with ISAP and Ascon's family of modes for AEAD and hashing, we can perform cryptographic computations with a performance of about 2 cycles/byte,or about 4 cycles/byte if protection against fault attacks and power analysis is desired.

As we show, our instruction extension requires only 4.7 kGE, or about half the area of dedicated Ascon co-processor designs, and is easy to integrate into low-end embedded devices like 32-bit ARM Cortex-M or RISC-V microprocessors. Finally, we analyze the provided implementation security of ISAP, when implemented using our instruction extension.

Fresh rekeying is a well-established method to protect a primitive or mode against side-channel attacks: an easy to protect but cryptographically not so involved function generates a subkey from the master key, and this subkey is then used for the block encryption of a single or a few messages. It is an efficient way to achieve side-channel protection, but current solutions only achieve birthday bound security in the block size of the cipher and thus halve its security (except if more involved primitives are employed). We present generalized solutions to parallel block cipher rekeying that, for the first time, achieve security beyond the birthday bound in the block size $n$. The first solution involves, next to the subkey generation, one multiplication and the core block cipher call and achieves $2^{2n/3}$ security. The second solution makes two block cipher calls, and achieves optimal $2^n$ security. Our third solution uses a slightly larger subkey generation function but requires no adaptations to the core encryption and also achieves optimal security. The construction seamlessly generalizes to permutation based fresh rekeying. Central to our schemes is the observation that fresh rekeying and generic tweakable block cipher design are two very related topics, and we can take lessons from the advanced results in the latter to improve our understanding and development of the former. We subsequently use these rekeying schemes in a constructive manner to deliver three authenticated encryption modes that achieve beyond birthday bound security and are easy to protect against side-channel attacks.

Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal lattices than in arbitrary ones, in particular in the quantum setting.

Our main contribution is to propose a new ``twisted'' version of the PHS (by Pellet-Mary, Hanrot and Stehlé 2019) algorithm, that we call Twisted-PHS. As a minor contribution, we also propose several improvements of the PHS algorithm. On the theoretical side, we prove that our Twisted-PHS algorithm performs at least as well as the original PHS algorithm. On the practical side though, we provide a full implementation of our algorithm which suggests that much better approximation factors are achieved, and that the given lattice bases are a lot more orthogonal than the ones used in PHS. This is the first time to our knowledge that this type of algorithm is completely implemented and tested for fields of degrees up to~$60$.

Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages.

In this work, we explore the possibility of achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the k-challenge setting (i.e., the adversary can obtain k challenge ciphertexts for each public key) if its secret key contains less than k bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the k-challenge setting, where the ratio of the secret key length to k approaches the lower bound 1.

Motivated by the currently widespread concern about mass surveillance of encrypted communications, Bellare \emph{et al.} introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare \emph{et al.}, CRYPTO'14 \& ACM CCS'15; Ateniese \emph{et al.}, ACM CCS'15; Berndt and Li\'{s}kiewicz, ACM CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much progress, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key, and also previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Li\'{s}kiewicz, ACM CCS'17).

In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more effective and dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practice. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box yet quite general attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack.

Our attack relies on a novel identification and formalization of certain properties that yield practical ASAs on KEMs. More broadly, it points at and may shed some light on exploring structural weaknesses of other ``composed cryptographic primitives,'' which may make them susceptible to more dangerous ASAs with effectiveness that surpasses the known logarithmic upper bound (i.e., reviewing composition as an attack enabler).

Achieving fairness and soundness in non-simultaneous rational secret sharing schemes has proved to be challenging. On the one hand, soundness can be ensured by providing side information related to the secret as a check, but on the other, this can be used by deviant players to compromise fairness. To overcome this, the idea of incorporating a time delay was suggested in the literature: in particular, time-delay encryption based on memory-bound functions has been put forth as a solution. In this paper, we propose a different approach to achieve such delay, namely using homomorphic time-lock puzzles (HTLPs), introduced at CRYPTO 2019, and construct a fair and sound rational secret sharing scheme in the non-simultaneous setting from HTLPs. HTLPs are used to embed sub-shares of the secret for a predetermined time. This allows to restore fairness of the secret reconstruction phase, despite players having access to information related to the secret which is required to ensure soundness of the scheme. Key to our construction is the fact that the time-lock puzzles are homomorphic so that players can compactly evaluate sub-shares. Without this efficiency improvement, players would have to independently solve each puzzle sent from the other players to obtain a share of the secret, which would be computationally inefficient. We argue that achieving both fairness and soundness in a non-simultaneous scheme using a time delay based on CPU-bound functions rather than memory-bound functions is more cost effective and realistic in relation to the implementation of the construction.

Bit commitment is a primitive task of many cryptographic tasks. It has been proved that the unconditionally secure quantum bit commitment is impossible from Mayers-Lo-Chau No-go theorem. A variant of quantum bit commitment requires cheat sensible for both parties. Another results shows that these no-go theorem can be evaded using the non-relativistic transmission or Minkowski causality. Our goal in this paper is to revise unconditionally secure quantum bit commitment. We firstly propose new quantum bit commitments using distributed settings and quantum entanglement which is used to overcome Mayers-Lo-Chau No-go Theorems. Both protocols are perfectly concealing, perfectly binding, and cheating sensible in asymptotic model against entanglement-based attack and splitting attack from quantum networks. These schemes are then extended to commit secret bits against eavesdroppers. We further propose two new applications. One is to commit qubit states. The other is to commit unitary circuits. These new schemes are useful for committing several primitives including sampling model, randomness, and Boolean functions in cryptographic protocols.

In CRYPTO 2015, Cogliati et al. have proposed one-round tweakable Even-Mansour (\textsf{1-TEM}) cipher constructed out of a single $n$-bit public permutation $\pi$ and a uniform and almost XOR-universal hash function \textsf{H} as $(k, t, x) \mapsto \textsf{H}_k(t) \oplus \pi(\textsf{H}_k(t) \oplus x)$, where $t$ is the tweak, and $x$ is the $n$-bit message. Authors have shown that its two-round extension, which we refer to as \textsf{2-TEM}, obtained by cascading $2$-independent instances of the construction gives $2n/3$-bit security and $r$-round cascading gives $rn/r+2$-bit security. In ASIACRYPT 2015, Cogliati and Seurin have shown that four-round tweakable Even-Mansour cipher, which we refer to as \textsf{4-TEM}, constructed out of four independent $n$-bit permutations $\pi_1, \pi_2, \pi_3$ and $\pi_4$ and two independent $n$-bit keys $k_1$ and $k_2$, defined as \begin{equation} \label{eq:abstract} k_1 \oplus t \oplus \pi_4(k_2 \oplus t \oplus \pi_3(k_1 \oplus t \oplus \pi_2(k_2 \oplus t \oplus \pi_1(k_1 \oplus t \oplus x)))), \end{equation}

\noindent is secure upto $2^{2n/3}$ adversarial queries. In this paper, we have shown that if we replace two independent permutations of \textsf{2-TEM} (Cogliati et al., CRYPTO 2015) with a single $n$-bit public permutation, then the resultant construction still guarrantees security upto $2^{2n/3}$ adversarial queries. Using the results derived therein, we also show that replacing the permutation $(\pi_4, \pi_3)$ with $(\pi_1, \pi_2)$ in Eqn.~\eqref{eq:abstract} preserves security upto $2^{2n/3}$ adversarial queries.

This paper studies constructions of pseudorandom functions (PRFs) from non-adaptive PRFs (naPRFs), i.e., PRFs which are secure only against distinguishers issuing all of their queries at once.

Berman and Haitner (Journal of Cryptology, '15) gave a one-call construction which, however, is not hardness preserving -- to obtain a secure PRF (against polynomial-time distinguishers), they need to rely on a naPRF secure against superpolynomial-time distinguishers; in contrast, all known hardness-preserving constructions require $\omega(1)$ calls. This leaves open the question of whether a stronger superpolynomial-time assumption is necessary for one-call (or constant-call) approaches. Here, we show that a large class of one-call constructions (which in particular includes the one of Berman and Haitner) cannot be proved to be a secure PRF under a black-box reduction to the (polynomial-time) naPRF security of the underlying function.

Our result complements existing impossibility results (Myers, EUROCRYPT '04; Pietrzak, CRYPTO '05) ruling out natural specific approaches, such as parallel and sequential composition. Furthermore, we show that our techniques extend to rule out a natural class of constructions making parallel but arbitrary number of calls which in particular includes parallel composition and the two-call, cuckoo-hashing based construction of Berman et al.\ (Journal of Cryptology, '19).