International Association
for Cryptologic Research

Grover's search algorithm gives a quantum attack against block ciphers with query complexity $O(\sqrt{N})$ to search a keyspace of size $N$, when given a sufficient number of plaintext-ciphertext pairs. At EUROCRYPT 2020, Jaques, Naehrig, Roetteler, and Virdia have estimated the cost of quantum key search attacks against AES under different security categories as defined in NIST's PQC standardization process.

In this work, we extend their approach to lightweight block ciphers for the cost estimates of quantum key search attacks under circuit depth restrictions. We design quantum circuits for the lightweight block ciphers GIFT, SKINNY, and SATURNIN. Our circuits give overall cost in both the gate count and depth-times-width cost models. Based on the NIST' security categories for maximum depth, we present the concrete cost of quantum key search against GIFT, SKINNY, and SATURNIN.

We implement the full Grover oracle for GIFT-64, GIFT-128, SKINNY-64, SKINNY-128 and SATURNIN-256 in Q\# quantum programming language for unit tests and automatic resource estimations.

We present a sub-exponential forger by using a $k$-sum algorithm against the aggregate $\Gamma$ signature, which was proposed at AsiaCCS2019 by Zhao. Our forger is a universal forger under a key-only attack and effective in the knowledge of secret key model.

Machine learning is an important tool for analyzing large data sets, but its use on sensitive data may be limited by regulation. One solution to this problem is to perform machine learning tasks on encrypted data using homomorphic encryption, which enables arbitrary computation on encrypted data. We take a fresh look at one specific task: training a logistic regression model on encrypted data. The most important factor in the efficiency of a solution is the multiplicative depth of the homomorphic circuit. Two prior works have given circuits with multiplicative depth of five per training iteration. We optimize one of these solutions, by Han et al. [Han+18], and give a circuit with half the multiplicative depth per iteration on average, which allows us to perform twice as many training iterations in the same amount of time. In the process of improving the state-of-the-art circuit for this task, we identify general techniques to improve homomorphic circuit design for two broad classes of algorithms: iterative algorithms, and algorithms based on linear algebra over real numbers. First, we formalize the encoding scheme from [Han+18] for encoding linear algebra objects as plaintexts in the CKKS homomorphic encryption scheme. We also show how to use this encoding to homomorphically compute many basic linear algebra operations, including novel operations not discussed in prior work. This “toolkit” is generic, and can be used in any application based on linear algebra. Second, we demonstrate how generic compiler techniques for loop optimization can be used to reduce the multiplicative depth of iterative algorithms.

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.