International Association
for Cryptologic Research

Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.

Federated learning (FL) is an emerging distributed machine learning paradigm which addresses critical data privacy issues in machine learning by enabling clients, using an aggregation server (aggregator), to jointly train a global model without revealing their training data. Thereby, it improves not only privacy but is also efficient as it uses the computation power and data of potentially millions of clients for training in parallel.

However, FL is vulnerable to so-called inference attacks by malicious aggregators which can infer information about clients’ data from their model updates. Secure aggregation restricts the central aggregator to only learn the summation or average of the updates of clients. Unfortunately, existing protocols for secure aggregation for FL suffer from high communication, computation, and many communication rounds.

In this work, we present SAFELearn, a generic design for efficient private FL systems that protects against inference attacks that have to analyze individual clients' model updates using secure aggregation. It is flexibly adaptable to the efficiency and security requirements of various FL applications and can be instantiated with MPC or FHE. In contrast to previous works, we only need 2 rounds of communication in each training iteration, do not use any expensive cryptographic primitives on clients, tolerate dropouts, and do not rely on a trusted third party. We implement and benchmark an instantiation of our generic design with secure two-party computation. Our implementation aggregates 500~models with more than 300K parameters in less than 0.5 seconds.

The problem of Blockwise Isomorphism of Polynomials was introduced by Santoso at PQCrypto 2020 as a generalization of the problem of Isomorphism of Polynomials. In the present paper, we describe how to solve this problem with circulant matrices, used in Santoso's Diffie-Hellman type encryption scheme.

The Lightning Network (LN) is a prominent scalability solution for Bitcoin that allows for low-latency off-chain payments through a network of payment channels. LN users lock bitcoins into collaboratively owned addresses and redistribute the ownership of these funds without confirming each transfer on-chain. The LN introduces new privacy challenges.

In this paper, we focus on channel balance probing. We propose a new model of the LN that accounts for parallel and unidirectional channels, which has not been done in prior work. We describe a probing algorithm that accurately updates the attacker's balance estimates without the need to directly connect to victims. We introduce an uncertainty-based metric to measure the attacker's information gain.

We implement the first probing-focused LN simulator and suggest several countermeasures against general probing (implemented considering parallel channels). We evaluate these techniques using the simulator, as well as experiments on the real network.

According to our simulations, an attacker can infer up to $80\%$~information regarding channel balances spending $\approx 20$~seconds per channel. The suggested countermeasures limit the attacker's gain at $30\%$, while also increasing the attack time by 2-4x.

In addition, we describe sophisticated attack techniques that combine fee-probing and channel jamming to get precise access to individual channel balances inside a hop, and test them against the real network.

Finally, we discuss payment flows and their concealment.

This report considers combining three well-known optimization methods for elliptic curve scalar multiplication: Gallant--Lambert--Vanstone (GLV) for complex multiplication endomorphisms $[i]$ and $[i+1]$; 3-bit fixed windows (signed base 8); and Hisil--Wong--Carter--Dawson (HWCD) curve arithmetic for twisted Edwards curves.

An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where $\textbf{M}$ is a field multiplication and $\textbf{S}$ is a field squaring. This is approximately $(3.55\textbf{M} + 4.07\textbf{S})$/bit, with $1\textbf{S}$/bit for input decompression and $1\textbf{S}$/bit for output normalization. Optimizing speed by allowing uncompressed input points leads to an estimate $(3.38\textbf{M}+2.95\textbf{S})$/bit.

To mitigate some side-channel attacks, the secret scalar is only used to copy curve points from one array to another: the field operations used are fixed and independent of the secret scalar. The method is likely vulnerable to cache-timing attacks, nonetheless.

Event date: 11 August to 14 August 2021
Submission deadline: 20 May 2021
Notification: 30 July 2021

We are proud to announce the winners of the 2021 IACR Test-of-Time Award. This award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field.

The Test-of-Time award for Eurocrypt 2006 is awarded to "A provable-security treatment of the key-wrap problem" (Phillip Rogaway and Thomas Shrimpton), for placing the important real world primitive of key-wrapping on a solid theoretic foundation.

The Test-of-Time award for Crypto 2006 is awarded to "New proofs for NMAC and HMAC: Security without collision-resistance" (Mihir Bellare), for proving that the security of the widely deployed HMAC construction does not depend on the collision resistance of the underlying hash function.

The Test-of-Time award for Asiacrypt 2006 is awarded to "Simulation-sound NIZK proofs for a practical language and constant size group signatures" (Jens Groth), for constructing asymptotically optimal NIZK proofs and group signatures without using random oracles, and paving the way to practical constructions.

For more information, see https://www.iacr.org/testoftime.

Dear fellow researchers,

As part of a wider effort on Blockchain Security and Finance research, we are offering funded Ph.D. positions related to the field of Decentralized Finance for stellar candidates.

We offer a striving research group with:

• Over 15 combined years of full-time research experience in the blockchain domain.
• Very consistent publications in highly competitive venues. So far, in the year 2021 alone: 2x IEEE Symposium on Security & Privacy (Oakland), 2x Financial Cryptography and Datasecurity (FC) and 1x IEEE EuroS&P paper.
• Hands-on supervision and collaboration among senior and junior Ph.D. students.
• Interdisciplinary challenges covering information security, cryptography, game theoretic incentives, economics, finance, systems, etc.
• Practical, real-world applicable research.
• Regular Zoom/Slack/iPad calls/chats/whiteboard sessions.
• Fun group events, such as game evenings etc.

Your profile ideally matches with the following:

• You enjoy to communicate transparently and openly, e.g. through regular/daily Zoom calls and slack.
• You are self-motivated, outcome drive and productive, especially during the current pandemic.
• You have a strong analytical background coupled with a solid ability to write clean and simple code.
• You prefer simplicity over complexity. You first strive towards a quick and non-perfect solution, and don't prematurely optimise something that shouldn't exist.
• While you may not yet like writing, you want to learn being able to write the perfect English text.
• You want to produce world-leading research, which you'd like to get challenged by reviewers from only the best conferences.

When applying, please familiarize yourself with the group's publications which can be found in reverse chronological order here: https://scholar.google.com/citations?hl=en&user=jLr_xi4AAAAJ&view_op=list_works&sortby=pubdate

Closing date for applications:

Contact: arthur@gervais.cc

More information: https://scholar.google.com/citations?hl=en&user=jLr_xi4AAAAJ&view_op=list_works&sortby=pubdate

The Institute of Applied Information Processing and Communications (aka IAIK) is the largest university institute in Austria for research and education in security and privacy. It has been active in this field for more than 30 years and currently employs more than 60 researchers. Within the "Secure Systems" area of our institute Sujoy Sinha Roy is establishing the new research group "Cryptographic Engineering”.

In order to complement our team, we are looking for a fulltime PhD researcher in Post-Quantum Cryptography.

Responsibilities:
The PhD researcher will be working on the implementation and side-channel security aspects of post-quantum cryptography within the “Cyroptografic Engineering” group within the “Secure Systems” area at IAIK.
The PhD candidate will have to start by May/June 2021.

Required Qualifications:
• MSc degree (or close to completion) in computer science, information and computer engineering, software development, mathematics, or a related field.
• Research experience from MSc/BSc projects.
• Outstanding candidates with BSc degree and publications in related research area are also welcome.
• Experience with cryptography, programming, and digital circuit design (ASIC or FPGA) design

How to apply:
Applications, curriculum vitae and other documents should preferably be uploaded here https://free.formcloud.de/formcycle/form/provide/7780/. Please select „7050 – PhD 2021 – crypteng" as a reference number. The application deadline is April 20th 2021.

Closing date for applications:

Contact: For more detailed information please conctact Sujoy Sinha Roy - sujoy.sinharoy@iaik.tugraz.at.

More information: https://www.tugraz.at/index.php?id=50397

The Department of Computer Science at the University of Manchester (UK) wishes to appoint a Senior Lecturer in Systems Security. The new appointment will complement existing world-class research in software security and automated reasoning.

Applicants should be computer scientists with a strong interest and track record in a relevant area of systems security, for example, cryptography, operating systems and virtualization, distributed systems security, authentication, authorization, and accountability. We also encourage applicants with a strong interest and track record in code and data integrity, malware analysis, integrity, trustworthiness, privacy, and anonymity. You will be a member of the Formal Methods Group with access to expertise in program analysis and reasoning methods. We are particularly interested in developing collaborations involving several groups within the department and wider University. For example, an exciting opportunity exists to work closely with the well-known advanced processor technologies group to study applications in massively parallel software and the IoT. Thus, experience and interest in collaborative research are particularly welcome.

You should hold a relevant Ph.D. or equivalent, have an excellent international publication record in top security conferences (e.g., ACM CCS, IEEE S&P, NDSS, USENIX Security). The applicants should show the capability of developing a portfolio of funded research activities in a multidisciplinary environment and have a solid commitment to excellence in teaching.

Closing date for applications:

Contact:

Enquiries about the vacancy, shortlisting and interviews: Dr. Lucas Cordeiro (lucas.cordeiro@manchester.ac.uk) or Dr. Giles Reger (giles.reger@manchester.ac.uk).

General enquiries: hrservices@manchester.ac.uk

More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?isPreview=Yes&jobid=19901

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

Threshold and blind signature schemes have found numerous applications in cryptocurrencies, e-cash, e-voting and other privacy-preserving technologies. In this work, we make advances in bringing lattice-based constructions for these primitives closer to practice.

1. Threshold Signatures. For round optimal threshold signatures, we improve the only known construction by Boneh et al. [CRYPTO'18] as follows:

a. Efficiency. We reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease signature bit-lengths from $\widetilde{O}(\lambda^3)$ to $\widetilde{O}(\lambda)$.

b. Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing queries are made. We improve this in two ways: in the ROM, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline pre-processing phase.

2. Blind Signatures. For blind signatures, we improve the state of art lattice-based construction by Hauck et al.[CRYPTO'20] as follows:

a. Round Complexity. We improve the round complexity from three to two -- this is optimal.

b. Efficiency. Again, we reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of signatures and $\lambda$ is the security parameter.

c. Number of Signing Queries. Unlike the scheme from Hauck et al., our construction enjoys a proof that is not restricted to a polylogarithmic number of signatures. Using lattice hardness assumptions over rings, we obtain signatures of bit-lengths bounded as $\widetilde{O}(\lambda)$. In contrast, the signature bit-length in the scheme from Hauck et al. is $\Omega(\lambda^3 + Q_S \cdot \lambda)$.

Concretely, we can obtain blind/threshold signatures of size $\approx 3$ KB using a variant of Dilithium-G with $\approx 128$ bit-security, for adversaries limited to getting $256$ signatures. In contrast, parameters provided by Hauck et al. lead to blind signatures of $\approx 7.73$ MB, for adversaries limited to getting 7 signatures, while concrete parameters are not provided for the construction of threshold signatures by Boneh et al.

Proxy signature (PS) is a kind of digital signature, in which an entity called original signer can delegate his signing rights to another entity called proxy signer. Designated verifier signature (DVS) is a kind of digital signature where the authenticity of any signature can be verified by only one verifier who is designated by the signer when generating it. Designated verifier proxy signature (DVPS) combines the idea of DVS with the concept of proxy signature (PS) and is suitable for being applied in many scenarios from e-tender, e-voting, e-auction, e-health and e-commerce, etc. Many DVPS schemes have been proposed and Identity-based DVPS (IBDVPS) schemes have also been discussed. Certificateless public-key cryptography (CL-PKC) is acknowledged as an appealing paradigm because there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. A number of certificateless designated verifier signature (CLDVS) schemes and many certificateless proxy signature (CLPS) schemes have been proposed. However, to the best of our knowledge, the concept of Certificateless Designated Verifier Proxy Signature (CLDVPS) has not been appeared in the literature. In this paper, we formalize the definition and the security model of CLDVPS schemes. We then construct the first CLDVPS scheme and prove its security.

This note solves the open problem of finding a closed formula for the bias of a rotational differential-linear distinguisher proposed in IACR ePrint 2021/189 (EUROCRYPT 2021), completely generalizing the results on ordinary differential-linear distinguishers due to Blondeau, Leander, and Nyberg (JoC 2017) to the case of rotational differential-linear distinguishers.

Motivated by the goal of designing versatile and flexible secure computation protocols that at the same time require as little interaction as possible, we present new multiparty reusable Non-Interactive Secure Computation (mrNISC) protocols. This notion, recently introduced by Benhamouda and Lin (TCC 2020), is essentially two-round Multi-Party Computation (MPC) protocols where the first round of messages serves as a reusable commitment to the private inputs of participating parties. Using these commitments, any subset of parties can later compute any function of their choice on their respective inputs by just sending a single message to a stateless evaluator, conveying the result of the computation but nothing else. Importantly, the input commitments can be computed without knowing anything about other participating parties (neither their identities nor their number) and they are reusable across any number of desired computations.

We give a construction of mrNISC that achieves standard simulation security, as classical multi-round MPC protocols achieve. Our construction relies on the Learning With Errors (LWE) assumption with polynomial modulus, and on the existence of a pseudorandom function (PRF) in $\mathsf{NC}^1$. We achieve semi-malicious security in the plain model and malicious security by further relying on trusted setup (which is unavoidable for mrNISC). In comparison, the only previously known constructions of mrNISC were either using bilinear maps or using strong primitives such as program obfuscation.

We use our mrNISC to obtain new Multi-Key FHE (MKFHE) schemes with threshold decryption:

$\bullet$ In the CRS model, we obtain threshold MKFHE for $\mathsf{NC}^1$ based on LWE with only $\textit{polynomial}$ modulus and PRFs in $\mathsf{NC}^1$, whereas all previous constructions rely on LWE with super-polynomial modulus-to-noise ratio.

$\bullet$ In the plain model, we obtain threshold levelled MKFHE for $\mathsf{P}$ based on LWE with $\textit{polynomial}$ modulus, PRF in $\mathsf{NC}^1$, and NTRU, and another scheme for constant number of parties from LWE with sub-exponential modulus-to-noise ratio. The only known prior construction of threshold MKFHE (Ananth et al., TCC 2020) in the plain model restricts the set of parties who can compute together at the onset.

This article discusses existing attacks and known weaknesses of BLS aggregate signatures. The goal is clarify the threat model of BLS aggregate signatures, what security properties that they have and do not have. It’s unfortunate that the weaknesses are not documented anywhere in BLS RFC draft v4 [1]. Confusion, ambiguity, misunderstanding all may cause security issues in practice. We hope that this article can help cryptographic practitioners make informed decisions when using BLS aggregate signatures and deploy mitigations at the application/protocol layer because BLS aggregate signatures might not have security guarantees that you need.

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.

We propose protocols for obliviously evaluating finite-state machines, i.e., the evaluation is shared between the provider of the finite-state machine and the provider of the input string in such a manner that neither party learns the other's input, and the states being visited are hidden from both. For alphabet size $|\Sigma|$, number of states $|Q|$, and input length $n$, previous solutions have either required a number of rounds linear in $n$ or communication $\Omega(n|\Sigma||Q|\log|Q|)$. Our solutions require 2 rounds with communication $O(n(|\Sigma|+|Q|\log|Q|))$. We present two different solutions to this problem, a two-party one and a setting with an untrusted but non-colluding helper.

The Tor anonymity network is often abused by some attackers to (anonymously) convey attack traffic. These attacks abuse Tor exit relays (i.e., the relays through which traffic exits Tor) by making it appear the attack originates there; as a result, many website operators indiscriminately block all Tor traffic (by blacklisting all exit IPs), reducing the usefulness of Tor.

Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service attacks). This suggests that a simple solution such as throttling traffic flow at the Tor exits may permit early detection of these attacks.

However, naively monitoring and throttling traffic at the Tor exits can endanger the privacy of the network's users. Indeed, many recent works have proposed private measurement systems that support safe aggregation of exit statistics. However, these systems do not permit identification of "unlinkable" connections that are part of a high-volume attack. Doing so could allow Tor to take proper remedial actions, such as dropping the attack traffic, but care must be taken to protect privacy.

We present ZXAD (pronounced "zed-zad"), the first zero-knowledge based private Tor exit abuse detection system. ZXAD detects large-volume traffic attacks without revealing any information, apart from the fact that some user is conveying a high volume of traffic through Tor. We formally prove the correctness and security of ZXAD. We also measure two proof-of-concept implementations of our zero-knowledge proofs and show that ZXAD operates with low bandwidth and processing overheads.

Given $2n$-to-$n$ compression functions $h_1,h_2,h_3$, we build a new $5n$-to-$n$ compression function $\mathrm{T}_5$, using only $3$ compression calls: $\mathrm{T}_5(m_1, m_2, m_3, m_4, m_5) := h_3( h_1(m_1, m_2)\oplus m_5, h_2(m_3, m_4)\oplus m_5) \oplus m_5$.

We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In particular, it provides birthday security for hashing $5$ inputs using three $2n$-to-$n$ compression calls, instead of only $4$ inputs in prior constructions.

Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where $t$ message blocks are hashed using only $3t/4$ calls to the $2n$-to-$n$ compression functions; a $25\%$ saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using $3$ (resp. $2$) parallel execution units; saving a factor of $4$ (resp. $2$) over the traditional MD-hashing, where parallelism does not help to process one message.

We also get a novel variant of a Merkle tree, where $t$ message blocks can be processed using $0.75(t-1)$ compression function calls and depth $0.86 \log_2 t$, thereby saving $25\%$ in the number of calls and $14\%$ in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree.

For the aggressive variant, we reduce the proof length to a $29\%$ overhead compared to Merkle trees ($1.29\log_2 t$ vs $\log_2 t$), but the verification time is now 14\% faster ($0.86\log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid $t$-block message.