International Association
for Cryptologic Research

Lattice signature schemes generally require particular care when it comes to preventing secret information from leaking through signature transcript. For example, the Goldreich-Goldwasser-Halevi (GGH) signature scheme and the NTRUSign scheme were completely broken by the parallelepiped-learning attack of Nguyen and Regev. Several heuristic countermeasures were also shown vulnerable to similar statistical attacks.

At PKC~2008, Plantard, Susilo and Win proposed a new variant of GGH, informally arguing resistance to such attacks. Based on this variant, Plantard, Sipasseuth, Dumondelle and Susilo proposed a concrete signature scheme, called DRS, that has been accepted in the round 1 of the NIST post-quantum cryptography project.

In this work, we propose yet another statistical attack and demonstrate a weakness of the DRS scheme: one can recover some partial information of the secret key from sufficiently many signatures. One difficulty is that, dued to the DRS reduction algorithm, the relation between the statistical leak and the secret seems more intricate. We work around this difficulty by training a statistical model, using a few features that we designed according to a simple heuristic analysis.

While we only recover partial information on the secret key, this information is easily exploited by lattice attacks, significantly decreasing their complexity. Concretely, we claim that, provided that $100\,000$ signatures are available, the secret key may be recovered using BKZ-$138$ for first set of DRS parameters submitted to the NIST. This puts the security level of this parameter set below $80$-bits (maybe even $70$ bits), for an original claim of $128$-bits.

In this paper, we connect two interesting problems in the domain of Information-Theoretic Cryptography: "Non-malleable Codes" and "Privacy Amplification". Non-malleable codes allow for encoding a message in such a manner that any "legal" tampering will either leave the message in the underlying tampered codeword unchanged or unrelated to the original message. In the setting of Privacy Amplification, we have two users that share a weak secret $w$ guaranteed to have some entropy. The goal is to use this secret to agree on a fully hidden, uniformly distributed, key $K$, while communicating on a public channel fully controlled by an adversary.

While lot of connections have been known from other gadgets to NMCs, this is the first result to show an application of NMCs to any information-theoretic primitive (other than tamper resilient circuits). Specifically, we give a general transformation that takes any augmented non-malleable code and builds a privacy amplification protocol. This leads to the following results:

(a) Assuming the existence of constant rate, optimal error (we say an $\epsilon$-(augmented) NMC has optimal error if $\epsilon$ = $2^{-O(message\ length)}$), two-state augmented non-malleable code there exists a $8$-round privacy amplification protocol with optimal entropy loss and min-entropy requirement $\Omega(\log(n)+ \kappa)$ (where $\kappa$ is the security parameter). In fact, "non-malleable randomness encoders" suffice.

(b) Instantiating our construction with the current best known augmented non-malleable code for $2$-split-state family [Li17], we get a $8$-round privacy amplification protocol with entropy loss $O(\log(n)+ \kappa \log (\kappa))$ and min-entropy requirement $\Omega(\log(n) +\kappa\log (\kappa))$.

AEGIS is an authenticated cipher introduced at SAC 2013, which takes advantage of AES-NI instructions to reach outstanding speed in software. Like LEX, Fides, as well as many sponge-based designs, AEGIS leaks part of its inner state each round to form a keystream. In this paper, we investigate the existence of linear biases in this keystream. Our main result is a linear mask with bias $2^{-89}$ on the AEGIS-256 keystream. The resulting distinguisher can be exploited to recover bits of a partially known message encrypted $2^{188}$ times, regardless of the keys used. We also consider AEGIS-128, and find a surprising correlation between ciphertexts at rounds $i$ and $i+2$, although the biases would require $2^{140}$ data to be detected. Due to their data requirements, neither attack threatens the practical security of the cipher.

In this paper we present a novel attack based on photonic emission analysis targeting software implementations of AES. We focus on the particular case in which the attacker can collect the photonic emission of a limited number of sense amplifiers (e.g. only one) of the SRAM storing the S-Box. The attack consists in doing hypothesis on the secret key based on the knowledge of the partial output of the SubBytes operation. We also consider the possibility to attack a masked implementation of AES using the photonic emission analysis. In the case of masking, the attacker needs 2 leakages of the same encryption to overcome the randomization of the masks. For our analysis, we assume the same physical setup described in other previous works. Reported results are based on simulations with some hypothesis on the probability of photonic emission of a single transistor.

In an anonymous subscription system (ASS), a subscribed user (SU) is able to access the services of a service provider without having to reveal its true identity. For a SU computing platform that is compliant with the Trusted Platform Module (TPM) standard, direct anonymous attestation (DAA) is an appropriate cryptographic protocol for realizing ASS, since DAA enables privacy-preserving authentication of the SU platform. This approach takes advantage of a cryptographic key that is securely embedded in the platform's hardware. Although the computing industry and academia have made significant strides in developing secure and sound DAA schemes, these schemes share a common drawback that may act as a major obstacle to their widespread deployment. In all of the existing schemes, the SU suffers from significant computational and communication costs that increase proportionally to the size of the revocation list. This drawback renders the existing schemes to be impractical when the size of the revocation list grows beyond a relatively modest size. In this paper, we propose a novel scheme called Lightweight Anonymous Subscription with Efficient Revocation (LASER) that addresses this very problem. In LASER, the computational and communication costs of the SU's signature are multiple orders of magnitude lower than the prior art. LASER achieves this significant performance improvement by shifting most of the computational and communication costs from the DAA's online procedure (i.e., signature generation) to its offline procedure (i.e., acquisition of keys/credentials). We have conducted a thorough analysis of LASER's performance-related features and compared the findings to the prior art. We have also conducted a comprehensive evaluation of LASER by implementing it on a laptop platform with an on-board TPM. To the best of our knowledge, the results presented in this paper represent the first implementation and analysis of a scheme using an actual TPM cryptoprocessor that is compliant with the most recent TPM specification version 2.0. We have thoroughly analyzed the security of LASER in the random oracle model.

Privacy-preserving data analysis in the context of federated databases distributed across multiple parties has the potential to produce richer and more accurate models than what each party can learn with their own data. Secure Multi-Party Computation (MPC) offers a robust cryptographic approach to this problem, and in fact several protocols have been proposed for various learning tasks on parametric models. In this paper we focus on $k$-NN, shifting the attention towards non-parametric models. We tackle several challenges arising in privacy-preserving $k$-NN classification on federated databases, and implement a concrete protocol for document classification. Our solution is faster than the state-of-the-art custom MPC protocol by at least one an order of magnitude.

Currently several traceable (or linkable) identity-based ring signature schemes have been proposed. However, most of them are constructed in the random oracle model. In this paper, we present a fully traceable ring signature (TRS) scheme without random oracles, which has the constant size signature and a security reduction to the computational Diffie-Hellman (CDH) assumption. Also, we give a formal security model for traceable ring signature and prove that the proposed scheme has the properties of traceability and anonymity.

This paper presents a secure cloud storage scheme based on hybrid cryptosystem, which consists of Elliptic Curve Cryptography (ECC), Advanced Encryption Standard (AES), and one-way hash function. Here, the data owner exports large volume of encrypted data to a cloud storage provider. The exported encrypted data is over-encrypted by the cloud storage provider, and the data is sent to the requesting user. An existing hybrid cryptosystem based dynamic key management scheme with hierarchical access control has been incorporated in our scheme. The key management scheme groups users in various security classes, and helps to derive efficiently, as well as directly the secret keys of the lower order security classes. The incorporated key management scheme in our proposed scheme incurs low computational, communication, and storage overheads for key generation, and derivation purposes. The security analysis, and the simulation results run on the AVISPA tool (formal security verification tool) show that the proposed scheme is protected from the adversaries. This scheme is useful in `owner-write-users-read' application areas, and the end users may use resource-constrained wireless mobile devices securely in this proposed scheme.

Increasingly connectivity becomes integrated in products and devices that previously operated in a stand-alone setting. This observation holds for many consumer ap- plications in the so-called "Internet of Things" (IoT) as well as for corresponding industry applications (IIoT), such as industrial process sensors. Often the only practicable means for authentication of human users is a weak password. The security of password-based authentication schemes frequently form the weakest point of the security infrastructure. In this paper we first expose, why a tailored protocol designed for the IIoT use case is considered necessary. The differences between IIoT and to the conventional Internet use-cases result in largely modified threats and require special procedures for allowing both, convenient and secure use in the highly constrained industrial setting. Specifically the use of a verifier-based password-authenticated key-exchange (V-PAKE) protocol as a hedge against public-key-infrastructure (PKI) failures is considered important. Availability concerns for the case of failures of (part of) the communication infrastructure makes local storage of access credentials mandatory. The larger threat of physical attacks make it important to use memory-hard password hashing. This paper presents a corresponding tailored protocol AuCPace together with a security proof within the Universal Composability (UC) framework considering fully adaptive adversaries. We also introduce a new security notion of partially augmented PAKE that provides specific performance advantages and allows, thus, for suitability for a larger set of IIoT applications. We also present an actual instantiation of our protocol, AuCPace25519, and present performance results on ARM Cortex-M0 and Cortex-M4 microcontrollers. Our implementation realizes new speed-records for PAKE and X25519 Diffie-Hellman for the ARM Cortex M4 architecture.

Event date: 14 September to 15 September 2018
Submission deadline: 13 April 2018

Third-party applications on Facebook can collect personal data of the users who install them, but also of their friends. This raises serious privacy issues as these friends are not notified by the applications nor by Facebook, and they have not given consent. This paper presents a detailed multi-faceted study of the collateral information collection of the applications on Facebook. To investigate the views of the users, we designed a questionnaire and collected the responses of 114 participants. The results show that participants are concerned about the collateral information collection and in particular about the lack of notification and of mechanisms to control the data collection. Based on real data, we compute the likelihood of collateral information collection affecting users: we show that the probability is significant and greater than 80% for popular applications such as TripAdvisor. We also demonstrate that a substantial amount of profile data can be collected by applications, which enables application providers to profile users. To investigate whether collateral information collection is an issue to users’ privacy we analysed the legal framework in light of the new General Data Protection Regulation. We provide a detailed analysis of the entities involved and investigate which entity is accountable for the collateral information collection. To provide countermeasures, we propose a privacy dashboard extension that implements privacy scoring computations to enhance transparency towards collateral information collection. Furthermore, we discuss alternative solutions highlighting other countermeasures such as notification and access control mechanisms, cryptographic solutions and application auditing. To the best of our knowledge, this is the first work that provides a detailed multi-faceted study of this problem and that analyses the threat of user profiling by application providers.

It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. In 2013, Bhasin et al. studied the minimum Hamming weight of $d$-CI Boolean functions, and presented an open problem: the minimal weight of a $d$-CI function in $n$ variables might not increase with $n$. Very recently, Carlet and Chen proposed some constructions of low-weight CI functions, and gave a conjecture on the minimum Hamming weight of $3$-CI functions in $n$ variables.

In this paper, we determine the values of the minimum Hamming weights of $d$-CI Boolean functions in $n$ variables for infinitely many $n$'s and give a negative answer to the open problem proposed by Bhasin et al. We then present a method to construct minimum-weight 2-CI functions through Hadamard matrices, which can provide all minimum-weight 2-CI functions in $4k-1$ variables. Furthermore, we prove that the Carlet-Chen conjecture is equivalent to the famous Hadamard conjecture. Most notably, we propose an efficient method to construct low-weight $n$-variable CI functions through $d$-linearly independent sets, which can provide numerous minimum-weight $d$-CI functions. Particularly, we obtain some new values of the minimum Hamming weights of $d$-CI functions in $n$ variables for $n\leq 13$. We conjecture that the functions constructed by us are of the minimum Hamming weights if the sets are of absolute maximum $d$-linearly independent. If our conjecture holds, then all the values for $n\leq 13$ and most values for general $n$ are determined.

In this paper we propose a rank based algorithm for sorting encrypted data using monomials. Greedy Sort is a sorting technique that achieves to minimize the depth of the homomorphic evaluations. It is a costly algorithm due to excessive ciphertext multiplications and its implementation is cumbersome. Another method Direct Sort has a slightly deeper circuit than Greedy Sort, nevertheless it is simpler to implement and scales better with the size of the input array. Our proposed method minimizes both the circuit depth and the number of ciphertext multiplications. In addition to its performance, its simple design makes it more favorable compared to the alternative methods which are hard to parallelize, e.g. not suitable for fast GPU implementations. Furthermore, we improve the performance of homomorphic sorting algorithm by adapting the SIMD operations alongside message slot rotation techniques. This method allow us to pack $N$ integers into a single ciphertext and compute $N$ comparisons at once, thus reducing $\mathcal{O}(N^2)$ comparisons to $\mathcal{O}(N)$.

We propose a security model for authenticated key establishment in the quantum setting. Our model is the first for authenticated key establishment that allows for quantum superpositions of queries. The model builds on the classical Canetti-Krawczyk model but allows quantum interactions between the adversary and quantum oracles that emulate classical parties. We demonstrate that this new security definition is satisfiable by giving a generic construction from simpler cryptographic primitives and a specific protocol which is secure in the quantum random oracle model, under the supersingular isogeny decisional Diffie-Hellman assumption (SIDH).

The notion of Functional Encryption (FE) has recently emerged as a strong primitive with several exciting applications. In this work, we initiate the study of the following question: Can existing public key encryption schemes be ``upgraded'' to Functional Encryption schemes without changing their public keys or the encryption algorithm? We call a public-key encryption with this property to be FE-compatible.

Indeed, assuming ideal obfuscation, it is easy to see that every CCA-secure public-key encryption scheme is FE-compatible. Despite the recent success in using indistinguishability obfuscation to replace ideal obfuscation for many applications, we show that this phenomenon most likely will not apply here. We show that assuming fully homomorphic encryption and the learning with errors (LWE) assumption, there exists a CCA-secure encryption scheme that is provably not FE-compatible. We also show that a large class of natural CCA-secure encryption schemes proven secure in the random oracle model are not FE-compatible in the random oracle model.

Nevertheless, we identify a key structure that, if present, is sufficient to provide FE-compatibility. Specifically, we show that assuming sub-exponentially secure iO and sub-exponentially secure one way functions, there exists a class of public key encryption schemes which we call Special-CCA secure encryption schemes that are in fact, FE-compatible.

In particular, each of the following popular CCA secure encryption schemes (some of which existed even before the notion of FE was introduced) fall into the class of Special-CCA secure encryption schemes and are thus FE-compatible:

1) The scheme of Canetti, Halevi and Katz (Eurocrypt 2004) when instantiated with the IBE scheme of Boneh-Boyen (Eurocrypt 2004). 2) The scheme of Canetti, Halevi and Katz (Eurocrypt 2004) when instantiated with any Hierarchical IBE scheme. 3) The scheme of Peikert and Waters (STOC 2008) when instantiated with any Lossy Trapdoor Function.

By design, existing (pre-processing) zk-SNARKs embed a secret trapdoor in a relation-dependent common reference strings (CRS). The trapdoor is exploited by a (hypothetical) simulator to prove the scheme is zero knowledge, and the secret-dependent structure facilitates a linear-size CRS and linear-time prover computation. If known by a real party, however, the trapdoor can be used to subvert the security of the system. The structured CRS that makes zk-SNARKs practical also makes deploying zk-SNARKS problematic, as it is difficult to argue why the trapdoor would not be available to the entity responsible for generating the CRS. Moreover, for pre-processing zk-SNARKs a new trusted CRS needs to be computed every time the relation is changed. %

In this paper, we address both issues by proposing a model where a number of users can update a universal CRS. The updatable CRS model guarantees security if at least one of the users updating the CRS is honest. We provide both a negative result, by showing that zk-SNARKs with private secret-dependent polynomials in the CRS cannot be updatable, and a positive result by constructing a zk-SNARK based on a CRS consisting only of secret-dependent monomials. The CRS is of quadratic size, is updatable, and is universal in the sense that it can be specialized into one or more relation-dependent CRS of linear size with linear-time prover computation.

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The caveat is that this worst case problem is only mildly hard and in particular admits a quasi-polynomial time algorithm, whereas the LPN variant used in the reduction requires extremely high noise rate of $1/2-1/poly(n)$. Thus we can only show that ``very hard'' LPN is harder than some ``very mildly hard'' worst case problem.

Specifically, we consider the (n,m,w)-nearest codeword problem ($(n,m,w)$-NCP) which takes as input a generating matrix for a binary linear code in $m$ dimensions and rank $n$, and a target vector which is very close to the code (Hamming distance at most $w$), and asks to find the codeword nearest to the target vector. We show that for balanced (unbiased) codes and for relative error $w/m \approx {\log^2 n}/{n}$, $(n,m,w)$-NCP can be solved given oracle access to an LPN distinguisher with noise ratio $1/2-1/poly(n)$.

Our proof relies on a smoothing lemma for codes which we show to have further implications: We show that $(n,m,w)$-NCP with the aforementioned parameters lies in the complexity class $\text{Search-BPP}^{SZK}$ (i.e. reducible to a problem that has a statistical zero knowledge protocol) implying that it is unlikely to be $\mathcal{NP}$-hard. We then show that LPN with very low noise rate $\log^2(n)/n$ implies the existence of collision resistant hash functions (our aforementioned result implies that in this parameter regime LPN is also in $\text{BPP}^\text{SZK})$.

In this work we explore a combinatorial optimization problem stemming from the Naccache-Stern cryptosystem. We show that solving this problem results in bandwidth improvements, and suggest a polynomial-time approximation algorithm to find an optimal solution.

Our work suggests that using optimal radix encoding results in an asymptotic 50% increase in bandwidth.

This technical report discusses three subtleties related to the widely used notion of differential privacy (DP). First, we discuss how the choice of a distinguisher influences the privacy notion and why we should always have a distinguisher if we consider approximate DP. Secondly, we draw a line between the very intuitive probabilistic differential privacy (with probability $1-\delta$ we have $\varepsilon$-DP) and the commonly used approximate differential privacy ($(\varepsilon,\delta)$-DP). Finally we see that and why probabilistic differential privacy (and similar notions) are not complete under post-processing, which has significant implications for notions used in the literature.

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary's queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension.

In this work, we give a new QROM proof technique that overcomes this ``recording barrier''. Our central observation is that when viewing the adversary's query and the oracle itself in the Fourier domain, an oracle query switches from writing to the adversary's space to writing to the oracle itself. This allows a reduction to simulate the oracle by simply recording information about the adversary's query in the Fourier domain.

We then use this new technique to show the indifferentiability of the Merkle-Damgard domain extender for hash functions. Given the threat posed by quantum computers and the push toward quantum-resistant cryptosystems, our work represents an important tool for efficient post-quantum cryptosystems.