International Association
for Cryptologic Research

Saber is one of the four finalists in the ongoing NIST post-quantum cryptography standardization project. A significant portion of Saber's computation time is spent on computing polynomial multiplications in polynomial rings with powers-of-two moduli. We propose several optimization strategies for improving the performance of polynomial multiplier architectures for Saber, targeting different hardware platforms and diverse application goals. We propose two high-speed architectures that exploit the smallness of operand polynomials in Saber and can achieve great performance with a moderate area consumption. We also propose a lightweight multiplier that consumes only 541 LUTs and 301 FFs on a small Artix-7 FPGA.

HElib is a C++ open source library (see https://github.com/homenc/HElib) that implements both the BGV and CKKS fully homomorphic encryption (FHE) schemes. This document summarizes some of the basic design principles of HElib, and describes some of its fundamental algorithms and data structures in significant detail. It is a work in progress, and currently focuses exclusively on the BGV scheme.

We remove the so far quadratic bit communication cost of three desirable properties of consensus protocols with leaders: { Responsiveness with Optimal latency }, { Optimistic Fast Track } and { Strong Unanimity }. No existing consensus protocol with leaders with subquadratic bit complexity has any of those properties so far. [Hotstuff, Podc'19] has suboptimal latency of two more messages delays, whereas Hotstuffv1 is not responsive. [SBFT, Dsn'19] has quadratic complexity every time a new leader appears. Strong Unanimity has equally quadratic complexity so far [Chan et al Podc'19] in this setting. We reduce the communication costs of each of these properties down to $O(n\log n)$. In addition, we achieve them { simultaneously }, with optimal corruption threshold.

To achieve these specifications we use the structure of the consensus of Castro-Liskov / [SBFT, Dsn'19], in which we drop-in succinct (range-) proofs of knowledge as a replacement for the forwarding of many messages. We use the same kind of strategy to enable a Fast Track and Strong Unanimity. Namely, we incorporate the additional structure of [SBFT, Dsn'19] and of [Chan et al Podc'19] in the previous protocol. Which we instantiate with proofs of knowledge of: a set of signed messages, from a threshold number of issuers, in which no value appears in majority. The required proofs of knowledge can be obtained from any succinct proof system. Of independent interest, we also introduce alternative elementary proofs, solely based on a black box Threshold Signature Scheme (TSS).

{ Applied } to the state of the art leader-less fully asynchronous consensus protocol [Podc'19], which uses the [Hotstuff, Podc'19] consensus as baseline, this reduces its latency by $25\%$. This speedup directly carries over the state machine replication system [Hotstuff, Podc'19], and thus to Libra. Of independent interest we maintain linear complexity when requiring both External Validity and Halting in finite time, in the Amortized regime over long values. Instantiated with the recent unpublished logarithmic Transparent TSS of Attema et al, none of our protocols requires a trusted setup or a distributed key generation.

Governments and policy makers are finding it difficult to curb the enormous spread of pandemic Covid-19 till the vaccine is invented and becomes available for use. When a person is detected to be infected with Novel coronavirus, the task of identifying the persons who have come across the victim in past fortnight is a challenging task. Identifying these contact persons manually is a hilarious task and often yields incomplete data. Some governments have used digital technology for contact tracing but it is prone to compromise privacy of citizens. In this paper, we propose to use blockchain for recording every transaction in a secure manner that involves communications between users who are equipped with cloud-enabled body area networks. Whenever an user is tested coronavirus positive, the health officials and concerned administration immediately finds only those blockchain transaction records corresponding to the infected persons to identify the contact tracings in the past fortnight. Further, if a contact person is suffering from high temparature that is also detected automatically by the proposed system. This proposed system will help authoroties immensely to quickly quarantine the contacts of Covid-19 cases and curb the spread of coronavirus beyond a limit while maintaining the privacy of users.

Multi-signatures are used to attest that a fixed collection of $n$ parties, represented by their respective public keys, have all signed a given message. An emerging application of multi-signatures is to be found in consensus protocols to attest that a qualified subset of a global set of $n$ validators have reached agreement. In this paper, we point out that the traditional security model for multi-signatures is insufficient for this new application, as it assumes that every party in the set participates in the multi-signature computation phase and is honest. None of these assumptions hold in the typical adversarial scenarios in consensus protocols (aka. byzantine agreement). We address this by introducing a new multi-signature variant called robust subgroup multi-signatures, whereby any eligible subgroup of signers from the global set can produce a multi-signature on behalf of the group, even in the presence of a byzantine adversary. We provide syntax and security definitions for the new variant. We argue that existing unforgeability security proofs for multi-signatures do not carry over to the consensus setting; a consequence of this observation is that many multi-signature based consensus protocols lack a rigorous security proof for correctness. To remedy this we propose several constructions which we prove secure under widely held cryptographic assumptions using our newly introduced formal definitions and also improve upon multi-signature computation time. Finally, we report on benchmarks from a proof-of-concept implementation.

Event date: 23 March to 26 March 2021
Submission deadline: 15 January 2021
Notification: 1 February 2021

Event date: 7 July to 9 July 2021
Submission deadline: 15 February 2021
Notification: 6 April 2021

The registration for Asiacrypt 2020 (virtual) is now open: https://asiacrypt.iacr.org/2020/

The IACR board has decided that virtual Asiacrypt 2020 will be free, but attendees are required to pay the IACR membership fee for 2021 if they have not already paid it (typically by attending an IACR conference in 2020).

The conference program is available here: https://asiacrypt.iacr.org/2020/program.php

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography. The student is expected to work on topics that include security and privacy issues for resource-constrained devices (e.g., sensors) that rely on external untrusted servers in order to perform computations. More precisely, the student shall be working on investigating efficient authentication and verifiable delegation of computation mechanisms that provide: i) provable security guarantees, and ii) rigorous privacy guarantees. The position is funded with a competitive salary.
Research area: Research areas include but are not limited to:

• Verifiable computation
• Secure Multi Party Computation
• Privacy-preserving authentication
• Cryptographic primitives

Your Profile:

• A MsC degree in Computer Science, Applied Mathematics or a relevant field;
• Strong mathematical and algorithmic CS background;
• Excellent programming skills;
• Excellent written and verbal communication skills in English

Deadline for applications: 15 December 2020
Starting date: Beginning of 2021 or by mutual agreement

Closing date for applications:

Contact: Katerina Mitrokotsa

More information: https://jobs.unisg.ch/offene-stellen/phd-position-in-information-security-and-cryptography-m-w-d/6366821b-4848-4217-90d2-78e6b1096162

Applications are invited for two fully-funded PhD student position at the IMDEA Software Institute (Madrid, Spain).

The selected candidate will work with Marco Guarnieri (https://mguarnieri.github.io) on the design, verification, and implementation of countermeasures against CPU micro-architectural attacks.

Who should apply?

Ideal candidates have earned (or are in their last year of) a Master's degree in Computer Science, Computer Engineering, or Mathematics, with interest in at least one of the following areas:

• Computer security
• Computer architectures
• Program analysis and verification
• Formal methods
• Logics

Solid programming skills will be highly valued. The position requires good teamwork and communication skills, including excellent spoken and written English.

Working at IMDEA Software

The IMDEA Software Institute is ranked among the best European research institutes in the areas of Programming Languages and Computer Security. Located in the Montegancedo Science and Technology Park, it perfectly combines the sunny and vibrant city of Madrid with cutting edge research and inspiring working environment.

The institute provides an internationally competitive stipend, access to an excellent public health care system, unemployment benefits, retirement benefits, and support for research related travel. The working language at the institute is English. Knowledge of Spanish is not required.

Dates

The duration of the position is intended to be for the duration of the doctoral studies. The ideal starting period is from early January 2021

Deadline for applications is December 20th, 2020. Review of applications will begin immediately, and continue until the positions are filled.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2020-11-phd-uarchsec.

Questions

For any questions about these positions, please contact Marco Guarnieri directly (marco dot guarnieri at imdea dot org).

Closing date for applications:

Contact: Marco Guarnieri (marco dot guarnieri at imdea dot org)

More information: https://software.imdea.org/open_positions/2020-11-phd-uarchsec.html

Applications are invited for one postdoctoral position at the IMDEA Software Institute (Madrid, Spain).

The selected candidate will work with Marco Guarnieri (https://mguarnieri.github.io) on the design, verification, and implementation of countermeasures against CPU micro-architectural attacks.

Who should apply?

Ideal candidates have earned (or are close to earning) a PhD in Computer Science or a related area with a promising publication record and experience in at least one of the following areas:

• Computer security
• Computer architectures
• Program analysis and verification
• Formal methods
• Logics

Solid programming skills will be highly valued. The position requires good teamwork and communication skills, including excellent spoken and written English.

Working at IMDEA Software

The IMDEA Software Institute is ranked among the best European research institutes in the areas of Programming Languages and Computer Security. Located in the Montegancedo Science and Technology Park, it perfectly combines the sunny and vibrant city of Madrid with cutting edge research and inspiring working environment.

The institute provides an internationally competitive stipend, access to an excellent public health care system, unemployment benefits, retirement benefits, and support for research related travel. The working language at the institute is English. Knowledge of Spanish is not required.

Dates

The duration of the position is intended to be for 24 months. The ideal starting period is from early January 2021.

Deadline for applications is December 20th, 2020. Review of applications will begin immediately, and continue until the positions are filled.

How to apply?

Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2020-11-postdoc-uarchsec.

Questions

For any questions about these positions, please contact Marco Guarnieri directly (marco dot guarnieri at imdea dot org).

Closing date for applications:

Contact: Marco Guarnieri (marco dot guarnieri at imdea dot org)

More information: https://software.imdea.org/open_positions/2020-11-postdoc-uarchsec.html

The CWI Cryptology group is looking for a young postdoc researcher interested in both codes and lattices in the context of cryptography. The goal is to make major progress in both research areas, by comparing them, by transferring techniques back and forth, or even by developing a unifying theory. All angles relevant to cryptography are considered, from construction to cryptanalysis, and from theory to practice.
The successful candidate will be working with Dr. Léo Ducas, within his ERC Starting Grant project ARTICULATE.

More details at : https://www.cwi.nl/jobs/vacancies/866541

Closing date for applications:

Contact: Léo Ducas : ducas AT cwi DOT nl

More information: https://www.cwi.nl/jobs/vacancies/866541

ElectionGuard is an open source set of software components and specifications from Microsoft designed to allow the modification of a number of different e-voting protocols and products to produce public evidence (transcripts) which anyone can verify. The software uses ElGamal, homomorphic tallying and sigma protocols to enable public scrutiny without adversely affecting privacy. Some components have been formally verified (machine-checked) to be free of certain software bugs but there was no formal verification of their cryptographic security. Here, we present a machine-checked proof of the verifiability guarantees of the transcripts produced and verified according to the ElectionGuard specification. We have also extracted an executable version of the verifier specification, which we proved to be secure, and used it to verify election transcripts produced by ElectionGuard. Our results show that our implementation is of similar efficiency to existing implementations.

Blockchain has the potential to accelerate the worldwide deployment of an emissions trading system (ETS) and improve the efficiency of existing systems. In this paper, we present a model for a permissioned blockchain implementation based on the successful European Union (EU) ETS and discuss its potential advantages over existing technology. The proposed ETS model is both backward compatible and future-proof, characterised by interconnectedness, transparency, tamper-resistance and continuous liquidity. Further, we identify key challenges to implementation of blockchain in ETS, as well as areas of future work required to enable a fully decentralised blockchain-based ETS.

Revocable identity-based encryption (RIBE) is an extension of identity-based encryption (IBE) and it supports efficient revocation of private keys. In the past, many efficient RIBE schemes have been proposed, but research on efficiently delegating the generation of update keys to a cloud server is somewhat insufficient. In this paper, we newly introduce the concept of delegated RIBE (DRIBE) that can delegate the generation of update keys to the cloud server and define the security models of DRIBE. Next, we propose a DRIBE scheme by generically combining a hierarchical IBE (HIBE) scheme, an identity-based broadcast encryption (IBBE) scheme, and a collision-resistant hash function. In addition, we propose a DRIBE-INC scheme that generates an occasional base update key and a periodic incremental update key to reduce the size of the update key in our DRIBE scheme.

A cryptographic protocol (CP) is a distributed algorithm designed to provide a secure communication in an insecure environment. CPs are used, for example, in electronic payments, electronic voting procedures, database access systems, etc. Errors in the CPs can lead to great financial and social damage, therefore it is necessary to use mathematical methods to justify the correctness and safety of the CPs. In this paper, a new mathematical model of a CP is introduced, which allows one to describe both the CPs and their properties. It is shown how, on the basis of this model, it is possible to solve the problems of verification of CPs.

Super-spreader events where one person infects many others have been a driving force of the Covid-19 pandemic. Such events often happen indoors, such as in restaurants, at choir practice or in gyms. Many systems for automated contact tracing (ACT) have been proposed, which will warn a user when they have been in proximity to an infected person. These generally fail to detect potential super-spreader events as only users who have come in close contact with the infected person, but not others who also visited the same location, are warned. Other approaches allow users to check into locations or venues, but these require user interaction.

We propose two designs how broadcast-based ACT systems can be enhanced to utilize location-specific information without the need for GPS traces or scanning of QR codes. This makes it possible to alert attendees of a potential super-spreader event while still remaining private. Our first design relies on cooperating lighthouses which cover a large area and send out pseudonyms. These are recorded by visitors and published by the health authority (HA) in case of an infection. The second design has lighthouses actively communicating with HAs after retrospectively detecting an infected visitor to warn everyone whose stay overlapped.

The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et. al in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.

We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results:

∙ A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE).

∙ A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed simulation technique that we call “simulation via teleportation,” which may be useful in other settings.

In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model, including an impossibility result for a natural class of simulators, and a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation.

Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.

Most state machine replication protocols are either based on the 40-years-old Byzantine Fault Tolerance (BFT) theory or the more recent Nakamoto’s longest chain design. Longest chain protocols, designed originally in the Proof-of-Work (PoW) setting, are available under dynamic participation, but has probabilistic confirmation with long latency dependent on the security parameter. BFT protocols, designed for the permissioned setting, has fast deterministic confirmation, but assume a fixed number of nodes always online. We present a new construction which combines a longest chain protocol and a BFT protocol to get the best of both worlds. Using this construction, we design TaiJi, the first dynamically available PoW protocol which has almost deterministic confirmation with latency independent of the security parameter. In contrast to previous hybrid approaches which use a single longest chain to sample participants to run a BFT protocol, our native PoW construction uses many independent longest chains to sample propose actions and vote actions for the BFT protocol. This design enables TaiJi to inherit the full dynamic availability of Bitcoin, as well as its full unpredictability, making it secure against fully-adaptive adversaries with up to 50% of online hash power.