International Association
for Cryptologic Research

We introduce Biometric-Authenticated Keyword Search (BAKS), a novel searchable encryption scheme that relieves clients from managing cryptographic keys and relies purely on client’s biometric data for authenticated outsourcing and retrieval of files indexed by encrypted keywords. BAKS utilises distributed trust across two servers and the liveness assumption which models physical presence of the client; in particular, BAKS security is guaranteed even if clients’ biometric data, which often has low entropy, becomes public. We formalise two security properties, Authentication and Indistinguishability against Chosen Keyword Attacks, which ensure that only a client with a biometric input sufficiently close to the registered template is considered legitimate and that neither of the two servers involved can learn any information about the encrypted keywords. Our BAKS construction further supports outsourcing and retrieval of files using multiple keywords and flexible search queries (e.g., conjunction, disjunction and subset-type queries). An additional update mechanism allows clients to replace their registered biometrics without requiring re-encryption of outsourced keywords, which enables smooth user migration across devices supporting different types of biometrics.

Traditional group signatures feature a single issuer who can add users to the group of signers and a single opening authority who can reveal the identity of the group member who computed a signature. Interestingly, despite being designed for privacy-preserving applications, they require strong trust in these central authorities who constitute single points of failure for critical security properties. To reduce the trust placed on authorities, we introduce dynamic group signatures which distribute the role of issuer and opener over several entities, and support t_I-out-of-n_I issuance and t_O-out-of-n_O opening. We first define threshold dynamic group signatures and formalize their security. We then give an efficient construction relying on the pairing-based Pointcheval–Sanders (PS) signature scheme (CT-RSA 2018), which yields very short group signatures of two first-group elements and three exponents. We also give a simpler variant of our scheme in which issuance requires the participation of all n_I issuers, but still supports t_O-out-of-n_O opening. It is based on a new multi-signature variant of the PS scheme which allows for efficient proofs of knowledge and is a result of independent inter- est. We prove our schemes secure in the random-oracle model under a non-interactive q-type of assumption.

In the past few years, significant progresses on homomorphic encryption (HE) have been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE). In this work, we present new conversion algorithms which switch between different (R)LWE-based HE schemes to take advantages of them. Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption. Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.

The SHA-1 hash function was designed in 1995 and has been widely used during two decades. A theoretical collision attack was first proposed in 2004 [WYY05], but due to its high complexity it was only implemented in practice in 2017, using a large GPU cluster [SBK+17]. More recently, an almost practical chosen-prefix collision attack against SHA-1 has been proposed [LP19]. This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more threatening for real protocols.

In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collisions attack against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity of $2^{61.2}$ rather than $2^{64.7}$, and chosen-prefix collisions with a complexity of $2^{63.4}$ rather than $2^{67.1}$. When renting cheap GPUs, this translates to a cost of 11k US\$ for a collision, and 45k US\$ for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid 75k US\$ because GPU prices were higher, and we wasted some time preparing the attack).

Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH). We strongly advise to remove SHA-1 from those type of applications as soon as possible. We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to a forgery. This proves that SHA-1 signatures now offers virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).

We show new hardness results for the class of Polynomial Local Search problems ($\mathsf{PLS}$):

* Hardness of $\mathsf{PLS}$ based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions.

* Hardness of $\mathsf{PLS}$ relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search.

The core observation behind the results is that the unique proofs property of incrementally-verifiable computations previously used to demonstrate hardness in $\mathsf{PLS}$ can be traded with a simple incremental completeness property.

This paper proposes various optimizations for lattice-based key-encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, small polynomial multiplications and more aggressive layer merging in the NTT but also reduced stack usage. We test those optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project and also NewHope-Compact, a recently proposed derivative of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on Cortex-M4 and shows speed improvements over previous high-speed implementations on the same platform for Kyber and NewHope . Moreover, it gives a common framework to compare those algorithms with the same level of optimization. Our results show that NewHope-Compact is the faster algorithm, followed by Kyber and finally NewHope that seems to suffer from its large modulus and error distribution for small dimensions.

With the increasing number of traffic accidents and terrorist attacks by modern vehicles, vehicular digital forensics (VDF) has gained significant attention in identifying and determining evidences from the related digital devices. Ensuring the law enforcement agency to accurately integrate various kinds of data is a crucial point to determine the facts. However, malicious attackers or semi-honest participants may undermine the digital forensic procedures. Enabling accountability and privacy preservation while providing secure fine-grained data access control in VDF is a non-trivial challenge. To mitigate this issue, in this paper, we propose a blockchain-based scheme for VDF named BB-VDF, in which the accountable protocols and privacy preservation methods are constructed. The desirable security properties and fine-grained data access control are achieved based on the customized smart contracts and cryptographic constructions. Specifically, we design novel smart contracts that model the forensics procedures as a finite state machine, which guarantees accountability that each participant performs auditable cooperation under tamper-resistant and traceable transactions. Furthermore, we design a distributed key-policy attribute based encryption scheme with partially hidden access structures to realize the secure fine-grained forensics data access control. Systematic security analysis and extensive experimental results show the feasibility and practicability of the proposed BB-VDF scheme.

The article provides a new double point compression method (to $2\log_2(q) + 4$ bits) for an elliptic $\mathbb{F}_{\!q}$-curve $E\!: y^2 = x^3 + b$ of $j$-invariant $0$ over a finite field $\mathbb{F}_{\!q}$ such that $q \equiv 1 \ (\mathrm{mod} \ 3)$. More precisely, we obtain explicit simple formulas transforming the coordinates $x_0,y_0,x_1,y_1$ of two points $P_0, P_1 \in E(\mathbb{F}_{\!q})$ to some two elements $t, s \in \mathbb{F}_{\!q}$ with four auxiliary bits. To recover (in the decompression stage) the points $P_0, P_1$ it is proposed to extract a sixth root $\sqrt[6]{w} \in \mathbb{F}_{\!q}$ of some element $w \in \mathbb{F}_{\!q}$. It is easily seen that for $q \equiv 3 \ (\mathrm{mod} \ 4)$, $q \not\equiv 1 \ (\mathrm{mod} \ 27)$ this can be implemented by means of just one exponentiation in $\mathbb{F}_{\!q}$. Therefore the new compression method seems to be much faster than the classical one with the coordinates $x_0, x_1$, whose decompression stage requires two exponentiations in $\mathbb{F}_{\!q}$.

In order to obtain an efficient elliptic curve with 128-bit security and a prime order, we explore the use of finite fields $GF(p^n)$, with $p$ a small modulus (less than $2^{16}$) and $n$ a prime. Such finite fields allow for an efficient inversion algorithm due to Itoh and Tsujii, which we can leverage to make computations on an ordinary curve (short Weierstraß equation) in affine coordinates. We describe a very efficient variant of Montgomery reduction for computations modulo $p$, and choose $p = 9767$ and $n = 19$ to better map the abilities of small microcontrollers of the ARM Cortex-M0+ class. Inversion cost is only six times the cost of multiplication. Our fully constant-time implementation of curve point multiplication runs in about 4.5 million cycles (only 1.29 times slower than the best reported Curve25519 implementations); it also allows for efficient key pair generation (about 1.9 million cycles) and Schnorr signature verification (about 5.6 million cycles). Moreover, we describe variants of the Itoh-Tsujii algorithms that allow fast computations of square roots and cube roots (in less than twenty times the cost of a multiplication), leading to efficient point compression and constant-time hash-to-curve operations with Icart's map.

A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not a sufficient condition to admit an ideal secret sharing scheme.

In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most $n$ times the size of the secret. Using the previously known secret sharing constructions, the size of each share was $O(n^2/\log n)$ the size of the secret.

Our construction is extended to ports of matroids of any rank $k\geq 2$, obtaining secret sharing schemes in which the size of each share is at most $n^{k-2}$ times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require $(F_q,\ell)$-linear secret schemes with total information ratio $\Omega(2^{n/2}/\ell n^{3/4}\sqrt{\log q})$.

The Crypto-System Laboratory (CSL) at the Department of Computer Science, Shanghai Jiao Tong University is looking for candidates for 2 postdoctoral positions and 2 research fellows/associates on cryptography, including but not limited to the following:

• privacy-preserving computation (MPC, FHE, ZKP, etc.)
• lattice-based cryptography
• side-channel attacks and leakage-resilient cryptography
• blockchain technologies (consensus, security and integration with IoT)
• cryptographic implementations and optimizations

We offer a competitive salary package commensurate with applicant's research experience. The contract will be for 2 years initially with the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences. Interested candidates are encouraged to send their CV and name two references to Dr. Yu Yu. Review of applicants will start immediately until the positions are filled.

Closing date for applications:

Contact: Dr. Yu Yu ( yyuu@sjtu.edu.cn )

More information: https://crypto.sjtu.edu.cn/lab/

The Department of Electronic and Electrical Engineering, Institute of Sensors, Signals and Communications seeks to appoint a Research Associate in the area of cyber security simulation platform for the H2020 Advanced cyber-security simulation platform for preparedness training in Aviation, Naval and Power-grid environments (FORESIGHT) project. The FORESIGHT project will develop a federated cyber-range solution to enhance the preparedness of cyber-security professionals at all levels and advance their skills towards preventing, detecting, reacting and mitigating sophisticated cyber-attacks thus providing a holistic approach to cyber-threat management and cultivate a strong security culture. In particular, you will be responsible to provide an ecosystem of networked realistic training and simulation platforms from the aviation, smart grid and naval domains. The creation of complex cross-domain/hybrid scenarios will extend the capabilities of existing solutions with an emphasis on realistic and dynamic scenarios based on cyber-attacks and vulnerabilities gathered from the dark web.

A full description can be foud here:

https://academicpositions.com/ad/university-of-strathclyde/2019/research-associate-in-cyber-security-simulation-platforms-h2020-foresight-258336/137449

Closing date for applications:

Contact: Please contact Dr Xavier Bellekens before applying with a CV at xavier.bellekens@strath.ac.uk

More information: https://academicpositions.com/ad/university-of-strathclyde/2019/research-associate-in-cyber-security-simulation-platform

Event date: 9 June to 11 June 2020
Submission deadline: 14 March 2020
Notification: 15 May 2020

Event date: 22 July 2020
Submission deadline: 1 February 2020
Notification: 30 April 2020

Event date: 10 May 2020
Submission deadline: 20 March 2020
Notification: 10 April 2020

Event date: 1 June to 5 June 2020
Submission deadline: 31 January 2020
Notification: 29 February 2020

A canonical identification (CID) scheme is a 3-move protocol consisting of a commitment, challenge, and response. It constitutes the core design of many cryptographic constructions such as zero-knowledge proof systems and various types of signature schemes. Unlike number-theoretic constructions, CID in the lattice setting usually forces provers to abort and repeat the whole authentication process once the distribution of the computed response does not follow a target distribution independent from the secret key. This concept has been realized by means of rejection sampling, which makes sure that the secrets involved in a protocol are concealed after a certain number of repetitions. This however has a negative impact on the efficiency of interactive protocols because it leads to a number of communication rounds that is multiplicative in the number of aborting participants (or rejection sampling procedures). In this work we show how the CID scheme underlying many lattice-based protocols can be designed with smaller number of aborts or even without aborts. Our new technique exploits (unbalanced) binary hash trees and thus significantly reduces the communication complexity. We show how to apply this new method within interactive zero-knowledge proofs. We also present BLAZE+: a further application of our technique to the recently proposed lattice-based blind signature scheme BLAZE (FC20). We show that BLAZE+ has an improved performance and communication complexity compared to BLAZE while preserving the size of signatures.

The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm. This construction requires a family F of trapdoor preimage sampleable functions (TPSF). In this work we extend this notion to the weaker Average TPSF (ATPSF) and show that the GPV construction also holds for ATPSF in the Random Oracle Model. We also introduce the problem of finding a Claw with a random function (Claw(RF)) and present a tight security reduction to the Claw(RF) problem. Our reduction is also optimal meaning that an algorithm that solves the Claw(RF) problem breaks the scheme. We extend these results to the quantum setting and prove this same tight and optimal reduction in the QROM. Finally, we apply these results to code-based signatures, notably the Wave signature scheme and prove tight and optimal reductions for it in the ROM and the QROM improving and extending the original analysis of [DST19a]

Lai-Massey scheme is a well-known block cipher structure which has been used in the design of the ciphers PES, IDEA, WIDEA, FOX and MESH. Recently, the lightweight block cipher FLY applied this structure in the construction of a lightweight $8 \times 8$ S-box from $4 \times 4$ ones. In the current paper, firstly we investigate the linear, differential and algebraic properties of the general form of S-boxes used in FLY, mathematically. Then, based on this study, a new cipher structure is proposed which we call generalized Lai-Massey scheme or GLM. We give upper bounds for the maximum average differential probability (MADP) and maximum average linear hull (MALH) of GLM and after examination of impossible differentials and zero-correlations of one round of this structure, we show that two rounds of GLM do not have any structural impossible differentials or zero-correlations. As a measure of structural security, we prove the pseudo-randomness of GLM by the H-coefficient method.

Privacy-preserving currency exchange between different cryptocurrencies on blockchain remains an open problem as the existing currency exchange schemes cannot provide anonymity of users or confidentiality of exchange amount. To solve this problem, we introduce BPCEX: a privacy-preserving currency exchange scheme which protects users' identities and the exchange amount, by usage of techniques including linkable ring signature, range proof, Diffie-Hellman key exchange, Pedersen commitment and UTXO swap. In BPCEX, the users' identities are hidden to verifiers and dealmakers, while the exchange amounts are hidden to the verifiers. BPCEX supports floating exchange rate, partial deal and public verification, without additional confirmation of traders, which improves the success rate and shortens the waiting time of the deal. Moreover, BPCEX is compatible with the regulatable privacy-preserving blockchain system, which realizes the traceability of users' identities and the exchange amount to prevent money laundering and illegal exchange, making BPCEX suitable in real-life applications, including currency market and stock market.