International Association
for Cryptologic Research

In this paper we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input and output whether the decryption key belongs to some known subset of keys. Partitioning oracles can arise when encryption schemes are not committing with respect to their keys. We detail adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords and de-anonymize anonymous communications. The attacks utilize efficient key multi-collision algorithms --- a cryptanalytic goal that we define --- against widely used authenticated encryption with associated data (AEAD) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305.

We build a practical partitioning oracle attack that quickly recovers passwords from Shadowsocks proxy servers. We also survey early implementations of the OPAQUE protocol for password-based key exchange, and show how many could be vulnerable to partitioning oracle attacks due to incorrectly using non-committing AEAD. Our results suggest that the community should standardize and make widely available committing AEAD to avoid such vulnerabilities.

Sanitizable signatures (SaS) allow a (single) sanitizer, chosen by the signer, to modify and re-sign a message in a somewhat controlled way, that is, only editing parts (or blocks) of the message that are admissible for modification.

This primitive is an efficient tool, with many formally defined security properties, such as unlinkability, transparency, immutability, invisibility, and unforgeability. An SaS scheme that satisfies these properties can be a great asset to the privacy of any field it will be applied to, e.g., anonymizing medical files.

In this work, we look at the notion of γ-sanitizable signatures ( γSaS): we take the sanitizable signatures one step further by allowing the signer to not only decide which blocks can be modified, but also how many of them at most can be modified within a single sanitization, setting a limit, denoted with γ. We adapt the security properties listed above to γSaS and propose our own scheme, ULISS (Unlinkable Limited Invisible Sanitizable Signature), then show that it verifies these properties. This extension of SaS can not only improve current use cases, but also introduce new ones, e.g., restricting the number of changes in a document within a certain timeframe.

In a universally composable framework, a global setup is intended to capture the ideal behavior of a primitive which is accessible by multiple protocols, allowing them to share state. The ledger implemented by blockchain protocols such as Bitcoin is a representative example of such global setup, since the Bitcoin ledger is known to be useful in various scenarios. Therefore, it has become increasingly popular to capture such ledgers as a global setup. One would hope that this allows one to make security statements about protocols that use such a global setup, e.g., a global ledger, which can then be automatically translated into the setting where the setup is replaced by a protocol implementing it, such as Bitcoin.

We show that the above reasoning is flawed and such a generic security-preserving replacement can only work under very (often unrealistic) strong conditions on the global setup. For example, the composable security of Bitcoin, cast as realizing an ideal ledger such as the one by Badertscher et al. [CRYPTO'17], is not sufficient per se to allow us to replace the ledger by Bitcoin when used as a global setup and to expect that security statements that are made in the global ledger-hybrid world would be preserved.

On the positive side, we provide characterizations of security statements for protocols that make use of global setups, for which the replacement is sound. Our results can be seen as a first guide on how to navigate the very tricky question of what constitutes a ``good'' global setup and how to use it in order to keep the modular protocol-design approach intact.

The concept of quantum bit commitment was introduced more than three decades ago in a failed attempt to base unconditional bit commitment solely on quantum information theory. In this work, we explore general properties of \textit{conditional} quantum bit commitment, which additionally assumes quantum computational hardness but without any mathematical structure (e.g. quantum-secure one-way function). While it is well known that a general quantum bit commitment scheme can only guarantee a fairly weak binding property compared with its classical counterpart, interestingly, we show that it also enjoys some other nice properties that its classical counterpart does not have. Among others, we show that any (interactive) quantum bit commitment scheme can be compiled into a non-interactive generic form (by an ensemble of quantum circuit pair). These general properties not only enable us to simplify both the construction and the security analysis of quantum bit commitment significantly but also suggest a potential use of it as a replacement of the classical one in quantum cryptography.

We prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of the quantum-hard one-way function.

Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments from quantum-hard one-way functions in the standard model. Instantiating the Bennet-Brassard-Crépeau-Skubiszewska (CRYPTO 91) framework with these commitments yields simulation-secure quantum oblivious transfer.

Permissionless blockchain systems such as Bitcoin or Ethereum are slow and expensive, since transactions are processed in a distributed network by a large set of parties. To improve on these shortcomings, a prominent approach is given by so-called 2nd-layer protocols. In these protocols parties process transactions off-chain directly between each other, thereby drastically reducing the costly and slow interaction with the blockchain. In particular, in the optimistic case, when parties behave honestly, no interaction with the blockchain is needed. One of the most popular off-chain solutions are Plasma protocols (often also called commit-chains). These protocols are orchestrated by a so-called operator that maintains the system and processes transactions between parties. Importantly, the operator is trustless, i.e., even if it is malicious users of the system are guaranteed to not lose funds. To achieve this guarantee, Plasma protocols are highly complex and require involved and expensive dispute resolution processes. This has significantly slowed down development and deployment of these systems.

In this work we propose CommiTEE-- a simple and efficient Plasma system leveraging the power of trusted execution environments (TEE). Besides its simplicity, our protocol requires minimal interaction with the blockchain, thereby drastically reducing costs and improving efficiency. An additional benefit of our solution is that it allows for switching between operators, in case the main operator goes offline due to system failure, or behaving maliciously. We implemented and evaluated our system over Ethereum and show that it is at least $2$ times (and in some cases more than $16$ times) cheaper in terms of communication complexity when compared to existing Plasma implementations. Moreover, for protocols using zero-knowledge proofs (like NOCUST-ZKP), CommiTEE decreases the on-chain gas cost by a factor $\approx 19$ compared to prior solution.

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