International Association
for Cryptologic Research

We show the first robust secret sharing scheme for a maximal threshold $t < n/2$ that features an optimal overhead in share size, offers security against a rushing adversary, and runs in polynomial time. Previous robust secret sharing schemes for $t < n/2$ either suffered from a suboptimal overhead, offered no (provable) security against a rushing adversary, or ran in superpolynomial time.

Physical Unclonable Functions (PUFs) are physical devices with unique behavior that are hard to clone. A variety of PUF schemes have been considered in theoretical studies as well as practical implementations of several security primitives such as identification and key generation. Recently, the inherent unclonability of quantum states has been exploited for defining (a partial) quantum analogue to classical PUFs (against limited adversaries). There are also a few proposals for quantum implementations of classical optical PUFs. However, none of these attempts provides a comprehensive study of Quantum Physical Unclonable Functions (QPUFs) with quantum cryptographic tools as we present in this paper. We formally define QPUFs, encapsulating all requirements of classical PUFs as well as introducing new ones inherent to the quantum setting such as testability. We develop a quantum game-based security framework for our analysis and define a new class of quantum attacks, called General Quantum Emulation Attack. This class of attacks exploits previously captured valid challenge-response pairs to emulate the action of an unknown quantum transformation on new input. We devise a concrete attack based on an existing quantum emulation algorithm and use it to show that a family of quantum cryptographic primitives that rely on unknown unitary transformations do not provide existential unforgeability while they provide selective unforgeability. Then, we express our results in the case of QPUF as an unknown unitary transformation.

In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold.

First, we identify a specific source of side-channel leakage in most implementations of those schemes. Signing in lattice-based hash-and-sign schemes involves sampling a lattice point according to a Gaussian distribution. This reduces to sampling several one-dimensional discrete Gaussian distributions with standard deviations determined by the Gram–Schmidt norms of the secret lattice basis. Our observation is that those norms often leak through timing side-channels in the implementation of the one-dimensional Gaussian samplers.

Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram–Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field. To establish it, we propose efficient algorithms of independent interest which, given the leading principal minors of the matrix associated to a totally positive field element (in the power basis for DLP and the bit-reversed order basis for Falcon) recover the element up to conjugation. In the case of those schemes, that element is $f\bar f + g\bar g$, where $(f,g)$ is the NTRU-style secret key. We then show that this element combined with the verification key suffices to recover the entire secret efficiently.

Third, we concretely demonstrate the side-channel attack against DLP. The challenge is that timing information only provides an approximation of the Gram–Schmidt norms (with an accuracy increasing with the number of traces), and our algebraic recovery technique needs to be combined with pruned tree search in order to apply it to approximated values. Experimentally, we show that around $2^{35}$ DLP traces are enough to reconstruct the entire key with good probability. Carrying out a similar experiment against Falcon is left as an open problem, however, since the recursive nature of our bit-reversed order recovery algorithm does not accommodate approximate inputs easily. Nevertheless, our results do underscore the importance of constant time implementations particularly for schemes using Gaussian sampling.

Middle-Product Learning With Errors (MP-LWE) is a variant of the LWE problem introduced at CRYPTO 2017 by Rosca et al [RSSS17]. Asymptotically, the theoretical results of [RSSS17] suggest that MP-LWE gives lattice-based public-key cryptosystems offering a ‘security-risk vs. efficiency’ trade-off: higher performance than cryptosystems based on unstructured lattices (LWE problem) and lower risk than cryptosystems based on structured lattices (Polynomial/Ring LWE problem). However, although promising in theory, [RSSS17] left the practical implications of MP-LWE for lattice-based cryptography unclear.

In this paper, we show how to build practical public-key cryptosystems with strong security guarantees based on MP-LWE. On the implementation side, we present optimised fast algorithms for computing the middle-product operation over polynomial rings $Z_q[x]$, the dominant computation for MP-LWE-based cryptosystems. On the security side, we show how to obtain a nearly tight security proof for MP-LWE from the hardest Polynomial LWE problem over a large family of rings, improving on the loose reduction of [RSSS17]. We also show and analyze an optimised cryptanalysis of MP-LWE that narrows the complexity gap to the above security proof. To evaluate the practicality of MP-LWE, we apply our results to construct, implement and optimise parameters for a practical MP-LWE-based public-key cryptosystem, Titanium, and compare its benchmarks to other lattice-based systems. Our results show that MP-LWE offers a new ‘security-risk vs. efficiency’ trade-off in lattice-based cryptography in practice, not only asymptotically in theory.

Blockchain is a distributed and decentralized ledger for recording transactions. It is maintained and shared among the participating nodes by utilizing cryptographic primitives. A consensus protocol ensures that all nodes agree on a unique order in which records are appended. However, current blockchain solutions are facing scalability issues. Many methods, such as Off-chain and Directed Acyclic Graph (DAG) solutions, have been proposed to address the issue. However, they have inherent drawbacks, e.g., forming parasite chains. Performance, such as throughput and latency, is also important to a blockchain system. Sharding has emerged as a good candidate that can overcome both the scalability and performance problems in blockchain. To date, there is no systematic work that analyzes the sharding protocols. To bridge this gap, this paper provides a systematic and comprehensive review on blockchain sharding techniques. We first present a general design flow of sharding protocols and then discuss key design challenges. For each challenge, we analyze and compare the techniques in state-of-the-art solutions. Finally, we discuss several potential research directions in blockchain sharding.

We present a new public-coin setup protocol for aggregating BLS signatures on distinct messages. For $n$ messages the verifier computes just $6$ pairings and $6(n+\textrm{log}(n))$ exponentiations—an improvement on previous aggregate schemes in which the verifier computes $n+1$ pairings. Our aggregate signature is logarithmic in size. This result uses an $\textit{inner pairing product argument}$ of knowledge that can be used to prove membership in pairing-based languages.

This paper presents an efficient deterministic algorithm for computing $13$\textsuperscript{th}-power residue symbols in the cyclotomic field $\mathbb{Q}(\zeta_{13})$, where $\zeta_{13}$ is a primitive $13$\textsuperscript{th} root of unity.

The new algorithm finds applications in the implementation of certain cryptographic schemes and closes a gap in the \textsl{corpus} of algorithms for computing power residue symbols.

Encrypted search algorithms (ESA) are cryptographic algorithms that support search over encrypted data. ESAs can be designed with various primitives including searchable/structured symmetric encryption (SSE/STE) and oblivious RAM (ORAM). Leakage abuse attacks attempt to recover client queries using knowledge of the client’s data. An important parameter for any leakage-abuse attack is its known-data rate; that is, the fraction of client data that must be known to the adversary.

In this work, we revisit leakage abuse attacks in several ways. We first highlight some practical limitations and assumptions underlying the well-known IKK (Islam et al. NDSS ’12) and Count (Cash et al., CCS ’15) attacks. We then design four new leakage-abuse attacks that rely on much weaker assumptions. Three of these attacks are volumetric in the sense that they only exploit leakage related to document sizes. In particular, this means that they work not only on SSE/STE-based ESAs but also against ORAM-based solutions. We also introduce two volumetric injection attack which use adversarial file additions to recover queries even from ORAM-based solutions. As far as we know, these are the first attacks of their kind.

We evaluated all our attacks empirically and considered many experimental settings including different data collections, query selectivities, known-data rates, query space size and composition. From our experiments, we observed that the only setting that resulted in reasonable recovery rates under practical assumptions was the case of high-selectivity queries with a leakage profile that includes the response identity pattern (i.e., the identifiers of the matching documents) and the volume pattern (i.e., the size of the matching documents). All other attack scenarios either failed or relied on unrealistic assumptions (e.g., very high known-data rates). For this specific setting, we propose several suggestions and countermeasures including the use of schemes like PBS (Kamara et al, CRYPTO ’18), VLH/AVLH (Kamara and Moataz, Eurocrypt ’19 ), or the use of padding techniques like the ones recently proposed by Bost and Fouque (Bost and Fouque, IACR ePrint 2017/1060).

Asymmetric schemes are moving towards a new series of cryptosystems based on known open problems that until the day guarantee security from the point that are not solvable under determined properties. In this paper you can read a novel research done mostly on the field of Multivariate Public Key Cryptography that focus the interest on sharing a pre-master key between Alice and Bob using quadratic multivariate polynomials as the public key. What does this scheme somehow special is that it uses a private construction involving polynomial factorization that allows Alice to recover the secret sent by Bob.

We seek constructions of general-purpose immunizers that take arbitrary cryptographic primitives, and transform them into ones that withstand a powerful “malicious but proud” adversary, who attempts to break security by possibly subverting the implementation of all algorithms (including the immunizer itself!), while trying not to be detected. This question is motivated by the recent evidence of cryptographic schemes being intentionally weakened, or designed together with hidden backdoors, e.g., with the scope of mass surveillance. Our main result is a subversion-secure immunizer in the plain model, that works for a fairly large class of deterministic primitives, i.e. cryptoschemes where a secret (but tamperable) random source is used to generate the keys and the public parameters, whereas all other algorithms are deterministic. The immunizer relies on an additional independent source of public randomness, which is used to sample a public seed. Assuming the public source is untamperable, and that the subversion of the algorithms is chosen independently of the seed, we can instantiate our immunizer from any one-way function. In case the subversion is allowed to depend on the seed, and the public source is still untamperable, we obtain an instantiation from collision-resistant hash functions. In the more challenging scenario where the public source is also tamperable, we additionally need to assume that the initial cryptographic primitive has sub-exponential security. Previous work in the area only obtained subversion-secure immunization for very restricted classes of primitives, often in weaker models of subversion and relying on random oracles, or by leveraging a higher number of independent random sources.

Blockchain brings dawn to decentralized applications which coordinate correct computations without a prior trust. However, existing scalable on-chain frameworks are incompetent in dealing with intensive validation. On the one hand, duplicated execution pattern leads to limited throughput and unacceptable expenses. On the other hand, there lack fair and secure incentive mechanisms allocating rewards according to the actual workload of validators, thus deriving bad dilemmas among rational participants and inducing effective attacks from shrewd adversaries. While most solutions rely on off-chain patterns to sidestep the shackles, it further introduces unexpected issues in applicability, fairness and brittle dependency on interactive cooperation. The intrinsic bottleneck of backbone has never been drastically broken.

This work presents Lever, the first scalable on-chain framework which supports intensive validation, meanwhile achieves validity, incentive compatibility and cost-efficiency tolerance of f<n/4 Byzantine participants. Lever firstly integrates the evaluation of complexity into the correctness of transaction, thoroughly decoupling intensive validation from regular Byzantine consensus. Significant scalability is then achieved by launching few rounds of novel validation-challenge game between potential adversaries and rational stakeholders; compelling incentive mechanism effectively transfers deposits of adversary to specialized rewards for honest validators, therefore allows the user to lever sufficient endorsement for verification with minimum cost. Combined with game-theoretic insights, a backstop protocol is designed to ensure finality and validity of the framework, breaking through the famous Verifier’s Dilemma. Finally, we streamline Lever under the efficient architecture of sharding, which jointly shows robust to conceivable attacks on validation and performs outstanding ability to purify Byzantine participants. Experimental results show that Lever vastly improves the throughput and reduces expenses of intensive validation with slight compromise in latency.

Despite several works on secrecy coding for fading and MIMO wiretap channels from an error probability perspective, the construction of information-theoretically secure codes over such channels remains an open problem. In this paper, we consider a fading wiretap channel model where the transmitter has only partial statistical channel state information. Our channel model includes static channels, i.i.d. block fading channels, and ergodic stationary fading with fast decay of large deviations for the eavesdropper's channel.

We extend the flatness factor criterion from the Gaussian wiretap channel to fading and MIMO wiretap channels, and establish a simple design criterion where the normalized product distance / minimum determinant of the lattice and its dual should be maximized simultaneously.

Moreover, we propose concrete lattice codes satisfying this design criterion, which are built from algebraic number fields with constant root discriminant in the single-antenna case, and from division algebras centered at such number fields in the multiple-antenna case.

Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most $n-1$, modulo an irreducible polynomial of degree $n$ with $2n$ input and $n$ output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only $O(n^{\log_2(3)})$ Toffoli gates at the cost of a higher CNOT gate count: theoretically up to $O(n^2)$ but in examples the CNOT gate count looks a lot better.

We consider compound multi-input multi-output (MIMO) wiretap channels where minimal channel state information at the transmitter (CSIT) is assumed. Code construction is given for the special case of isotropic mutual information, which serves as a conservative strategy for general cases. Using the flatness factor for MIMO channels, we propose lattice codes universally achieving the secrecy capacity of compound MIMO wiretap channels up to a constant gap (measured in nats) that is equal to the number of transmit antennas. The proposed approach improves upon existing works on secrecy coding for MIMO wiretap channels from an error probability perspective, and establishes information theoretic security (in fact semantic security). We also give an algebraic construction to reduce the code design complexity, as well as the decoding complexity of the legitimate receiver. Thanks to the algebraic structures of number fields and division algebras, our code construction for compound MIMO wiretap channels can be reduced to that for Gaussian wiretap channels, up to some additional gap to secrecy capacity.

The Real World Crypto Symposium (RWC) 2019 will be held in New York, USA, January 8-10, 2020.

The conference webpage: https://rwc.iacr.org/2020/index.html

Registration information: https://rwc.iacr.org/2020/registration.html

TCC 2019, the 17th Theory of Cryptography Conference will be held in Nuremberg, Germany, December 1-5, 2019.

The conference webpage: https://tcc.iacr.org/2019/index.html

Registration
TCC 2019 registrations are now open at https://tcc.iacr.org/2019/registration.html. The early registration deadline ends on November 3, 2019.

Accommodation
There is a number of hotels listed under https://tcc.iacr.org/2019/accommodations.html.
Note that the provided rates will no longer be valid after 17 October. Later bookings will be considerably more expensive due to Nuremberg Christkindlesmarkt which also opens in December.

We study the concrete security of high-performance implementations of half-gates garbling, which all rely on (hardware-accelerated)~AES. We find that current instantiations using $k$-bit wire labels can be completely broken---in the sense that the circuit evaluator learns all the inputs of the circuit garbler---in time $O(2^k/C)$, where $C$ is the total number of (non-free) gates that are garbled, possibly across multiple independent executions. The attack can be applied to existing circuit-garbling libraries using $k=80$ when $C \approx 10^9$, and would require 267 machine-months and cost about USD 3500 to implement on the Google Cloud Platform. Since the attack can be entirely parallelized, the attack could be carried out in about a month using $\approx 250$ machines.

With this as our motivation, we seek a way to instantiate the hash function in the half-gates scheme so as to achieve better concrete security. We present a construction based on AES that achieves optimal security in the single-instance setting (when only a single circuit is garbled). We also show how to modify the half-gates scheme so that its concrete security does not degrade in the multi-instance setting. Our modified scheme is as efficient as prior work in networks with up to 2 Gbps bandwidth.

Blind signatures constitute basic cryptographic ingredients for privacy-preserving applications such as anonymous credentials, e-voting, and Bitcoin. Despite the great variety of cryptographic applications, blind signatures also found their way in real-world scenarios. Due to the expected progress in cryptanalysis using quantum computers, it remains an important research question to find practical and secure alternatives to systems based on classical security assumptions that are not future-proof. In this work we present $\mathsf{BLAZE}$, a new practical blind signature scheme from lattice assumptions. With respect to all relevant efficiency metrics $\mathsf{BLAZE}$ is much more efficient than all previous blind signature schemes based on assumptions conjectured to withstand quantum computer attacks. In particular, $\mathsf{BLAZE}$ considerably improves upon the first (and currently only secure) lattice-based proposal introduced by Rückert at ASIACRYPT 2010 ($\mathsf{RBS}$). For instance, at 128 bits of security signatures are as small as 6.6 KB, which represents an improvement factor of 13.5 compared to $\mathsf{RBS}$, 2.7 compared to all previous candidates, and an expansion factor of 2.5 compared to the NIST PQC submission $\mathsf{Dilithium}$. We also give a highly optimized implementation, which demonstrates the efficiency of $\mathsf{BLAZE}$ to be deployed in practical applications. In particular, generating a blind signature takes just 18 ms, which represents a factor improvement of 15 compared to $\mathsf{RBS}$. The running times for key generation and verification are in the same order as state-of-the-art regular signature schemes, however several orders of magnitudes faster than $\mathsf{RBS}$.

This paper presents optimized software for constant-time variable-base scalar multiplication on prime-order Weierstraß curves using the complete addition and doubling formulas presented by Renes, Costello, and Batina in 2016. Our software targets three different microarchitectures: Intel Sandy Bridge, Intel Haswell, and ARM Cortex-M4. We use a 255-bit elliptic curve over $\mathbb{F}_{2^{255}-19}$ that was proposed by Barreto in 2017. The reason for choosing this curve in our software is that it allows most meaningful comparison of our results with optimized software for Curve25519. The goal of this comparison is to get an understanding of the cost of using cofactor-one curves with complete formulas when compared to widely used Montgomery (or twisted Edwards) curves that inherently have a non-trivial cofactor.

We revisit the high-order masking schemes for private multiplication introduced by Belaïd et al. at EUROCRYPT 2016, and the matrix model for non-interference (NI) security that they develop in their follow-up work of CRYPTO 2017. This leads to two main results. 1) We generalise the theorems of CRYPTO 2017 so as to be able to apply them to masking schemes over any finite field --- in particular GF(2) --- and to be able to analyse the strong non-interference (SNI) security notion. This leads to an efficient algorithm that allows us to computationally check the (S)NI security of binary schemes up to order d=11. 2) We propose new SNI and NI masking gadgets for multiplication over GF(2) (and any extension thereof) up to order 9 and 11 that improve the randomness complexity of the schemes of EUROCRYPT 2016 and of Ishai, Sahai and Wagner (CRYPTO 2003) respectively. A natural generalisation of the NI schemes is also conjectured to be secure at any order.