International Association
for Cryptologic Research

Superlight blockchain clients learn facts about the blockchain state while requiring merely polylogarithmic communication in the total number of blocks. For proof-of-work blockchains, two known constructions exist: Superblock and FlyClient. Unfortunately, none of them can be deployed to existing blockchains, as they require consensus changes and at least a soft fork to implement. In this paper, we investigate how a blockchain can be upgraded to support superblock clients without a soft fork. We show that it is possible to implement the needed changes without modifying the consensus protocol and by requiring only a minority of miners to upgrade, a process termed a “velvet fork” in the literature. While previous work conjectured that superblock clients can be safely deployed using velvet forks as-is, we show that previous constructions are insecure, and that using velvet techniques to interlink a blockchain can pose insidious security risks. We describe a novel class of attacks, called “chain-sewing”, which arise in the velvet fork setting: an adversary can cut-and-paste portions of various chains from independent temporary forks, sewing them together to fool a superlight client into accepting a false claim. We show how previous velvet fork constructions can be attacked via chain- sewing. Next, we put forth the first provably secure velvet superblock client construction which we show secure against adversaries that are bounded by 1/3 of the upgraded honest miner population. Like non-velvet superlight clients, our approach allows proving generic predicates about chains using infix proofs and as such can be adopted in practice for fast synchronization of transactions and accounts.

When electronic wallets are transferred by more than one party, the level of security can be enhanced by decentralising the distribution of authorisation amongst those parties. Threshold signature schemes enable this functionality by allowing multiple cosigners to cooperate in order to create a joint signature. These cosigners interact to sign a transaction which then confirms that a wallet has been transferred. However, in the event of a post-quantum attack, existing threshold signature schemes that support such an authorisation technique in privacy-preserving cryptocurrency protocols - like Ring Confidential Transaction (RingCT) - would not provide adequate security.

In this paper, we present a new post-quantum cryptographic mechanism, called Lattice-based Linkable Ring Signature with Co-Signing (L2RS-CS), which offers a distributed authorisation feature to protect electronic wallets. A novel security model for L2RS-CS is also formalised to capture the security and privacy requirements to protect transactions in applications to blockchain cryptocurrency protocols, such as the RingCT. To address key-generation security concerns, and to support compression of keys and signatures, the L2RS-CS incorporates a distributed key generation along with a solid public-key aggregation. Finally, we prove the security of our constructed L2RS-CS in the random oracle model and the standard lattice-based Module-SIS hardness assumption.

Diene, Thabet and Yusuf recently proposed a new multivariate signature scheme whose public key is a set of multivariate cubic polynomials over a finite field. This paper studies its security.

Contact discovery allows users of mobile messengers to conveniently connect with people in their address book. In this work, we demonstrate that severe privacy issues exist in currently deployed contact discovery methods.

Our study of three popular mobile messengers (WhatsApp, Signal, and Telegram) shows that, contrary to expectations, large-scale crawling attacks are (still) possible. Using an accurate database of mobile phone number prefixes and very few resources, we have queried 10% of US mobile phone numbers for WhatsApp and 100% for Signal. For Telegram we find that its API exposes a wide range of sensitive information, even about numbers not registered with the service. We present interesting (cross-messenger) usage statistics, which also reveal that very few users change the default privacy settings. Regarding mitigations, we propose novel techniques to significantly limit the feasibility of our crawling attacks, especially a new incremental contact discovery scheme that strictly improves over Signal's current approach.

Furthermore, we show that currently deployed hashing-based contact discovery protocols are severely broken by comparing three methods for efficient hash reversal of mobile phone numbers. For this, we also propose a significantly improved rainbow table construction for non-uniformly distributed inputs that is of independent interest.

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are related to relatively high approximation errors and the complexity of dealing with them.

We present a reduced-error CKKS variant that removes the approximation errors due to the Learning With Errors (LWE) noise in the encryption and key switching operations. We also propose and implement its RNS instantiation that has a lower error than the original CKKS scheme implementation based on multiprecision integer arithmetic. While formulating the RNS instantiation, we develop an intermediate RNS variant that has a smaller approximation error than the prior RNS variant of CKKS. The high-level idea of our main RNS-specific improvements is to remove the approximate scaling error using an automated procedure that computes different scaling factors for each level and performs all necessary adjustments. The rescaling procedure and scaling factor adjustments in our implementation are done automatically and are not exposed to the application developer.

We implement both RNS variants in PALISADE and compare their approximation error and efficiency to the prior RNS variant. Our results for uniform ternary secret key distribution, which is the most efficient setting included in the community homomorphic encryption security standard, show that the reduced-error CKKS RNS implementation typically has an approximation error that is 6 to 9 bits smaller for computations with multiplications than the prior RNS variant. For computations without a multiplication, the approximation error can be up to 20 bits lower than in the prior RNS variant. As compared to the original CKKS using multiprecision integer arithmetic, our reduced-error CKKS RNS implementation has an error that is smaller by 4 and up to 20 bits for computations with multiplications and without multiplications, respectively. For the sparse ternary secret key setting, which was used in the original CKKS paper, the approximate error reduction of reduced-error CKKS w.r.t. original CKKS typically ranges from 6 to 8 bits for computations with multiplications.

Blockchain is the distributed system allowing multiple parties to host a service. Nakamoto Consensus, also named Proof of Work (PoW), is widely used in Bitcoin and other blockchain systems. PoW is an important consensus algorithm. It solves the Byzantine Generals problem in an open network. It also protects the blockchain security from longest chain attack.

World widely virtual currency mining was commonly regarded as over energy consuming. How to make use of the computation capacity provided by mining, is one of the most important problems to solve in blockchain. We extend Proof of Work to be useful and economic. And discover a simple method to generate the proof of storing useful data with PoW. In a blockchain based distributed file storage system, any storage resource owner could freely join as a service provider. It requires the service provider to show the proof of honestly keeping the data content, because the malicious provers may use other's content to generate the proof in order to reduce their resource cost. This is out-sourcing attack. Furtherly, we proposed a novel technique to combine data replica process with Proof of Work's contributing to blockchain security.

Multivariate cryptography studies applications of endomorphisms of K[x_1, x_2, …, x_n] where K is a finite commutative ring given in the standard form x_i →f_i(x_1, x_2,…, x_n), i=1, 2,…, n. The importance of this direction for the constructions of multivariate digital signatures systems is well known. Close attention of researchers directed towards studies of perspectives of quadratic rainbow oil and vinegar system and LUOV presented for NIST postquantum certification. Various cryptanalytic studies of these signature systems were completed. Recently some options to modify theses algorithms as well as all multivariate signature systems which alow to avoid already known attacks were suggested. One of the modifications is to use protocol of noncommutative multivariate cryptography based on platform of endomorphisms of degree 2 and 3. The secure protocol allows safe transfer of quadratic multivariate map from one correspondent to another. So the quadratic map developed for digital signature scheme can be used in a private mode. This scheme requires periodic usage of the protocol with the change of generators and the modification of quadratic multivariate maps. Other modification suggests combination of multivariate map of unbounded degree of size O(n) and density of each f_i of size O(1). The resulting map F in its standard form is given as the public rule. We suggest the usage of the last algorithm on the secure El Gamal mode. It means that correspondents use protocols of Noncommutative Cryptography with two multivariate platforms to elaborate safely a collision endomorphism G: x_i → g_i of linear unbounded degree such that densities of each gi are of size O(n^2). One of correspondents generates mentioned above F and sends F+G to his/her partner. The security of the protocol and entire digital signature scheme rests on the complexity of NP hard word problem of finding decomposition of given endomorphism G of K[x_1,x_2,…,x_n ] into composition of given generators 1^G, 2^G, …t^G, t>1 of the semigroup of End(K[x_1 ,x_2 ,…,x_n]). Differently from the usage of quadratic map on El Gamal mode the case of unbounded degree allows single usage of the protocol because the task to approximate F via interception of hashed messages and corresponding signatures is unfeasible in this case.

Electromagnetic Fault Injection (EMFI) is considered as an effective fault injection technique for the purpose of conducting physical attacks against integrated circuits. It enables an adversary to inject errors on a circuit to gain knowledge of sensitive information or to bypass security features. The aim of this paper is to highlight the design and validation of SiliconToaster, which is a cheap and programmable platform for EM pulse injection. It has been designed using low-cost and accessible components that can be easily found. In addition, it can inject faults with a programmable voltage up to 1.2kV without the need to an external power supply as it is powered by the USB. The second part of the paper invests the SiliconToaster in order to bypass the firmware security protections of an IoT chip. Two security configurations were bypassed sequentially in a non-invasive way (without chip decapsulation).

The postdoc will work alongside Prof. Martin Albrecht and other cryptographic researchers in the ISG on topics in lattice-based cryptography and related fields. This post is funded by a joint grant between Royal Holloway and Imperial College (Dr. Cong Ling) for bridging the gap between lattice-based cryptography and coding theory.

The ISG is a nice place to work; it’s a friendly environment with strong research going on in several areas. We got people working across the field of information security including several people working on cryptography. For example, Carlos Cid, Anamaria Costache, Lydia Garms, Jianwei Li, Sean Murphy, Rachel Player, Eamonn Postlethwaite, Joe Rowell, Fernando Virdia and Martin Albrecht all have looked at or are looking at lattice-based cryptography.

The ISG is one of the largest departments dedicated to information security in the world with 21 core academic staff in the department, as well as research and support staff. We work with many research partners in other departments and have circa 90 PhD students working on a wide range of security research, many of whom are fully funded through our Centre for Doctoral Training in Cyber Security. We have a strong, vibrant, embedded and successful multi-disciplinary research profile spanning from cryptography to systems security and social aspects of security. This vibrant environment incorporates visiting researchers, weekly research seminars, weekly reading groups, PhD seminars and mini conferences, the WISDOM group (Women in the Security Domain Or Mathematics) and we are proud of our collegial atmosphere and approach.

A postdoc here is a 100% research position, i.e. the postdoc would not have teaching duties. That said, if the applicant would like to gain some teaching experience, we can arrange for that as well.

Closing date for applications:

Contact: Martin Albrecht

More information: https://martinralbrecht.wordpress.com/2020/09/17/postdoc-at-royal-holloway-on-lattice-based-cryptography-4/

We are looking for outstanding Post doctoral researchers working on topics related to cryptography and IT Security.

Current topics of interest include (but are not limited to):

• Secure cryptographic implementations
• Leakage/tamper resilient cryptography
• Blockchains and cryptocurrencies
• Distributed cryptography

The application must include a curriculum vitae, a short research statement, and names of 2 contacts that can provide reference about the applicant and her/his work.

The candidate shall be able to show solid expertise in cryptography/IT Security illustrated in form of publications at major crypto/security venues such as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, CHES, FC, ACM CCS, Oakland, USENIX Security, NDSS etc.

The position offers an internationally competitive salary including social benefits. TU Darmstadt is a leading university for Computer Science and offers excellent working environment in the heart of the Rhein-Main metropolitan area. It has a strong institute for research on IT security and cryptography with more than 300 researchers working on all aspects of cybersecurity. Review of applications starts immediately until the position is filled.

Closing date for applications:

Contact: sebastian.faust@cs.tu-darmstadt.de

Event date: 19 October to 20 October 2020

Three Ph.D. positions opening at Dr. Jiafeng Harvest Xie's research group at the Department of Electrical and Computer Engineering of Villanova University, Villanova, PA (west of Philadelphia, USA). The research topics of these positions are focused on cryptographic engineering and fault detection related security analysis. Interested ones are warmly welcomed to apply and send their resume/CV to Dr. Xie through email: jiafeng.xie@villanova.edu

Requirements: preferred to be at the majors of Computer Science or Computer Engineering. Majoring in Mathematics are also ok. Proficiency in programming languages such as C, C++, Python, and so on is needed. Good at English communication and writing. Great enthusiasm of doing research oriented tasks. Excellent team worker.

Degree: both B.S. and M.S. graduates or similar are warmly welcomed to apply.

Deadline: better to start at Spring 2021 (Fall 2021 is also ok). It is always better to apply as early as possible. Positions are open until they are filled.

Closing date for applications:

Contact: Jiafeng Harvest Xie (jiafeng.xie@villanova.edu)

We have an open PhD position in the domain of Scalable and Secure Data Sharing. The prospective candidate is expected to investigate how conventional lightweight symmetric ciphers perform over MPC, as well as benchmark their performance over MPC. The work also entails provable security in this context. The candidate must hold a Master's degree in mathematics / computer science / electrical engineering / cryptography, with strong grades. Strong background in mathematics / computer science / cryptography is expected. Any prior publications and experience in C/C++ and Python are merited.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

We have an open postdoc position in the domain of Scalable and Secure Data Sharing. The prospective candidate is expected to design and develop efficient MPC protocols for privacy-preserving data analytics. The work includes, but not limited to, investigating machine learning algorithms that best suit MPC and that can be efficiently implemented over MPC. You will be working closely with tools such as https://github.com/KULeuven-COSIC/SCALE-MAMBA. The candidate must hold a PhD degree in Cryptography or a related subject with strong publication records in crypto/security venues. In addition to a strong background in both public and symmetric cryptography, good knowledge in MPC, machine learning algorithms, and cryptographic protocols are expected. The candidate should also have coding experience in C/C++ and Python, experience in practical aspects of secure computation is a must.

Closing date for applications:

Contact: jobs-cosic@esat.kuleuven.be

More information: https://www.esat.kuleuven.be/cosic/vacancies/

Verifiable mix nets, and specifically proofs of (correct) shuffle, are a fundamental building block in numerous applications: these zero-knowledge proofs allow the prover to produce a public transcript which can be perused by the verifier to confirm the purported shuffle. They are particularly vital to verifiable electronic voting, where they underpin almost all voting schemes with non-trivial tallying methods. These complicated pieces of cryptography are a prime location for critical errors which might allow undetected modification of the outcome.

The best solution to preventing these errors is to machine-check the cryptographic properties of the design and implementation of the mix net. Particularly crucial for the integrity of the outcome is the soundness of the design and implementation of the verifier (software). Unfortunately, several different encryption schemes are used in many different slight variations which makes t infeasible to machine-check every single case individually. However, a particular optimized variant of the Terelius-Wikstrom mix net is, and has been, widely deployed in elections including national elections in Norway, Estonia and Switzerland, albeit with many slight variations and several different encryption schemes.

In this work, we develop the logical theory and formal methods tools to machine-check the design and implementation of all these variants of Terelius-Wikstrom mix nets, for all the different encryption schemes used; resulting in provably correct mix nets for all these different variations. We do this carefully to ensure that we can extract a formally verified implementation of the verifier (software) which is compatible with existing deployed implementations of the Terelius-Wikstrom mix net. This gives us provably correct implementations of the verifiers for more than half of the national elections which have used verifiable mix nets.

Our implementation of a proof of correct shuffle is the first to be machine-checked to be cryptographically correct and able to verify proof transcripts from national elections. We demonstrate the practicality of our implementation by verifying transcripts produced by the Verificatum mix net system and the CHVote evoting system from Switzerland.

Almost perfect nonlinear functions possess the optimal resistance to the differential cryptanalysis and are widely studied. Most known APN functions are obtained as functions over finite fields $\mathbb{F}_{2^n}$ and very little is known about combinatorial constructions in $\mathbb{F}_2^n$. In this work we proposed two approaches for obtaining quadratic APN functions in $\mathbb{F}_2^n$. The first approach exploits a secondary construction idea, it considers how to obtain quadratic APN function in $n+1$ variables from a given quadratic APN function in $n$ variables using special restrictions on new terms. The second approach is searching quadratic APN functions that have matrix form partially filled with standard basis vectors in a cyclic manner. This approach allowed us to find a new APN function in 7 variables. Also, we conjectured that a quadratic part of an arbitrary APN function has a low differential uniformity. This conjecture allowed us to introduce a new subclass of APN functions, so-called stacked APN functions. We found cubic examples of such functions for dimensions up to 6.

Mixed Integer Linear Programming (MILP) is a powerful tool that helps to automate several cryptanalysis techniques for symmetric key primitives. $\textsf{Gurobi}$ is one of the most popular solvers used by researchers to obtain useful results from the MILP models corresponding to these cryptanalysis techniques. In this report, we provide a cautionary note on the use of $\textsf{Gurobi}$ in the context of bit-based division property integral attacks. In particular, we report four different examples in which $\textsf{Gurobi}$ gives contradictory results when solving the same MILP model by just changing the number of used threads or reordering some constraints.

An efficient scalar multiplication algorithm is a crucial component of elliptic curve cryptosystems. In this paper we propose a scalar multiplication algorithm based on scalar recodings that is regular in nature and provides resistance against simple power analysis attacks. Our scalar multiplication algorithm is made from two scalar recoding algorithms called Recode and Align. Recode is the generalization of the signed non-zero bit recoding algorithm given by Hedabou, Pinel and Beneteau in 2005. It recodes the $k$-$ary$ representation of the given scalar into a signed nonzero form by means of a small lookup table. On the other hand, Align is the generalized $k$-$ary$ version of the sign-aligned columns recoding algorithm given by Faz-Hernandez, Longa and Sanchez in 2014. It recodes the $k$-$ary$ representation of a scalar in such a way that the sign of each of its digits agrees a given $\{1,-1\}$-valued sequence of signs. When analyzing the choice of $k$ in $\{2,3\}$, we find some theoretical evidence that $k=3$ may offer better performance in certain scenarios.

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA and over variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or contain subtle issues in their security proofs.

In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat--Shamir with Aborts paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme. A key step to achieve security (overlooked in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message---which can inevitably happen in the Fiat--Shamir with Aborts setting. We manage to do so using lattice-based homomorphic commitments as constructed by Baum et al. (SCN 2018).

We first propose a three-round $n$-out-of-$n$ signature from Module-LWE with tight security (using ideas from lossy identification schemes). Then, we further reduce the complexity to two rounds, at the cost of relying on Module-SIS as an additional assumption, losing tightness due to the forking lemma, and requiring somewhat more expensive trapdoor commitments. The construction of suitable trapdoor commitments from lattices is a side contribution of this paper. Finally, we also obtain a two-round multi-signature scheme as a variant of our two-round $n$-out-of-$n$ protocol.

At a combined computational expense of about $6{\ell}$ field operations, V\'elu's formulae are used to construct and evaluate degree-$\ell$ isogenies in the vast majority of isogeny-based primitive implementations. Recently, Bernstein, de Feo, Leroux and Smith introduced a new approach for solving this same problem at a reduced cost of just $\tilde{O}(\sqrt{\ell})$ field operations. In this work, we present a concrete computational analysis of these novel formulae, along with several algorithmic tricks that helped us to slightly, but noticeably, reduce their practical cost. Furthermore, we report a Python-3 implementation of several instantiations of CSIDH and B-SIDH using a combination of the novel formulae and an adaptation of the optimal strategies commonly used in the SIDH/SIKE protocols. Compared to a traditional V\'elu constant-time implementation of CSIDH, our experimental results report a saving of 5.357\%, 13.68\% and 25.938\% base field operations for CSIDH-512, CSIDH-1024, and CSIDH-1792, respectively. Additionally, the first implementation of the B-SIDH scheme in the open literature is reported here.