International Association
for Cryptologic Research

Event date: 2 September to 5 September 2019

Event date: 12 November to 15 November 2019
Submission deadline: 15 June 2019
Notification: 15 August 2019

Today server authentication is largely handled through Public Key Infrastructure (PKI) in both the private and the public sector. PKI is established as the defacto standard for Internet communication through the world wide web, and its usage in HTTPS, SSL/TLS (Web PKI). However, in its application to Internet of Things (IoT) devices, using Web PKI infrastructure for server authentication has several shortcomings, including issues with validity periods, identity, revocation practice, and governance. Recently, di erent approaches to decentralized PKI (DPKI) using Blockchain technology have been proposed, but so far have lacked practicality in their application to devices commonly used in IoT deployments. The approaches are too resource intensive for IoT devices to handle and even the “light client” protocols have not been resource e cient enough to be practical. We present BlockQuick, a novel protocol for a super-light client, which features reading blockchain data securely from a remote client. BlockQuick requires less data for validation than existing approaches, like PoPoW or FlyClient, while also providing e ective means to protect against eclipse and MITM attacks on the network. BlockQuick clients have low kilobyte RAM requirements, which are optimal for IoT devices and applications with embedded MCUs.

A recent line of research has investigated a new profiling technique based on deep learning as an alternative to the well-known template attack. The advantage of this new profiling approach is twofold: $(1)$ the approximation of the information leakage by a multivariate Gaussian distribution is relaxed (leading to a more generic approach) and $(2)$ the pre-processing phases such as the traces realignment or the selection of the Points of Interest (PoI) are no longer mandatory, in some cases, to succeed the key recovery (leading to a less complex security evaluation roadmap). The related published works have demonstrated that Deep Learning based Side-Channel Attacks (DL-SCA) are very efficient when targeting cryptographic implementations protected with the common side-channel countermeasures such as masking, jitter and random delays insertion. In this paper, we assess the efficiency of this new profiling attack under different realistic and practical scenarios. First, we study the impact of the intrinsic characteristics of the manipulated data-set (\emph{i.e.} distance in time samples between the PoI, the dimensionality of the area of interest and the pre-processing of the data) on the robustness of the attack. We demonstrate that the deep learning techniques are sensitive to these parameters and we suggest some practical recommendations that can be followed to enhance the profiling and the key recovery phases. Second, we discuss the tolerance of DL-SCA with respect to a deviation from the idealized leakage models and provide a comparison with the well-known stochastic attack. Our results show that DL-SCA are still efficient in such a context. Then, we target a more complex masking scheme based on Shamir's secret sharing and prove that this new profiling approach is still performing well. Finally, we conduct a security evaluation of a batch of several combinations of side-channel protections using simulations and real traces captured on the ChipWhisperer board. The experimental results obtained confirm that DL-SCA are very efficient even when a cryptographic implementation combines several side-channel countermeasures.

An important characteristic of recent MPC protocols is an input independent preprocessing phase in which most computations are offloaded, which greatly reduces the execution overhead of the online phase where parties provide their inputs. For a very efficient evaluation of arithmetic circuits in an information-theoretic online phase, the MPC protocols consume Beaver multiplication triples generated in the preprocessing phase. Triple generation is generally the most expensive part of the protocol, and improving its efficiency is the aim of our work. We specifically focus on the semi-honest model and the two-party setting, for which an Oblivious Transfer (OT)-based protocol is the currently best solution. To improve upon this method, we propose a Somewhat Homomorphic Encryption-based protocol. Our experiments show that our protocol is more scalable, and it outperforms the OT-based protocol in most cases, improving communication by up to 6.9x and runtime by up to 3.6x for 64-bit triple generation.

A group-characterizable random variable [Chan and Yeung 2002] is induced by a joint distribution on the (left) cosets of some subgroups of a main group. A homomorphic secret sharing scheme [Benaloh 1986] is called group-homomorphic if the secret and share spaces are groups. We study the connection between these two notions. It is easy to see that a group-characterizable secret sharing with \emph{normal} subgroups in the main group is group-homomorphic. In this paper, we show that the converse holds true as well. A non-trivial consequence of this result is that total and statistical secret sharing coincide for group-homomorphic schemes.

We present a necessary and sufficient condition for a joint distribution to be inherently group-characterizable (i.e., up to a relabeling of the elements of the support). Then, we show that group-homomorphic secret sharing schemes satisfy the sufficient condition and, consequently, they are inherently group-characterizable. We strengthen our result by showing that they indeed have a group characterization with normal subgroups in the main group.

Group-characterizable random variables are known to be quasi-uniform (namely, all marginal distributions are uniform). As an additional contribution, we present an example of a quasi-uniform random variable which is not inherently group-characterizable.

Unlike linear secret sharing, very little is known about abelian secret sharing. In this paper, we present two results on abelian secret sharing. First, we show that the information ratio of access structures (or more generally access functions) remain invariant for the class of abelian schemes with respect to duality. Then, we prove that abelian secret sharing schemes are superior to the linear ones.

New techniques and insight are used to achieve both results. Our result on abelian duality is proved using the notion of Pontryagin duality. The intuition behind the usefulness of this tool is to work with an equivalent definition of linear secret sharing, which is less prevalent in the literature, to make it possible to extend the result on linear duality to abelian duality.

We develop a new method for proving lower bound on the linear information ratio of access structures that can work not only for general linear secret sharing but also for linear schemes on finite fields with a specific characteristic. Unlike the common lower bound techniques, which are usually either based on rank/information inequalities or based on counting/combinatorial-algebraic arguments, our method is linear algebraic in essence. We apply our method to the Fano and non-Fano access structures for the characteristics on which they are not ideal.

We then show in a straightforward way that for their union---a well-known 12-participant access structure---the abelian schemes are superior to the linear ones.

We analyze the digital signatures schemes submitted to NIST's Post-Quantum Cryptography Standardization Project in search for subliminal channels.

Event date: 11 November 2019
Submission deadline: 1 August 2019
Notification: 22 August 2019

We formalize and analyze the general suffix keyed sponge construction, a pseudorandom function built on top of a cryptographic permutation. The construction hashes its data using the (keyless) sponge construction, transforms part of the state using the secret key, and generates the tag from the output of a final permutation call. In its simplest form, if the key and tag size are at most the rate of the sponge, one can see the suffix keyed sponge as a simple sponge function evaluation whose input is the plaintext appended with the key. The suffix keyed sponge is, however, much more general: the key and tag size may exceed the rate without any need to make extra permutation calls. We prove that the suffix keyed sponge construction achieves birthday-bound PRF security in the capacity, even if key and tag size exceed the rate. Furthermore, we prove that if the absorption of the key into the state happens in a leakage resilient manner, the suffix keyed sponge itself is leakage resilient as well. Our findings show that the suffix keyed sponge compares favorably with the hash-then-MAC construction. For instance, to reach a security level of $k$ bits, the side-channel protected component in the suffix keyed sponge just needs to process $k$ bits of input besides the key, whereas schemes following the hash-then-MAC construction need a side-channel protected MAC function that processes $2k$ bits of input besides the key. Moreover, even if we just consider black-box attacks, the MAC function in a hash-then-MAC scheme needs to be cryptographically strong whereas in the suffix keyed sponge the key may be absorbed by a simple XOR. The security proofs are performed using the H-coefficient technique, and make effective use of the multicollision limit function results of Daemen et al. (ASIACRYPT 2017), both for arguing that state manipulation larger than the rate is tolerated after key processing and for upper bounding the amount of leakage an attacker may gain about the secret key.

Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be consider in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.

Smart contracts are self-executing agreements written in program code and are envisioned to be one of the main applications of blockchain technology. While they are supported by prominent cryptocurrencies such as Ethereum, their further adoption is hindered by fundamental scalability challenges. For instance, in Ethereum contract execution suffers from a latency of more than 15 seconds, and the total number of contracts that can be executed per second is very limited. State channel networks are one of the core primitives aiming to address these challenges. They form a second layer over the slow and expensive blockchain, thereby enabling instantaneous contract processing at negligible costs. In this work we present the first complete description of a state channel network that exhibits the following key features. First, it supports virtual multi-party state channels, i.e. state channels that can be created and closed without blockchain interaction and that allow contracts with any number of parties. Second, the worst case time complexity of our protocol is constant for arbitrary complex channels. This is in contrast to the existing virtual state channel construction that has worst case time complexity linear in the number of involved parties. In addition to our new construction, we provide a comprehensive model for the modular design.

Machine learning techniques represent a powerful option in profiling side-channel analysis. Still, there are many settings where their performance is far from expected. In such occasions, it is very important to understand the difficulty of the problem and the behavior of the machine learning algorithm. To that end, one needs to investigate not only the performance of machine learning but also to provide insights into its explainability. One tool enabling us to do this is the bias-variance decomposition where we are able to decompose the predictive error into bias, variance, and noise. With this technique, we can analyze various scenarios and recognize what are the sources of problem difficulty and how additional measurements/features or more complex machine learning models can alleviate the problem. While such results are promising, there are still drawbacks since often it is not easy to connect the performance of side-channel attack and performance of a machine learning classifier as given by the bias-variance decomposition. In this paper, we propose a new tool for analyzing the performance of machine learning-based side-channel attacks -- the Guessing Entropy Bias-Variance Decomposition. With it, we are able to better understand the performance of various machine learning techniques and understand how a change in a setting influences the performance of an attack. To validate our claims, we give extensive experimental results for a number of different settings.

This paper presents the Lattice-based Ring Confidential Transactions (Lattice RingCT v2.0) protocol. Unlike the previous Lattice RingCT v1.0 (LRCT v1.0) protocol, the new protocol supports Multiple-Input and Multiple-Output (MIMO) wallets in transactions, and it is a fully functional protocol construction for cryptocurrency applications such as Hcash. Since the MIMO cryptocurrency setting introduces new balance security requirements (and in particular, security against (out-of-range) amount attacks), we give a refined balance security model to capture such attacks, as well as a refined anonymity model to capture amount privacy attacks. Our protocol extends a previously proposed ring signature scheme in the LRCT v1.0 protocol, to support the MIMO requirements while preserving the post-quantum security guarantees, and uses a lattice-based zero-knowledge range proof to achieve security against (out-of-range) attacks. Preliminary parameter estimates and signature sizes are proposed as a point of reference for future studies.

Post-quantum cryptography has gathered significant attention in recent times due to the NIST call for standardization of quantum resistant public key algorithms. In that context, supersingular isogeny based key exchange algorithm (SIKE) has emerged as a potential candidate to replace traditional public key algorithms like RSA and ECC. SIKE provides $\mathbf{O(\sqrt[4]{p})}$ classical security and $\mathbf{O(\sqrt[6]{p})}$ quantum security where $p$ is the characteristic of the underlying field. Additionally, SIKE has the smallest key sizes among all the post-quantum public algorithm, making it very suitable for bandwidth constrained environment. In this paper, we present an efficient implementation of SIKE protocol for FPGA based applications. The proposed architecture provides the same latency as that of the best existing implementation of SIKE protocol while consuming $48\%$ less DSPs and $58\%$ less block RAM resources. Thus, our design is substantially more efficient compared to that of existing implementations of SIKE.

In this paper, we revisit the generic construction of ring signatures from hash-then-one-way type ($\mathsf{Type-H}$) signatures proposed by Abe et al. (AOS) in 2004 and made the following contributions. First, we give a proof for the generic construction, in a strengthened security model. Previously, this was only done for concrete instantiations, in a weaker model. Second, we extend AOS's framework to generically construct one-time linkable ring signatures from $\mathsf{Type-H}$ signatures and one-time signatures. Lastly, we instantiate the generic construction with an NTRU-based $\mathsf{Type-H}$ signature: Falcon~and obtain a post-quantum linkable ring signature scheme. Our analysis shows that the resulting linkable signature is more efficient than any existing lattice based solutions for small to moderate number of users.

Robustness to modeling attacks is an important requirement for PUF circuits. Several reported Arbiter PUF com- positions have resisted modeling attacks. and often require huge computational resources for successful modeling. In this paper we present deep feedforward neural network based modeling attack on 64-bit and 128-bit Arbiter PUF (APUF), and several other PUFs composed of Arbiter PUFs, namely, XOR APUF, Lightweight Secure PUF (LSPUF), Multiplexer PUF (MPUF) and its variants (cMPUF and rMPUF), and the recently proposed Interpose PUF (IPUF, up to the (4,4)-IPUF configuration). The technique requires no auxiliary information (e.g. side-channel information or reliability information), while employing deep neural networks of relatively low structural complexity to achieve very high modeling accuracy at low computational overhead (compared to previously proposed approaches), and is reasonably robust to error-inflicted training dataset.

Content moderation is crucial for stopping abuse and harassment via messaging on online platforms. Existing moderation mechanisms, such as message franking, require platform providers to see user identifiers on encrypted traffic. These mechanisms cannot be used in messaging systems in which users can hide their identities, such as Signal. The key technical challenge preventing moderation is in simultaneously achieving cryptographic accountability while preserving deniability. In this work, we resolve this tension with a new cryptographic primitive: asymmetric message franking schemes (AMFs). We define strong security notions for AMFs, including the first formal treatment of deniability in moderation settings. We then construct, analyze, and implement an AMF scheme that is fast enough for deployment. We detail how to use AMFs to build content moderation for metadata-private messaging.

An important primitive in ensuring security of modern systems-on-chip designs are protocols for authenticated firmware load. These loaders read a firmware binary image from an untrusted input device, authenticate the image using cryptography and load the image into memory for execution if authentication succeeds. While these protocols are an essential part of the hardware root of trust in almost all modern computing devices, verification techniques for reasoning about end-to-end security of these protocols do not exist.

In this paper, we take a step toward addressing this gap by introducing a system model, adversary model and end-to-end security property that enable reasoning about the security of authenticated load protocols. We then present a decomposition of the security property into two simpler hyperproperties. This decomposition enables more scalable verification. Experiments on a protocol model demonstrate viability of the methodology.

Many cryptocurrencies, such as Bitcoin and Ethereum, do not provide any financial privacy to their users. These systems cannot be used as a medium of exchange as long as they are transparent. Therefore the lack of privacy is the largest hurdle for cryptocurrency mass adoption next to scalability issues. Although many privacy-enhancing schemes had been already proposed in the literature, most of them did not get traction due to either their complexity or their adoption would rely on severe changes to the base protocol. To close this gap, in this work we propose ShareLock, a practical privacy-enhancing tool for cryptocurrencies which is deployable on today's cryptocurrency networks.