International Association
for Cryptologic Research

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for $f < n/3$ by Berman et al. but a considerable gap remains for $n/3 \le f < n/2$.

This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message $M$, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed $M$, even though the verifier will not see---let alone verify---all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.

After defining compact certificates, we demonstrate an efficient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50--280$\times$ smaller and 300--4000$\times$ cheaper to verify than a natural baseline approach.

Smart grid has improved the security, efficiency of the power system and balanced the supply and demand by intelligent management, which enhanced stability and reliability of power grid. The key point to achieve them is real-time data and consume data sharing by using fine-grained policies. But it will bring the leakage of the privacy of the users and losing of control over data for data owners. The reported solutions can not give the best trade-off among the privacy protection, control over the data shared and confidentiality. In addition, they can not solve the problems of large computation overhead and dynamic management such as users’ revocation. This paper aims at these problems and proposes a decentralized attribute-based data sharing scheme. The proposed scheme ensures the secure sharing of data while removing the central authority and hiding user’s identity information. It uses attribute-based signcryption(ABSC) to achieve data confidentiality and authentication. Under this model, attribute-based encryption gives the access policies for users and keeps the data confidentiality, and the attribute-based signature is used for authentication of the primary ciphertextintegrity. It is more efficient than ”encrypt and then sign” or ”sign and then encrypt”. In addition, the proposed scheme enables user’s revocation and public verifiability. Under the random oracle model, the security and the unforgeability against adaptive chosen message attack are demonstrated.

Though Mobile Cloud Computing (MCC) and Mobile Edge Computing (MEC) technologies have brought more convenience to mobile services over past few years, but security concerns like mutual authentication, user anonymity, user untraceability, etc., have yet remained unresolved. In recent years, many efforts have been made to design security protocols in the context of MCC and MEC, but most of them are prone to security threats. In this paper, we analyze Jia et al.’s scheme, one of the latest authentication protocols for MEC environment and we show this scheme is vulnerable to user impersonation and ephemeral secret leakage attacks. Further, we demonstrate that the aforementioned attacks can be similarly applied to Li et al.’s scheme which recently derived from Jia et al.’s protocol. In this paper, we propose a provably secure authenticated key agreement protocol on the basis of Jia et al.’s scheme that not only withstands security weaknesses of it, but also offers low computational and communicational costs compared to the other related schemes. As a formal security proof, we simulate our scheme with widely used AVISPA tool. Moreover, we show the scalability and practicality of our scheme in a MEC environment through NS-3 simulation.

Several Central Bank Digital Currency (CBDC) projects are considering the development of a digital currency that is managed on a permissioned blockchain, i.e. only authorized entities are involved in transactions verification. In this paper, we explore the best possible balance between privacy and accountability in such a traceable digital currency. Indeed, in case of suspicion of fraud or money laundering activity, it is important to enable the retrieval of the identity of a payer or a payee involved in a specific transaction. Based on a preliminary analysis of achievable anonymity properties in a transferable, divisible and traceable digital currency systems, we first present a digital currency framework along with the corresponding security and privacy model. Then, we propose a pairing-free traceable digital currency system that reconciles user's privacy protection and accountability. Our system is proven secure in the random oracle model.

Prime integers form the basis for finite field and elliptic curve cryptography, as well as many other applications. Provable prime generation guarantees primality and is more efficient than probabilistic generation, and provides components for an efficient primality proof. This paper details a protocol which takes in the proof components from the generation process, proves primality, and as an added benefit, supplies the user with a subgroup generator.

A verifiable timed signature (VTS) scheme allows one to time-lock a signature on a known message for a given amount of time $T$ such that after performing a sequential computation for time $T$ anyone can extract the signature from the time-lock. Verifiability ensures that anyone can publicly check if a time-lock contains a valid signature on the message without solving it first, and that the signature can be obtained by solving the same for time $T$.

This work formalizes VTS, presents efficient constructions compatible with BLS, Schnorr, and ECDSA signatures, and experimentally demonstrates that these constructions can be employed in practice. On a technical level, we design an efficient cut-and-choose protocol based on the homomorphic time-lock puzzles to prove the validity of a signature encapsulated in a time-lock puzzle. We also present a new efficient {range proof} protocol that significantly improves upon existing proposals in terms of the proof size, and is also of independent interest.

While VTS is a versatile tool with numerous existing applications, we demonstrate VTS's applicability to resolve three novel challenging issues in the space of cryptocurrencies. Specifically, we show how VTS is the cryptographic cornerstone to construct: (i) Payment channel networks with improved on-chain unlinkability of users involved in a transaction, (ii) multi-party signing of transactions for cryptocurrencies without any on-chain notion of time and (iii) cryptocurrency-enabled fair multi-party computation protocol.

In this paper, we completely study two classes of Boolean functions that are suited for hybrid symmetric-FHE encryption with stream ciphers like FiLIP. These functions (which we call homomorphic-friendly) need to satisfy contradictory constraints: 1) allow a fast homomorphic evaluation, and have then necessarily a very elementary structure, 2) be secure, that is, allow the cipher to resist all classical attacks (and even more, since guess and determine attacks are facilitated in such framework). Because of constraint 2, these functions need to have a large number of variables (often more than 1000), and this makes even more difficult to satisfy constraint 1 (hence the interest of these two classes). We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes and we give close bounds for the others (fast algebraic immunity, dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in classes of a sufficient cryptographic interest.

Private stream aggregation (PSA) allows an untrusted data aggregator to compute statistics over a set of multiple participants' data while ensuring the data remains private. Existing works rely on a trusted party to enable an aggregator to achieve offline fault tolerance, but in the real world this may not be practical. We develop a new framework that supports PSA in a way that is robust to online user faults, while still supporting a strong guarantee on each individual’s privacy. We first must define a new level of security in the presence of online faults and malicious adversaries because the existing definition does not account for online faults. After this we describe a general framework that allows existing work to reach this new level of security. Furthermore, we develop the first protocol that provably reaches this level of security by leveraging trusted hardware. After we develop a methodology to outsource computationally intensive work to higher performance devices, while still allowing for strong privacy, we reach new levels of scalability and communication efficiency over existing work seeking to support offline fault tolerance, and achieve differential privacy.

CPU caches are a powerful source of information leakage. To develop practical cache-based attacks, there is an increasingly need to automate the process of finding exploitable cache-based side-channels in computer systems. Cache template attack is a generic technique that utilizes Flush+Reload attack in order to automatically exploit cache vulnerability of Intel platforms. Cache template attack on T-table-based AES implementation consists of two phases including the profiling phase and the key exploitation phase. Profiling is a preprocessing phase to monitor dependencies between the secret key and behavior of the cache memory. In addition, the addresses of T-tables can be obtained automatically. In the key exploitation phase, most significant bits (MSBs) of the secret key bytes are retrieved by monitoring exploitable addresses. In this paper, we propose a simple yet effective searching technique which accelerates the profiling phase by a factor of at most 64. To verify the theoretical model of our technique, we implement the described attack on AES. The experimental results showed the profiling phase runtime of the cache template attack is around 10 minutes while our method speeds up the running of this phase to around 9 seconds.

We have a vacancy for a PhD Candidate at NTNU, in the Department of Information Security and Communication Technology (IIK), in the area of cryptography. The candidate will work in the general areas of privacy-preserving computation, lattice-based cryptography and post-quantum cryptography. This will be under the supervision of Dr. Anamaria Costache, in the cryptography team at NTNU. The cryptography team at NTNU is heavily involved in research in these areas, and so the successful candidate will benefit from a good research support system. A good work environment is characterized by diversity. We encourage qualified candidates to apply, regardless of their gender, functional capacity or cultural background. If you have any questions about the position, please contact Dr. Anamaria Costache, Anamaria.costache@ntnu.no. If you have any questions about the recruitment process, please contact HR officer Stine Terese Ruen Nymoen, stine.t.r.nymoen@ntnu.no. For a detailed description of the requirements, please go the link below. Application deadline 25/01/2021.

Closing date for applications:

Contact: Dr. Anamaria Costache, anamaria.costache@ntnu.no

More information: https://www.jobbnorge.no/en/available-jobs/job/197509/phd-candidate-in-cryptography

Applications are invited for a research intern position at the IMDEA Software Institute, Madrid, Spain. The successful applicant will work under the supervision of Ignacio Cascudo in a project in the area of cryptography, where the topic will be related to mathematical aspects of privacy-preserving protocols such as secure multiparty computation protocols, secret sharing or zero knowledge proofs.

Who should apply?
Applicants should be MSc students in computer science, mathematics or a related discipline. The applicants should in particular have strong background in mathematics and some background and interest in cryptography. Good teamwork and communication skills, including excellent spoken and written English are also required.

Working at IMDEA Software
The position is based in Madrid, Spain, where the IMDEA Software Institute is situated. The institute provides for travel expenses and an internationally competitive stipend. The working language at the institute is English.

Dates
The internship duration is intended to be for 4-6 months (with some flexibility). The starting period would be March 2021 or later.

How to apply?
Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2020-12-intern-mpc. Deadline for applications is January 25th, 2021.

For enquiries about the position, please contact: Ignacio Cascudo, ignacio.cascudo (at) imdea.org

Closing date for applications:

Contact: Ignacio Cascudo

More information: https://careers.software.imdea.org/

The cryptography team at Ant Group (formerly known as Ant Finance and Alipay) is looking for multiple applied cryptographers or engineers at all levels. We are a team to bridge the academia world and the industry; to promote new crypto solutions via solving real world problems.

Candidates are expected to be developing cryptographic libraries and/or conduct related researches with a growing team of researchers and engineers. Candidates are likely to be working in one of the following directions:

• homomorphic encryptions
• multiparty computations
• zero-knowledge proofs

Knowledge of at least one of the above fields is a MUST. Please highlight in your CV your previous publications or open-source projects in those domains.

Bonus points:

• experience in developing cryptographic libraries
• top tier publications in cryptography or security
• experience with Rust

Location:

• Beijing
• Hangzhou

Closing date for applications:

Contact: Zhenfei Zhang

The Max Planck Institutes for Informatics (Saarbruecken), Software Systems (Saarbruecken and Kaiserslautern), and Security and Privacy (Bochum) offer research internships in all areas of Computer Science. An internship at a Max Planck Institute is a way to pursue world-class research in computer science! Our internships are also an excellent way to explore research or new research areas for the first time.

Internships are open to exceptional Bachelors, Masters, and Doctoral students worldwide, as well as exceptional individuals from industry interested in gaining academic research experience in computer science. Intern positions are limited and admissions are very competitive

We welcome interns all year round, but most interns prefer the summer months. Every intern works directly with an assigned faculty mentor at one of the participating institutes. Internship projects are based on the intern’s academic interests, maturity and prior experience.

All interns receive a monthly stipend, free (shared) housing, and travel to- and from- the institute hosting the internship. A typical internship lasts 12 to 14 weeks, but longer internships are possible.

Application Deadlines for Summer Internships:

• Early Deadline: 31 December (for internships starting in May or June)
• Late Deadline: 31 January (for internships starting in July or August)

For an internship starting at any other time, please apply at least 4 months before your intended started date.

More information can be obtained at https://www.cis.mpg.de/internships

We understand that travel restrictions due to the ongoing COVID-19 pandemic may prevent interns from traveling to host institutes right now. In such a case, the intern and the mentor may agree mutually to complete the internship remotely. The intern will still be paid the monthly stipend.

Closing date for applications:

Contact: Catalin Hritcu

More information: https://www.cis.mpg.de/internships

With the NIST Post quantum cryptography competition in final round, the importance of implementation security is highlighted in the latest call. In this regard, we report practical side-channel assisted message recovery attacks over embedded implementations of several post-quantum public key encryption (PKE) and key encapsulation mechanisms (KEM) based on the Learning With Errors (LWE) and Learning With Rounding (LWR) problem, which include three finalists and three semi-finalist candidates of the NIST standardization process. The proposed attacks target storage of the decrypted message in memory, a basic operation found in all libraries and typically unavoidable in any embedded implementation. We also identify interesting ciphertext malleability properties for LWE/LWR-based PKEs and exploit them to generalise proposed attack to different implementation choices as well as implementations protected with side-channel countermeasures such as shuffling and masking. All proposed attacks are validated on ARM Cortex-M4 microcontroller, targeting optimized open source implementations of PQC schemes using electromagnetic side-channel measurements.

This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols:

- Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points on classic prime order curves.

- Unified and complete formulas allow secure and efficient computations in the group.

- Efficiency is on par with twisted Edwards curves, and in some respects slightly better; e.g. half of double-odd curves have formulas for computing point doublings with only six multiplications (down to 1M+5S per doubling on some curves).

We describe here various formulas and discuss implementations. We also define two specific parameter choices for curves with 128-bit security, called do255e and do255s. Our own implementations on 64-bit x86 (Coffee Lake) and low-end ARM Cortex M0+ achieve generic point multiplication in 76696 and 2.19 million cycles, respectively, with curve do255e.

Our main result is a quantum public-key encryption scheme based on the Extrapolated Di- hedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For poly- nomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size Õ(n) qubits. The key generation and decryption algorithms require Õ(n) qubit operations while the encryption algorithm takes O(1) qubit operations.

In this work we focus on improving the communication complexity of the online phase of honest majority MPC protocols. To this end, we present a general and simple method to compile arbitrary secret-sharing-based passively secure protocols defined over an arbitrary ring that are secure up to additive attacks in a malicious setting, to actively secure protocols with abort. The resulting protocol has a total communication complexity in the online phase of $1.5(n-1)$ shares, which amounts to $1.5$ shares per party asymptotically. An important aspect of our techniques is that they can be seen as generalization of ideas that have been used in other works in a rather ad-hoc manner for different secret-sharing protocols. Thus, our work serves as a way of unifying key ideas in recent honest majority protocols, to understand better the core techniques and similarities among these works. Furthermore, for $n=3$, when instantiated with replicated secret-sharing-based protocols (Araki et al. CCS 2016), the communication complexity in the online phase amounts to only $1$ ring element per party, matching the communication complexity of the BLAZE protocol (Patra & Suresh, NDSS 2020), while having a much simpler design.

LWE based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie-Hellman key-exchange or polynomial LWE-modulus, resulting in unwanted efficiency overhead.

We study the possibility of designing non-interactive LWE-based protocols with polynomial LWE-modulus. To this end,

• We identify and formalize simple non-interactive and polynomial LWE-modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) LWE samples with polynomial LWE-modulus and then run individual key reconciliation functions to obtain the shared key.

• We point out central barriers and show that such non-interactive key-exchange protocols are impossible if:

1) the reconciliation functions first compute the inner product of the received LWE sample with their private LWE secret. This impossibility is information theoretic.

2) one of the reconciliation functions does not depend on the error of the transmitted LWE sample. This impossibility assumes hardness of LWE.

• We give further evidence that progress in either direction, of giving an LWE-based NIKE protocol or proving impossibility of one will lead to progress on some other well-studied questions in cryptography.

Overall, our results show possibilities and challenges in designing simple (ring) LWE-based non-interactive key exchange protocols.

Physical security of NIST lightweight cryptography competition candidates is gaining importance as the standardization process progresses. Side-channel attacks (SCA) are a well-researched topic within the physical security of cryptographic implementations. It was shown that collisions in the intermediate values can be captured by side-channel measurements to reduce the complexity of the key retrieval to trivial numbers.

In this paper, we target a specific bit permutation vulnerability in the block cipher GIFT that allows the attacker to mount a key recovery attack. We present a novel SCA methodology called DCSCA - Differential Ciphertext SCA, which follows principles of differential fault analysis, but instead of the usage of faults, it utilizes SCA and statistical distribution of intermediate values. We simulate the attack on a publicly available bitslice implementation of GIFT, showing the practicality of the attack. We further show the application of the attack on GIFT-based AEAD schemes (GIFT-COFB, ESTATE, HYENA, and SUNDAE-GIFT) proposed for the NIST LWC competition. DCSCA can recover the master key with $2^{13.39}$ AEAD sessions, assuming 32 encryptions per session.