Network Function Virtualisation (NFV) advances the adoption of composable software middleboxes. Accordingly, cloud data centres become major NFV vendors for enterprise traffic processing. Due to the privacy concern of traffic redirection to the cloud, secure middlebox systems (e.g., BlindBox) draw much attention; they can process encrypted packets against encrypted rules directly. However, most of the existing systems supporting pattern matching based network functions require the enterprise gateway to tokenise packet payloads via sliding windows. Such tokenisation induces a considerable communication overhead, which can be over 100$\times$ to the packet size. To overcome this bottleneck, in this paper, we propose the first bandwidth-efficient encrypted pattern matching protocol for secure middleboxes. We resort to a primitive called symmetric hidden vector encryption (SHVE), and propose a variant of it, aka SHVE+, to achieve constant and moderate communication cost. To speed up, we devise encrypted filters to reduce the number of accesses to SHVE+ during matching highly. We formalise the security of our proposed protocol and conduct comprehensive evaluations over real-world rulesets and traffic dumps. The results show that our design can inspect a packet over 20k rules within 100 $\mu$s. Compared to prior work, it brings a saving of 94$\%$ in bandwidth consumption.

There have been several 51% attacks on Proof-of-Work (PoW) blockchains recently, including Verge and GameCredits, but the most noteworthy has been the attack that saw hackers make off with up to $18 million after a successful double spend was executed on the Bitcoin Gold network. For this reason, the Proof-of-Stake (PoS) algorithm, which already has advantages of energy efficiency and throughput, is attracting attention as an alternative to the PoW algorithm. With a PoS, the attacker needs to obtain 51% of the cryptocurrency to carry out a 51% attack. But unlike PoW, attacker in a PoS system is highly discouraged from launching 51% attack because he would have to risk losing his entire stake amount to do so. Moreover, even if a 51% attack succeeds, the value of PoS-based cryptocurrency will fall, and the attacker with the most stake will eventually lose the most. In this paper, we try to derive the results that go against these conventional myths. Despite of the significant depreciation of cryptocurrency, our method can make a profit from a 51% attack on the PoS blockchains using the traditional stock market's short selling (or shorting) concept. Our findings are an example to show that the conventional myth that "a destructive attack that destroys the blockchain ecosystem totally will not occur because it is fundamentally unprofitable to the attacker itself" may be wrong.

Ring signatures are a common construction used to provide signer ambiguity among a non-interactive set of public keys specified at the time of signing. Unlike early approaches where signature size is linear in the size of the signer anonymity set, current optimal solutions either require centralized trusted setups or produce signatures logarithmic in size. However, few also provide linkability, a property used to determine whether the signer of a message has signed any previous message, possibly with restrictions on the anonymity set choice. Here we introduce Triptych, a family of linkable ring signatures without trusted setup that is based on generalizations of zero-knowledge proofs of knowledge of commitment openings to zero. We demonstrate applications of Triptych in signer-ambiguous transaction protocols by extending the construction to openings of parallel commitments in independent anonymity sets. Signatures are logarithmic in the anonymity set size and, while verification complexity is linear, collections of proofs can be efficiently verified in batches. We show that for anonymity set sizes practical for use in distributed protocols, Triptych offers competitive performance with a straightforward construction.

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 evidence 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 data access control in VDF is a non-trivial challenge. To mitigate this issue, in this paper, we propose a blockchain-based decentralized solution for VDF named BB-VDF, in which the accountable protocols and algorithm are constructed. The desirable security properties and fine-grained data access control are achieved based on smart contract and the customized cryptographic construction. Specifically, we design a distributed key-policy attribute based encryption scheme with partially hidden access structures, named DKP-ABE-H, to realize the secure fine-grained forensics data access control. Further, a novel smart contract is designed to model the forensics procedures as a finite state machine, which guarantees accountability that each participant performs auditable cooperation under tamper-resistant and traceable transactions. Systematic security analysis and extensive experimental results show the feasibility and practicability of our proposed BB-VDF scheme.

The article provides a new double point compression method (to $2\lceil \log_2(q) \rceil + 4$ bits) for an elliptic $\mathbb{F}_{\!q}$-curve $E_b\!: 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 of $\mathbb{F}_{\!q}$ with four auxiliary bits. In order to recover (in the decompression stage) the points $P_0, P_1$ it is proposed to extract a sixth root $\sqrt[6]{Z} \in \mathbb{F}_{\!q}$ of some element $Z \in \mathbb{F}_{\!q}$. It is known 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}$. We also successfully adapt the new approach for compressing one $\mathbb{F}_{\!q^2}$-point on a curve $E_b$ with $b \in \mathbb{F}_{\!q^2}^*$.

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})$.

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 (FC'20). We show that BLAZE+ has an improved performance and communication complexity compared to BLAZE while preserving the size of keys and 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.

Traceable range proof (TRP) plays a major role in the construction of regulatable privacy-preserving blockchains, as it empowers regulators with traceability of the hidden amount in each transaction. In this paper, we give new constructions of TRPs with improved efficiency and more regulatory functions. In particular, we introduce sTBoRP: a simplified traceable Borromean range proof directly from Borromean ring signature without additional validity proofs for tracing keys, sTBoRP can be applied for multiple regulation between different regulators, and can be further modified to be secure against malicious regulators. Moreover, we introduce jTBuRP: a modified traceable Bulletproofs range proof to support joint regulation against collusion attack of malicious regulators, by improving the generation algorithm of tracing keys. We also give the security proofs for both schemes and give the comparisons of efficiency and security.

Let $f:\{-1,1\}^n\rightarrow \{-1,1\}$ be with total degree $d$, and $\widehat{f}(i)$ be the linear Fourier coefficients of $f$. The relationship between the sum of linear coefficients and the total degree is a foundational problem in theoretical computer science. In 2012, O'Donnell Conjectured that \[ \sum_{i=1}^n \widehat{f}(i)\le d\cdot {d-1 \choose \lfloor\frac{d-1}{2}\rfloor}2^{1-d}. \] In this paper, we prove that the conjecture is equivalent to a conjecture on the cryptographic Boolean function. We then prove that the conjecture is true for $d=1,n-1$. Moreover, we count the number of $f$'s such that the upper bound is achieved.

Constructing an elliptic curve of prime order has a significant role in elliptic curve cryptography. For security purposes, we need an elliptic curve of almost prime order. In this paper, we propose an efficient technique to generate an elliptic curve of nearly prime order. In practice, this algorithm produces an elliptic curve of order 2 times a prime number. Therefore, these elliptic curves are appropriate for practical uses. Presently, the most known working algorithms for generating elliptic curves of prime order are based on complex multiplication. The advantages of the proposed technique are: it does not require a deep mathe- matical theory, it is easy to implement in any programming language and produces an elliptic curve with a remarkably simple expression.