International Association
for Cryptologic Research

In Attribute-Based Signatures (ABS; first defined by Maji, Prabhakaran and Rosulek, CT-RSA 2011) an authority can generate multiple signing keys, where each key is associated with an attribute $x$. Messages are signed with respect to a constraint $f$, such that a key for $x$ can sign messages respective to $f$ only if $f(x) = 0$. The security requirements are unforgeability and key privacy (signatures should not expose the specific signing key used). In (single-hop) Homomorphic Signatures (HS; first defined by Boneh and Freeman, PKC 2011), given a signature for a data-set $x$, one can evaluate a signature for the pair $(f(x),f)$, for functions $f$. In context-hiding HS, evaluated signatures do not reveal information about the original (pre-evaluated) signatures.

In this work we start by showing that these two notions are in fact equivalent. The first implication of this equivalence is a new lattice-based ABS scheme for polynomial-depth circuits, based on the HS construction of Gorbunov, Vaikuntanathan and Wichs (GVW; STOC 2015).

We then construct a new ABS candidate from a worst case lattice assumption (SIS), with different parameters. Using our equivalence again, now in the opposite direction, our new ABS implies a new lattice-based HS scheme with different parameter trade-off, compared to the aforementioned GVW.

In PETS 2015, Kiayias, Leonardos, Lipmaa, Pavlyk, and Tang proposed the first $(n, 1)$-CPIR protocol with rate $1 - o (1)$. They use advanced techniques from multivariable calculus (like the Newton-Puiseux algorithm) to establish optimal rate among a large family of different CPIR protocols. It is only natural to ask whether one can achieve similar rate but with a much simpler analysis. We propose parameters to the earlier $(n, 1)$-CPIR protocol of Lipmaa (ISC 2005), obtaining a CPIR protocol that is asymptotically almost as communication-efficient as the protocol of Kiayias et al. However, for many relevant parameter choices, it is slightly more communication-efficient, due to the cumulative rounding errors present in the protocol of Kiayias et al. Moreover, the new CPIR protocol is simpler to understand, implement, and analyze. The new CPIR protocol can be used to implement (computationally inefficient) FHE with rate $1 - o (1)$.

The Universal 2nd Factor (U2F) protocol is an open authentication standard to strengthen the two-factor authentication which is required to protect our authentication details online. It augments the existing password based infrastructure by using a specialized USB (termed as U2F authenticator) as the 2nd factor. In this work we show why the U2F protocol is not secure against side channel attacks. In U2F, at the time of manufacturing, the U2F authenticator is assigned fixed keys namely the device secret key and the attestation private key. These secret keys are later used by the U2F authenticator during the Registration phase to encrypt and provide digital signature to crucial informations that will help in proper validation of the user and the web server. However, the use of fixed keys for the above processing leaks information through side channel about both the secrets. We present a countermeasure for side channel attack based on re-keying technique to prevent the repeated use of the device secret key for the encryption purposes and thus prevents side channel attack. We also recommend a modification in the existing U2F protocol to minimise the effect of signing with the fixed attestation private key. Incorporating our proposed countermeasure and recommended modification, we then present a new variant of the existing U2F protocol that we believe will provide strong security guarantees in the current existing scheme.

We propose some new baby-step giant-step algorithms for computing "low-weight" discrete logarithms; that is, for computing discrete logarithms in which the radix-b representation of the exponent is known to have only a small number of nonzero digits. Prior to this work, such algorithms had been proposed for the case where the exponent is known to have low Hamming weight (i.e., the radix-2 case). Our new algorithms (i) improve the best-known deterministic complexity for the radix-2 case, and then (ii) generalize from radix-2 to arbitrary radixes b>1. We also discuss how our new algorithms can be used to attack several recent Verifier-based Password Authenticated Key Exchange (VPAKE) protocols from the cryptographic literature with the conclusion that the new algorithms render those constructions completely insecure in practice.

The secure storage of long-lived sensitive data is constantly growing in its relevance due to the ever increasing digitization of documents. One very important challenge of this research field is to provide confidentiality for the stored data even in the long term. The only known approach to achieve this, as required, for instance, for medical records, is to use proactive secret sharing. However, all currently known schemes suffer from being inefficient. They require information-theoretic secure communication channels between any two shareholders and between the client and each shareholder and come with a high communication complexity. Thus, this work addresses the scenario where only a subset of servers holding shares is connected via private channels. Furthermore, it is sufficient if there is only one private channel between the client and one shareholder. In addition to improving practicability the presented proactive secret sharing solution, called EPSS, performs data aggregation to provide an efficient solution with respect to the communication complexity. Nevertheless, it still provides unconditional confidentiality for the data at rest and towards external attackers eavesdropping the communication channels.

Typically, when secrecy multiplication is performed in multiparty computation using Shamir’s (k,n) threshold secret sharing scheme, the result is a polynomial with degree of 2k-2 instead of k-1. This causes a problem where, in order to reconstruct a multiplication result, the number of polynomials needed will increase from k to 2k-1. Shingu et al. proposed a method to solve the problem that the degree of polynomial increases when secrecy multiplication is performed by using the (scalar value×polynomial) approach instead of the typical (polynomial×polynomial). However, this method is not secure when a combination operation, such as a product-sum operation, is performed. In this paper, we propose a multiparty computation that uses a secret sharing scheme that is secure against a product-sum operation but does not increase the degree of polynomial of the output. We prove that all combinations of the basic operations (addition, subtraction, multiplication, and division) can be performed securely using this scheme. We also propose three preconditions and finally show that our proposed method is information-theoretic secure against a passive adversary.

The XOR-Encrypt-XOR (XEX) block cipher mode was introduced by Rogaway in 2004. XEX mode uses nonce-based secret masks $(L)$ that are distinct for each message. The existence of secret masks in XEX mode prevents the application of conventional fault attack techniques, such as differential fault analysis. This work investigates other types of fault attacks against XEX mode that either eliminate the effect of the secret masks or retrieve their values. Either of these outcomes enables existing fault attack techniques to then be applied to recover the secret key. To estimate the success rate and feasibility, we ran simulations for ciphertext-only fault attacks against 128-bit AES in XEX mode. The paper discusses also the relevance of the proposed fault attacks to certain authenticated encryption modes based on XEX, such as OCB2, OTR, COPA, SHELL and ElmD. Finally, we suggest effective countermeasures to provide resistance to these fault attacks.

In this paper, we construct an anonymous and decentralized cryptocash protocol which is secure in the quantum computation model. In order to achieve that, a linkable ring signature based on the ideal lattice is proposed. The size of a signature in our scheme is O(log N ), where N is the number of participants in the ring. The framework of our cryptocash system follows that of CryptoNote with some modications. By adopting the logarithmic size quantum resistant linkable ring signature scheme, our protocol is ecient and anonymous. We also introduce how to generate the verifying and signing key pairs of the linkable ring signature temporarily. With these techniques, both the sender and the receiver's privacy in transactions are protected even though they are published in the public ledger.

We build a privacy-preserving deep learning system in which many learning participants perform neural network-based deep learning over a combined dataset of all, without actually revealing the participants' local data. To that end, we revisit the previous work by Shokri and Shmatikov (ACM CCS 2015) and point out that local data information may be actually leaked to an honest-but-curious server. We then move on to fix that problem via building an enhanced system with following properties: (1) no information is leaked to the server; and (2) accuracy is kept intact, compared to that of the ordinary deep learning system also over the combined dataset.

Our system is a bridge between deep learning and cryptography: we utilise stochastic gradient descent (SGD) applied to neural networks, in combination with additively homomorphic encryption. We show that our usage of encryption adds tolerable overhead to the ordinary deep learning system.

We introduce two new cryptographic notions in the realm of public and symmetric key encryption.

Encryption with invisible edits is an encryption scheme with two tiers of users: "privileged" and "unprivileged". Privileged users know a key pair $(pk, sk)$ and "unprivileged" users know a key pair $(pk_e, sk_e)$ which is associated with an underlying edit $e$ to be applied to messages encrypted. Each key pair on its own works exactly as in standard public-key encryption, but when an unprivileged user attempts to decrypt a ciphertext generated by a privileged user of an underlying plaintext $m$, it will be decrypted to an edited $m' = Edit(m,e)$. Here, $Edit$ is some supported edit function and $e$ is a description of the particular edit to be applied. For example, we might want the edit to overwrite several sensitive blocks of data, replace all occurrences of one word with a different word, airbrush an encrypted image, etc. A user shouldn't be able to tell whether he's an unprivileged or a privileged user.

An encryption with deniable edits is an encryption scheme which allows a user who owns a ciphertext $c$ encrypting a large corpus of data $m$ under a secret key $sk$, to generate an alternative but legitimate looking secret key $sk_{e,c}$ that decrypts $c$ to an "edited" version of the data $m'=Edit(m,e)$. This generalizes classical receiver deniable encryption, which can be viewed as a special case of deniable edits where the edit function performs a complete replacement of the original data. The new flexibility allows us to design solutions with much smaller key sizes than required in classical receiver deniable encryption, and in particular allows the key size to only scale with the description size of the edit $e$ which can be much smaller than the size of the plaintext data $m$.

We construct encryption schemes with deniable and invisible edits for any polynomial-time computable edit function under minimal assumptions: in the public-key setting we only require the existence of standard public-key encryption and in the symmetric-key setting we only require the existence of one-way functions.

The solutions to both problems use common ideas, however there is a significant conceptual difference between deniable edits and invisible edits. Whereas encryption with deniable edits enables a user to modify the meaning of a single ciphertext in hindsight, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts.

Secure Instant Messaging (SIM) is utilized in two variants: one-to-one communication and group communication. While the first variant has received much attention lately (Frosch et al., EuroS&P16; Cohn-Gordon et al., EuroS&P17; Kobeissi et al., EuroS&P17), little is known about the cryptographic mechanisms and security guarantees of SIM group communication.

In this paper, we investigate group communication security mechanisms of three main SIM applications: Signal, WhatsApp, and Threema. We first provide a comprehensive and realistic attacker model for analyzing group SIM protocols regarding security and reliability. We then describe and analyze the group protocols used in Signal, WhatsApp, and Threema. By applying our model, we reveal multiple weaknesses, and propose generic countermeasures to enhance the protocols regarding the required security and reliability goals. Our systematic analysis reveals that (1) the communications’ integrity – represented by the integrity of all exchanged messages – and (2) the groups’ closeness – represented by the members’ ability of managing the group – are not end-to-end protected.

We additionally show that strong security properties, such as Future Secrecy which is a core part of the one-to-one communication in the Signal protocol, do not hold for its group communication.

Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces $K^n$ over general commutative ring $K$ of increasing with $n$ order can be used in the key exchange protocols and related to them El Gamal multivariate cryptosystems. We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via the usage of conjugations for two polynomials of kind $g^k$ and $g^{-1}$ given by key holder (Alice) or giving them as elements of different transformation groups. We present key exchange protocols based on twisted discrete logarithms problem which uses noncommutativity of semigroup. Recent results on the existence of families of stable transformations of prescribed degree and density and exponential order over finite fields can be used for the implementation of schemes as above with feasible computational complexity. We introduce an example of a new implemented quadratic multivariate cryptosystem based on the above mentioned ideas.

Event date: 10 September to 14 September 2017

In the framework of a H2020 program of the European Commission, Intelligent Voice Ltd is receiving financial support to hire a postdoctoral researcher for one year on the following topic :

The cloud offers an ideal opportunity for storing large volumes of data. However, the storage of sensitive data such as speech in plain text format on the cloud is not permitted in many industry sectors such as finance, health care etc. Hence speech data should be encrypted before storage on the cloud, and because it contains biometric identifiers it must remain encrypted. The challenge then is to search over large amounts of encrypted speech and return encrypted search results that can be decrypted by the user only. Intelligent Voice are providers of the world\'s fastest speech to text engine, and we are looking for a talented researcher in semantic security and searchable encryption to join our research team. This post builds on existing research within Intelligent Voice on Searchable and Homomorphic cryptographic protocols for speech processing.

Applicants should have already completed, or be close to completing, a PhD in computer science, mathematics, or a related discipline. Applicants should have an excellent research track record demonstrated by publications at major cryptography/security venues, and should have significant experience in the design and deployment of cryptographic protocols.

To apply please send your CV (with publication list), a 1-page cover letter, and the names of at least two people who can provide reference letters (e-mail).

Closing date for applications: 31 August 2017

Contact: Gérard Chollet, Head of Research, Intelligent Voice Ltd

St Clare House, 30-33 Minories, London EC3N 1BP

gerard.chollet(at)intelligentvoice.com

Phone: +44 20 3627 2670

More information: http://www.intelligentvoice.com/

Event date: 3 November to 5 November 2017
Notification: 15 September 2017

Composability and robustness against physical defaults (e.g., glitches) are two highly desirable properties for secure implementations of masking schemes. While tools exist to guarantee them separately, no current formalism enables their joint investigation. In this paper, we solve this issue by introducing a new model, the robust probing model, that is naturally suited to capture the combination of these properties. We first motivate this formalism by analyzing the excellent robustness and low randomness requirements of first-order threshold implementations, and highlighting the difficulty to extend them to higher orders. Next, and most importantly, we use our theory to design higher-order secure, robust and composable multiplication gadgets. While admittedly inspired by existing approaches to masking (e.g., Ishai-Sahai-Wagner-like, threshold, domain-oriented), these gadgets exhibit subtle implementation differences with these state-of-the-art solutions (none of which being provably composable and robust). Hence, our results illustrate how sound theoretical models can guide practically-relevant implementations.

A group of $n$ users want to run a distributed protocol $\pi$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $\pi$, is able to maliciously flip bits on the channels. Can we efficiently simulate $\pi$ in the presence of such an adversary?

We show that this is possible, even when $L$, the number of bits sent in $\pi$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $\pi$ that 1) fails with probability at most $\delta$, for any $\delta > 0$; and 2) sends $\tilde{O}(L+T)$ bits, where the $\tilde{O}$ notation hides a $\log(nL/\delta)$ term multiplying $L$.

Additionally, we show how to improve this result when the average message size $\alpha$ is not constant. In particular, we give an algorithm that sends $O(L(1 + (1/\alpha) \log(nL/\delta) + T )$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $\alpha$. We note that if $\alpha$ is $\Omega (log(nL/\delta))$, then this improved algorithm sends only $O(L + T)$ bits, and is therefore within a constant factor of optimal.

The advent of large-scale quantum computers has resulted in significant interest in quantum-safe cryptographic primitives. Lattice-based cryptography is one of the most attractive post-quantum cryptographic families due to its well-understood security, efficient operation and versatility. However, LWE-based schemes are still relatively bulky and slow. In this work, we present spKEX, a forward-secret, post-quantum, unauthenticated lattice-based key-exchange scheme that combines four techniques to optimize performance. spKEX relies on Learning with Rounding (LWR) to reduce bandwidth; it uses sparse and ternary secrets to speed up computations and reduce failure probability; it applies an improved key reconciliation scheme to reduce bandwidth and failure probability; and computes the public matrix A by means of a permutation to improve performance while allowing for a fresh A in each key exchange. For a quantum security level of 128 bits, our scheme requires 32\% lesser bandwidth than the LWE-based key-exchange proposal Frodo and allows for a fast implementation of the key exchange.

We make a number of remarks about the AES-GCM-SIV nonce-misuse resistant authenticated encryption scheme currently considered for standardization by the Crypto Forum Research Group (CFRG). First, we point out that the security analysis proposed in the ePrint report 2017/168 is incorrect, leading to overly optimistic security claims. We correct the bound and re-assess the security guarantees offered by the scheme for various parameters. Second, we suggest a simple modification to the key derivation function which would improve the security of the scheme with virtually no efficiency penalty.

Linear regression is an important statistical tool that models the relationship between some explanatory values and an outcome value using a linear function. In many current applications (e.g. predictive modelling in personalized healthcare), these values represent sensitive data owned by several different parties that are unwilling to share them. In this setting, training a linear regression model becomes challenging and needs specific cryptographic solutions. In this work, we propose a new system that can train a linear regression model with 2-norm regularization (i.e. ridge regression) on a dataset obtained by merging a finite number of private datasets. Our system is composed of two phases: The first one is based on a simple homomorphic encryption scheme and takes care of securely merging the private datasets. The second phase is a new ad-hoc two-party protocol that computes a ridge regression model solving a linear system where all coefficients are encrypted. The efficiency of our system is evaluated both on synthetically generated and real-world datasets.