International Association
for Cryptologic Research

Braid groups are infinite non-abelian groups naturally arising from geometric braids that have been used in cryptography for the last two decades. In braid group cryptography public braids often contain secret braids as a factor and it is hoped that rewriting the product of braid words hides the individual factors. We provide experimental evidence that this is in general not the case and argue that under certain conditions parts of the Garside normal form of factors can be found in the Garside normal form of their product. This observation can be exploited to decompose products in braid groups of the form $ABC$ when only $B$ is known.

Our decomposition algorithm yields a universal forgery attack on WalnutDSA^TM, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptographic algorithms. Our attack on WalnutDSA^TM can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments.

Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.

An attempt to derive signer-efficient digital signatures from aggregate signatures was made in a signature scheme referred to as Structure-free Compact Rapid Authentication (SCRA) (IEEE TIFS 2017). In this paper, we first mount a practical universal forgery attack against the NTRU instantiation of SCRA by observing only 8161 signatures. Second, we propose a new signature scheme (FAAS), which transforms any single-signer aggregate signature scheme into a signer-efficient scheme. We show two efficient instantiations of FAAS, namely, FAAS-NTRU and FAAS-RSA, both of which achieve high computational efficiency. Our experiments confirmed that FAAS schemes achieve up to 100x faster signature generation compared to their underlying schemes. Moreover, FAAS schemes eliminate some of the costly operations such as Gaussian sampling, rejection sampling, and exponentiation at the signature generation that are shown to be susceptible to side-channel attacks. This enables FAAS schemes to enhance the security and efficiency of their underlying schemes. Finally, we prove that FAAS schemes are secure (in random oracle model), and open-source both our attack and FAAS implementations for public testing purposes.

In a recent paper Faonio, Nielsen and Venturi (ICALP 2015) gave new constructions of leakage-resilient signature schemes. The signature schemes proposed remain unforgeable against an adversary leaking arbitrary information on the entire state of the signer, including the random coins of the signing algorithm. The main feature of their signature schemes is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. The notion, put forward by Nielsen, Venturi, and Zottarel (PKC 2014), defines a slack parameter $\gamma$ which, roughly speaking, describes how gracefully the security degrades. Unfortunately, the standard-model signature scheme of Faonio,Nielsen and Venturi has a slack parameter that depends on the number of signatures queried by the adversary.

In this paper we show two new constructions in the standard model where the above limitation is avoided. Specifically, the first scheme achieves slack parameter $O(1/\lambda)$ where $\lambda$ is the security parameter and it is based on standard number theoretic assumptions, the second scheme achieves optimal slack parameter (i.e. $\gamma = 1$) and it is based on knowledge of the exponent assumptions. Our constructions are efficient and have leakage rate $1 - o(1)$, most notably our second construction has signature size of only 8 group elements which makes it the leakage-resilient signature scheme with the shortest signature size known to the best of our knowledge.

Proofs of liabilities are used for applications, function like banks or Bitcoin exchanges, to prove the sums of money in their dataset that they should owe. The Maxwell protocol, a cryptographic proof of liabilities scheme which relies on a data structure well known as the summation Merkle tree, utilizes a Merkle approach to prove liabilities in the decentralized setting, i.e., clients independently verify they are in the dataset with no trusted auditor. In this paper, we go into the Maxwell protocol and the summation Merkle tree. We formalize the Maxwell protocol and show it is not secure. We present an attack with which the proved liabilities using the Maxwell protocol are less than the actual value. This attack can have significant consequences: A Bitcoin exchange controlling a total of $n$ client accounts can present valid liabilities proofs including only one account balance in its dataset. We suggest two improvements to the Maxwell protocol and the summation Merkle tree, and present a formal proof for the improvement that is closest in spirit to the Maxwell protocol. Moreover, we show the DAM scheme, a micropayment scheme of Zerocash which adopts the Maxwell protocol as a tool to disincentivize double/multiple spending, is vulnerable to an multi-spending attack. We show the Provisions scheme, which adopts the Maxwell protocol to extend its privacy-preserving proof of liabilities scheme, is also infected by a similar attack.

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an adversary learns a bounded amount of leakage, where each bit of leakage can depend jointly on the shares of an adaptively chosen subset of $p$ parties. A lot of works have focused on designing secret sharing schemes that handle individual and (mostly) non-adaptive leakage for (some) threshold secret sharing schemes [DP07,DDV10,LL12,ADKO15,GK18,BDIR18].

We give an unconditional compiler that transforms any standard secret sharing scheme with arbitrary access structure into a $p$-party leakage-resilient one for $p$ logarithmic in the number of parties. This yields the first secret sharing schemes secure against adaptive and joint leakage for more than two parties.

As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing} and build such schemes for general access structures. We empower the computationally unbounded adversary to adaptively leak from the shares and then use the leakage to tamper with each of the shares arbitrarily and independently. Leveraging our $p$-party leakage-resilient schemes, we also construct such non-malleable secret sharing schemes: any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of Goyal and Kumar (CRYPTO 2018) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found several applications in cryptography [LL12,ADKO15,GKPRS18,GK18,CL18,OPVV18].

Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient $p$-party leakage-resilient schemes for $p$ upto $O(\log n)$ as our share sizes have exponential dependence on $p$. We observe that improving this dependence from $2^{O(p)}$ to $2^{o(p)}$ will lead to progress on longstanding open problems in complexity theory.

We construct a genus 2 curve inside the product of 2 elliptic curves. The formula for this construction has appeared in a previous paper. The current paper discusses how this formula arises naturally by using some theory of elliptic Kummer surfaces

Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key. It is important to note that, the proxy which performs the re-encryption learns nothing about the message encrypted under either public keys. Due to its transformation property, proxy re-encryption schemes have practical applications in distributed storage, encrypted email forwarding, Digital Rights Management (DRM) and cloud storage. From its introduction, several proxy re-encryption schemes have been proposed in the literature, and a majority of them have been realized using bilinear pairing. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the scheme. We also present the first collusion-resistant pairing-free unidirectional proxy re-encryption scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

Proof-of-Stake (PoS) protocols have been actively researched for the past few years. PoS finds direct applicability in permissionless blockchain platforms and emerges as one of the strongest candidates to replace the largely inefficient Proof of Work mechanism that is currently plugged in the majority of existing permissionless blockchain systems. Although a number of PoS variants have been proposed, these protocols suffer from a number of security shortcomings. Namely, most existing PoS variants are either subject to the nothing at stake, the long range, or the stake grinding attacks which considerably degrade security in the blockchain. These shortcomings do not result from a lack of foresight when designing these protocols, but are inherently due to the ease of manipulating "stake" when compared to other more established variants, such as "work". In this paper, we address these problems and propose a secure Proof of Stake protocol, PoTS, that leverages Trusted Execution Environments (TEEs), such as Intel SGX, to ensure that each miner can generate at most one block per "height" for strictly increasing heights—thus thwarting the problem of nothing at stake and a large class of long-range attacks. In combination with TEEs, PoTS additionally uses cryptographic techniques to also prevent grinding attacks and protect against posterior corruption. We show that our protocol is secure, in the sense of well-established cryptographic notions for blockchain protocols, down to realistic hardware assumptions on TEE and well-established cryptographic assumptions. Finally, we evaluate the performance of our proposal by means of implementation. Our evaluation results show that PoTS offers a strong tradeoff between security of performance of the underlying PoS protocol.

So far, the topic of merged mining has mainly been considered in a security context, covering issues such as mining power centralization or crosschain attack scenarios. In this work we show that key information for determining blockchain metrics such as the fork rate can be recovered through data extracted from merge mined cryptocurrencies. Specifically, we reconstruct a long-ranging view of forks and stale blocks in Bitcoin from its merge mined child chains, and compare our results to previous findings that were derived from live measurements. Thereby, we show that live monitoring alone is not sufficient to capture a large majority of these events, as we are able to identify a non-negligible portion of stale blocks that were previously unaccounted for. Their authenticity is ensured by cryptographic evidence regarding both, their position in the respective blockchain, as well as the Proof-of-Work difficulty.

Furthermore, by applying this new technique to Litecoin and its child cryptocur rencies, we are able to provide the first extensive view and lower bound on the stale block and fork rate in the Litecoin network. Finally, we outline that a recovery of other important metrics and blockchain characteristics through merged mining may also be possible.

This paper proposes two closely related asymmetric key (or a public key) schemes for key exchange whose security is based on the notion of ideal secrecy. In the first scheme, the private key consists of two singular matrices, a polar code matrix and a random permutation matrix all over the binary field. The sender transmits addition of two messages over a public channel using the public key of the receiver. The receiver can decrypt individual messages using the private key. An adversary, without the knowledge of the private key, can only compute multiple equiprobable solutions in a space of sufficiently large size related to the dimension of the kernel of the singular matrices. This achieves security in the sense of ideal secrecy. The next scheme extends over general matrices. The two schemes are cryptanalyzed against various attacks.

We present Ouroboros Crypsinous, the first privacy-preserving proof-of-stake (PoS) blockchain protocol. To model its security we give a thorough treatment of private ledgers in the universal composition (UC) setting that might be of independent interest. To prove our protocol secure against adaptive attacks, which are particularly critical in the PoS setting, we introduce a new coin evolution technique that relies on a SNARKs mechanism and key-private forward secure encryption. The latter primitive---and the associated construction---can be of independent interest. We stress that existing approaches to private blockchains, such as the proof-of-work-based Zerocash are analyzed only against static corruptions.

Cloud storage enables its users to store confidential information as encrypted files in the cloud. A cloud user (say Alice) can share her encrypted files with another user (say Bob) by availing proxy re-encryption services of the cloud. Proxy Re-Encryption (PRE) is a cryptographic primitive that allows transformation of ciphertexts from Alice to Bob via a semi-trusted proxy, who should not learn anything about the shared message. Typically, the re-encryption rights are enabled only for a bounded, fixed time and malicious parties may want to decrypt or learn messages encrypted for Alice, even beyond that time. The basic security notion of PRE assumes the proxy (cloud) is semi-trusted, which is seemingly insufficient in practical applications. The proxy may want to collude with Bob to obtain the private keys of Alice for later use. Such an attack is called collusion attack, allowing colluders to illegally access all encrypted information of Alice in the cloud. Hence, achieving collusion resistance is indispensable to real-world scenarios. Realizing collusion-resistant PRE has been an interesting problem in the ID-based setting. To this end, several attempts have been made to construct a collusion-resistant IB-PRE scheme and we discuss their properties and weaknesses in this paper. We also present a new collusion-resistant IB-PRE scheme that meets the adaptive CCA security under the decisional bilinear Diffie-Hellman hardness assumption and its variant in the random oracle model.

The Coefficients H Technique (also called H-technique), by Patarin, is a tool to obtain upper bound on the distinguishing advantage. The tool is known for providing quite simpler and tight bound proofs as compared to some other well-known tools such as Game-playing technique and Random Systems methodology. In this paper, we aim to provide a brief survey on the H-technique. The survey is in three parts: First, we redevelop the necessary nomenclatures and tools required to study the security of symmetric key designs. Second, we give a full description of the H-technique and show that it can provide optimal bounds on the distinguishing advantage. Third, we give simpler proofs for some popular symmetric key designs, across different paradigms, using the H-technique.

Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian's randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian's randomization after encoding, the complexity of the best attacks is significantly increased for CLT13. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude.

As an application, we describe the first concrete implementation of non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange based on CLT13 that is resistant against the Cheon et al. attack. For N=4 users and a medium (62 bits) level of security, our implementation requires 8 GB of public parameters, and a few minutes for the derivation of a shared key. Without Kilian's randomization of encodings our construction would be completely unpractical, as it would require more than 100 TB of public parameters.

Direct Anonymous Attestation (DAA) is an anonymous signature scheme, which is designed to allow the Trusted Platform Module (TPM), a small chip embedded in a host computer, to attest to the state of the host system, while preserving the privacy of the user. DAA provides two signature modes: fully anonymous signatures and pseudonymous signatures. To generate a DAA signature, the calculations are divided between the TPM and the host. One goal for designing new DAA schemes is to reduce the signing burden on the TPM as much as possible, since the TPM has only limited resources when compared to the host and the computational overhead of the TPM dominates the whole signing performance. In an optimal DAA scheme, the signing workload on the TPM will be no more than that required for a normal signature. DAA has developed about fifteen years, but no scheme has achieved this optimal signing efficiency for both signature modes. In this paper, we propose the first DAA scheme which achieves this optimal TPM signing efficiency for both signature modes. In particular, the TPM takes only a single exponentiation in a prime-order group when generating a DAA signature. Additionally, this single exponentiation can be precomputed, which enables our scheme to achieve fast online signing time. Our DAA scheme is provably secure under the DDH, DBDH and q-SDH assumptions in the Universally Composable (UC) security model. Our scheme can be implemented using the existing TPM 2.0 commands, and thus is compatible with the TPM 2.0 specification. There are three important use cases for DAA: quoting platform configuration register values, certifying a key and signing a message. We have implemented and benchmarked the commands needed for these use cases on an Infineon TPM 2.0 chip. Based on these benchmark results, our scheme is about twice as fast as the existing DAA schemes supported by TPM 2.0 in terms of signing efficiency. In addition, our DAA scheme supports selective attribute disclosure, which can satisfy more application requirements. We also extend our DAA scheme to support signature-based revocation and to guarantee privacy against subverted TPMs. The two extended DAA schemes keep the TPM signing efficiency optimal for both signature modes, and outperform existing related schemes in terms of signing performance.

This paper introduces Freestyle, a randomized, and variable round version of the ChaCha cipher. Freestyle demonstrates the concept of hash based halting condition, where a decryption attempt with an incorrect key is likely to take longer time to halt. This makes it resistant to key-guessing attacks i.e. brute-force and dictionary based attacks. Freestyle uses a novel approach for ciphertext randomization by using random number of rounds for each block of message, where the exact number of rounds are unknown to the receiver in advance. Due to its inherent random behavior, Freestyle provides the possibility of generating up to $2^{256}$ different ciphertexts for a given key, nonce, and message; thus resisting key and nonce reuse attacks. This also makes cryptanalysis through known-plaintext, chosen-plaintext, and chosen-ciphertext attacks difficult in practice. Freestyle is highly customizable, which makes it suitable for both low-powered devices as well as security-critical applications. It is ideal for: (i) applications that favor ciphertext randomization and resistance to key-guessing and key reuse attacks; and (ii) situations where ciphertext is in full control of an adversary for carrying out an offline key-guessing attack.

To deal with message streams, which is required by many symmetric cryptographic functionalities (MAC, AE, HASH), we propose a lightweight round function called Thin Sponge. We give a framework to construct all these functionalities (MAC, AE, and HASH) using the same Thin Sponge round function. Besides the common security assumptions behind traditional symmetric algorithms, the security of our schemes depends on the hardness of problems to find collisions of some states. We give a class of constructions of Thin Sponge, which is improvement of the round function of Trivium and ACORN. We give simple criteria for determining parameters. According to these criteria, we give an example, which achieves all functionalities in a single round function and hence can be realized by the same hardware. Our algorithm is also efficient in software.

A landmark security property of smart contracts is liquidity: in a non-liquid contract, it may happen that some funds remain frozen. The relevance of this issue is witnessed by a recent liquidity attack to the Ethereum Parity Wallet, which has frozen 160M USD within the contract, making this sum unredeemable by any user. We address the problem of verifying liquidity of Bitcoin contracts. Focussing on itML, a contracts DSL with a computationally sound compiler to Bitcoin, we study various notions of liquidity. Our main result is that liquidity of BitML contracts is decidable, in all the proposed variants. To prove this, we first transform the infinite-state semantics of BitML into a finite-state one, which focusses on the behaviour of any given set of contracts, abstracting the moves of the context. With respect to the chosen contracts, this abstraction in sound and complete. Our decision procedure for liquidity is then based on model-checking the finite space of states of the abstraction. The computational soundness of the BitML compiler allows to lift this result from the symbolic to the computational level: if our decision procedure establishes that a contract is liquid, then it will be such also under a computational adversary, and vice versa.

The Cryptology Group at CWI in Amsterdam has an opening for a PhD position (4 yrs) in the area of ``mathematical aspects of cryptology,`` e.g., the intersection between algebraic coding theory and secure multiparty computation. The successful applicant will also be part of the Mathematical Institute, Leiden University.

Requirements:

You should hold a Master degree (or expect to obtain it soon) in mathematics or computer science (or a comparable subject) with excellent grades, and you should have successfully demonstrated your research abilities, e.g. by completion of an (undergraduate) research project with outstanding results. Furthermore, preferably, you:

• have some background in cryptography;

• enjoy mathematics;

• possess good academic writing and presentation skills;

• are fluent in spoken and written English.

Application:

Your application should include the following information:

• a curriculum vitae;

• a letter of motivation (at most 1 page) explaining why you are interested in this position;

• a list of all university courses taken, including a transcript of grades;

• a report from an undergraduate research project you have done;

• the name and contact details (including email address) of two to three referees who can provide details about your profile (one of whom should be the main supervisor of your Master thesis).

The applications will be reviewed upon receipt and until the position is filled.

Closing date for applications: 1 February 2019

Contact: Please send your application to Ronald Cramer (CWI & Leiden U) and Serge Fehr (CWI & Leiden U), using ``Application CWI PhD Position`` as subject. Email: {cramer,fehr} (at) cwi.nl

We have 1 year Post-doc Position on Constraint Programming for Cryptanalysis of Symmetric Encryption Schemes in LIMOS, Clermont-Ferrand, France

Your Profile:

A PhD in Computer Science, Applied Mathematics, Cryptography or related field.

Competitive research record in symmetric cryptography or in constraint programming.

Commitment, team working and a critical mind.

Fluent written and verbal communication skills in English are essential

Closing date for applications: 1 September 2019

Contact: email your cover letter, your CV, your PhD, reports of the reviewers of your PhD, a selection of your best papers related to the post-doc offer, some recommandation

letters, contact information for 3 referees and any information that might help us to choose you.

More information: http://sancy.univ-bpclermont.fr/~lafourcade/post-doc-LIMOS.pdf