International Association
for Cryptologic Research

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.

In this paper, we introduce the syntax and security notions of multi-adjustable join (M-Adjoin) schemes as an extension of the adjustable join (Adjoin) schemes [Popa-Zeldovich 2012]. An M-Adjoin is a symmetric-key primitive that enables a user to securely outsource his database to a server, and later to privately issue the join queries for a list of column labels (instead of a pair in an Adjoin scheme). The security definitions of Adjoin [Mironov-Segev-Shahaf 2017] extends to M-Adjoin in a straightforward way. It turns out that even though the 3Partition security does capture the minimal leakage of an Adjoin scheme, it does not carry the expected minimal leakage of an M-Adjoin scheme. We propose a new security notion for this purpose, which we refer to as M3Partition. The gap between 3Partition and M3Partition is filled with a sequence $\{\textrm{M3Pk}\}_{k \in N}$ of security definitions where $\textrm{M3P}_1$ and $\textrm{M3P}_{\infty}$, respectively, correspond to 3Partition and M3Partition. We propose constructions for achieving both M3Partition and M3Pk security levels. Our M3Partition-secure scheme joins m columns, each containing $n$ elements, in time $O(n^{(m-1)})$ with minimal leakage. Our M3Pk-secure scheme uses ideas from secret sharing in its construction and does the job in time $O((m - 1)\cdot n^k/k)$ with some leakage that we refer to as the k-monotonous leakage. It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient (both in computation and storage) than the previous ones due to the type of pairing (asymmetric vs symmetric) and the hardness assumption that we rely on. Additionally, we present some separation results between different security definitions, which were left open in previous works.

Event date: 28 June 2019

Event date: 1 July to 2 July 2019

Event date: 15 December to 18 December 2019
Submission deadline: 1 August 2019
Notification: 1 October 2019

Bootstrapping of FHE over the integer with large message is a open problem, which is to evaluate double modulo $(c ~\text{mod}~ p )~\mod~ Q$ arithmetic homomorphically for large $Q$. In this paper, we express this double modulo reduction circuit as a arithmetic circuit of degree at most $\theta^2 \log^2\theta/2$, with $O(\theta \log^2\theta)$ multiplication gates, where $\theta= \frac{\lambda}{\log \lambda}$ and $\lambda$ is the security parameter. The complexity of decryption circuit is independent of the message space size $Q$ with a constraint $Q> \theta \log^2\theta/2$.

Though it is well known that the roots of any affine polynomial over finite field can be computed by a system of linear equations by using a normal base of the field, such solving approach appears to be difficult to apply when the field is fairly large. Thus, it may be of great interest to find explicit representation of the solutions independently of the field base. This was previously done only for quadratic equations over binary finite field. This paper gives explicit representation of solutions for much wider class of affine polynomials over binary prime field.

Recently one new key recovery method for a filter generator was proposed. It is based on so-called planar approximations of such a generator. This paper contains the numerical part of the research of the Boolean functions properties which allow to protect the generator against this method. The main theoretical part of this research is presented at the CTCrypt 2019 conference.

We give a number of approaches which, to a newcomer, may seem like natural ways to attack the SIDH/SIKE protocol, and explain why each of these approaches seems to fail, at least with the specific setup and parameters of SIKE. Our aim is to save some time for others who are looking to assess the security of SIDH/SIKE. We include methods that fail to attack the pure isogeny problem, namely: looking at the $\mathbb F_p$-subgraph, lifting to characteristic zero, and using Weil restrictions. We also include methods that fail to make use of the public 2-power and 3-power torsion points, namely: interpolation techniques, any purely group-theoretic approaches, and constructing an endomorphism à la Petit to exploit the auxiliary points, but with balanced parameters.

This paper generalizes the notable Galbrath's test by introducing the general reciprocity law on function fields. With the help of the extended Galbrath's test, we show the scheme of Boneh, LaVigne and Sabin (BLS) is not anonymous in general. BLS's scheme naturally generalizes Cocks' scheme to higher power residue symbols, but it is less efficient, bandwidth-wise because computing $e$-th power residue symbols is really time-consuming and ciphertexts are expressed as polynomials. We improve the efficiency of BLS's scheme through taking off the part of computing $e$-th power residue symbols in the encryption phase. Our construction also widens BLS's scheme to the case $e$ is square-free. Finally, we provide some methods for computing $e$-th power residue symbols in order to make our scheme more efficient.

How much we say, to whom, and when, is inherently telling, even if the contents of our communication is unclear. In other words: encryption is not enough; neither to secure privacy, nor to maintain confidentiality. Years ago Adi Shamir already predicted that encryption will be bypassed. And it has. The modern dweller of cyber space is routinely violated via her data behavior. Also, often an adversary has the power to compel release of cryptographic keys over well-exposed communication. The front has shifted, and now technology must build cryptographic shields beyond content, and into pattern, even as to existence of communication. We present here tools, solutions, methods to that end. They are based on equivocation. If a message is received by many recipients, it hides the intended one. If a protocol calls for decoy messages, then it protects the identity of the sender of the contents-laden message. BitGrey is a protocol that creates a "grey hole" (of various shades) around the communicating community, so that very little information leaks out. In addition the BitLoop protocol constructs a fixed rate circulating bit flow, traversing through all members of a group. The looping bits appear random, and effectively hide the pattern, even the existence of communication within the group.

In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We compute the security of the families presented by Fotiadis and Konstantinou in [13], compute some new families, and compare the efficiency of both of these with the (adjusted) BLS, KSS, and BN families, and with the new families of [19]. Finally, we present an optimal pairing-friendly elliptic curve for security level 128 and recommend two pairing-friendly elliptic curves for security level 192.

Pseudorandom functions are traditionally built upon block ciphers, but with the trend of permutation based cryptography, it is a natural question to investigate the design of pseudorandom functions from random permutations. We present a generic study of how to build beyond birthday bound secure pseudorandom functions from public random permutations. We first show that a pseudorandom function based on a single permutation call cannot be secure beyond the $2^{n/2}$ birthday bound, where n is the state size of the function. We next consider the Sum of Even-Mansour (SoEM) construction, that instantiates the sum of permutations with the Even-Mansour construction. We prove that SoEM achieves tight $2n/3$-bit security if it is constructed from two independent permutations and two randomly drawn keys. We also demonstrate a birthday bound attack if either the permutations or the keys are identical. Finally, we present the Sum of Key Alternating Ciphers (SoKAC) construction, a translation of Encrypted Davies-Meyer Dual to a public permutation based setting, and show that SoKAC achieves tight $2n/3$-bit security even when a single key is used.