International Association
for Cryptologic Research

Event date: 10 December to 15 June 2021
Submission deadline: 15 June 2021

Event date: 6 July to 8 July 2021
Submission deadline: 16 February 2021
Notification: 15 April 2021

Event date: 7 July to

Project Title: Social and Societal Foundations of Cryptography: The Case of Large-Scale Protests. The Centre for Doctoral Training in Cyber Security for the Everyday at Royal Holloway seeks to recruit PhD students who will explore the social and societal foundations of cryptography. Cryptography is a field that actively interrogates its foundations. These foundations are, unsurprisingly and sensibly, understood to be of the complexity-theoretic and mathematical variety. However, cryptographic security notions -- and everything that depends on them -- do not exist in a vacuum, they have reasons to be. While the immediate objects of cryptography are not social relations, it presumes and models them. This fact is readily acknowledged in the introductions of cryptographic papers which illustrate the utility of the work by reference to some social situation where several parties have conflicting ends but a need or desire to interact. Yet, this part of the definitional work has not received the same rigour from the cryptographic community as complexity-theoretic and mathematical questions. This project aims to take first steps towards remedying this situation by grounding cryptographic security notions in findings emerging from ethnographic fieldwork in adversarial situations. In particular, it considers protesters in large-scale protests and aims to understand their security needs, practices and the technologies they rely upon. The project then also analyses these technologies, i.e. attempts to break their security, and proposes new solutions based on the findings from fieldwork. By bringing cryptographic security notions to *the field*, the project provokes a series of security questions about, for example, confidentiality and anonymity in online and offline networks, trust relations and how to establish them, onboarding and authentication practices. We seek applicants with either a background in mathematics and/or computer science or related disciplines or a background in ethnography or experience using related qualitative social science methods

Closing date for applications:

Contact: The studentship includes * Tuition fees: * Maintenance: £21,285 for each academic year. The CDT in Cyber Security for the Everyday can offer up to ten studentships per year, three of which can be awarded to international students (which includes EU and EEA.) contact Prof Martin Albrecht

TU Berlin, Faculty IV (Electrical Engineering and Computer Science), Institute for Software Engineering and Theoretical Computer Science and the Berlin Institute for Foundations of Learning and Data (BIFOLD) invites applications for the position of a University Professorship - salary grade W3 in the field of "Machine Learning and IT Security". Faculty IV Reference number: IV-756/20 (starting at the earliest possible / unlimited / closing date for applications 04/01/21) Working field: We are seeking qualified applicants who based on previous work will conduct independent research and teaching in two or more of the following areas: (i) Machine Learning for IT-Security (ii) for IT-Security for Machine Learning (iii) Scalable IT-Security (iv) Security fo Data Science Systems and Platforms. Requirements: Applicants must fulfill the appointment requirements according to §100 BerlHG. The prerequisites are a completed scientific university degree with a focus on computer science, the special qualification for scientific work (usually proven by a doctorate) in the field of machine learning/IT security, additional scientific achievements (habilitation or equivalent scientific achievements) as well as pedagogical aptitude and experience, to be given proof of by a teaching portfolio (for more information see TUB website, quick access no. 144242). Research experience in the areas outlined in the job description, experience in national and international research cooperations (proven by relevant stays abroad and/or significant participation in projects) are also required. Teaching will be conducted in both German and English. For the complete job posting, please follow the link https://stellenticket.de/86502/TUB/?lang=en.

Closing date for applications:

Contact: Ms. Anita Hummel

More information: https://stellenticket.de/86502/TUB/?lang=en

Axelar is building a decentralized network that connects dApp builders with blockchain ecosystems, applications and users for frictionless cross-chain communication. Our team consists of experienced engineers and researchers in distributed systems, cryptography, and consensus. We’re growing our team and looking for engineers who’re interested in building the new financial stack from the ground up.

• Understanding of public and secret key: encryption, signatures (Ed25519, ECDSA, etc.).
• Knowledge of networking technologies, specifically TCP/IP, RPC and the related protocols.
• Knowledge of operating systems, file systems, and memory on macOS and Linux.
• Experience with engineering security practices.
• Ability to find, exploit and fix bugs, security vulnerabilities in software.
• General knowledge of blockchain technologies.
• Experience with Go and/or Rust.
• Bonus: understanding of elliptic curve cryptography, multi-party computation and threshold schemes.

More info at: https://axelar.network

Closing date for applications:

Contact: Sergey Gorbunov: sergey [at] axelar [dot] network

More information: https://axelar.network

The Ira A. Fulton Schools of Engineering at Arizona State University (ASU) seek applicants for a tenure-track/tenured faculty position in the intersection of Distributed Systems / Blockchain / Security in the School of Computing, Informatics, and Decision Systems Engineering (CIDSE). Areas of interest include, but are not limited to: the robustness, security, and resilience of distributed systems; secure distributed consensus algorithms; internet-scale distributed security; distributed cybersecurity approaches; theory and applications of blockchains and cryptography; secure distributed learning; game-theoretic approaches to cybersecurity; secure multiparty computation, data management, and cryptography; the distributed Internet of Things; and other emerging areas covering various intersections of distributed systems, blockchain, and cybersecurity. Application deadline is January 15, 2021.

More details at https://apply.interfolio.com/81408. For further information or questions about this position please contact Professor Yan Shoshitaishvili at (yans@asu.edu)

Closing date for applications:

Contact: Yan Shoshitaishvili (yans@asu.edu); Ni Trieu (nitrieu@asu.edu)

More information: https://apply.interfolio.com/81408

We present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attack is both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. We implemented and tested the attack against major open source homomorphic encryption libraries, including \HEAAN, \SEAL, \HElib\ and \PALISADE, and when computing several functions that often arise in applications of the CKKS scheme to machine learning on encrypted data, like mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series.

The attack shows that the traditional formulation of \INDCPA\ security (or indistinguishability against chosen plaintext attacks) achieved by CKKS does not adequately capture security against passive adversaries when applied to approximate encryption schemes, and that a different, stronger definition is required to evaluate the security of such schemes.

We provide a solid theoretical basis for the security evaluation of homomorphic encryption on approximate numbers (against passive attacks) by proposing new definitions, that naturally extend the traditional notion of \INDCPA\ security to the approximate computation setting. We propose both indistinguishability-based and simulation-based variants, as well as restricted versions of the definitions that limit the order and number of adversarial queries (as may be enforced by some applications). We prove implications and separations among different definitional variants, and discuss possible modifications to CKKS that may serve as a countermeasure to our attacks.

An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key $k$ for a secure pseudorandom function $F$, and the client has an input $x$ for the function. At the end of the protocol the client learns $F(k,x)$, and nothing else, and the server learns nothing. An OPRF is verifiable if the client is convinced that the server has evaluated the PRF correctly with respect to a prior commitment to $k$. OPRFs and verifiable OPRFs have numerous applications, such as private-set-intersection protocols, password-based key-exchange protocols, and defense against denial-of-service attacks. Existing OPRF constructions use RSA-, Diffie-Hellman-, and lattice-type assumptions. The first two are not post-quantum secure.

In this paper we construct OPRFs and verifiable OPRFs from isogenies. Our main construction uses isogenies of supersingular elliptic curves over $\mathbb{F}_{p^{2}}$ and tries to adapt the Diffie-Hellman OPRF to that setting. However, a recent attack on supersingular-isogeny systems due to Galbraith et al. [ASIACRYPT 2016] makes this approach difficult to secure. To overcome this attack, and to validate the server's response, we develop two new zero-knowledge protocols that convince each party that its peer has sent valid messages. With these protocols in place, we obtain an OPRF in the SIDH setting and prove its security in the UC framework.

Our second construction is an adaptation of the Naor-Reingold PRF to commutative group actions. Combining it with recent constructions of oblivious transfer from isogenies, we obtain an OPRF in the CSIDH setting.

Access and search pattern leakage from range queries are detrimental to the security of encrypted databases, as evidenced by a large body of work on efficient attacks that reconstruct one-dimensional databases. Recently, the first attack in two-dimensions showed that higher-dimensional databases are also in danger. This attack requires complete information for reconstruction. In this paper, we develop reconstructions that require less information. We present an order reconstruction attack that only depends on access pattern leakage, and empirically show that the order allows the attacker to infer the geometry of the underlying data. Notably, this attack achieves full database reconstruction when the 1D horizontal and vertical projections of the points are dense. We also give an approximate database reconstruction attack that is distribution-agnostic and works with any subset of the possible responses, given the order of the database. We support our results with experiments on real-world databases with queries drawn from various distributions. Our attack is effective, e.g. we achieve good reconstructions with 15% percent of the queries under a Gaussian distribution.

Cloud computing and cloud storage are among the most efficient technologies for storing and processing metadata. But there are many privacy concerns within this domain. Most of the challenges are coming from trusted or semi trusted cloud servers where some computations must be applied to high confidential data. Data encryption can solve some confidentiality issues on the cloud but it is not easy to provide privacy preserving data processing services such as searching a query over encrypted data. On the other hand implementing searchable encryption algorithms in cloud infrastructure helps providing data confidentiality and privacy preserving data processing and can provide searching capability as well, which is the most important step of selecting a document. First in this article, some injection attacks against searchable public key encryption schemes are described. To be more specific message injection attack and index injection attack are applied against PEKS and PERKS schemes. Afterwards, two new schemes are proposed that are secure against them and are based of dPEKS and SAE-I. Finally, efficiency and security of proposed schemes are analyzed, and some implementation issues were discussed.

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta$-uniform functions. This leads to an open problem on APN functions. We also improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound improves upon the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta$-uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide two upper bounds and study the tightness of the second (which is tighter when $m$ is near $n$); this poses an interesting question on APN functions, to which we answer negatively. We finally improve the bound on the differential uniformity, under an additional condition.

We study the notion of zero-knowledge secure against quantum polynomial-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting. Despite being extensively studied in the classical setting, concurrent composition in the quantum setting has hardly been studied. We initiate a formal study of concurrent quantum zero-knowledge. Our results are as follows:

- Bounded Concurrent QZK for NP and QMA: Assuming post-quantum one-way functions, there exists a quantum zero-knowledge proof system for NP in the bounded concurrent setting. In this setting, we fix a priori the number of verifiers that can simultaneously interact with the prover. Under the same assumption, we also show that there exists a quantum zero-knowledge proof system for QMA in the bounded concurrency setting.

- Quantum Proofs of Knowledge: Assuming quantum hardness of learning with errors with cloning security (a novel variant of learning with errors), there exists a bounded concurrent zero-knowledge proof system for NP satisfying quantum proof of knowledge property. Our extraction mechanism simultaneously allows for extracting the witness from an unbounded prover with probability negligibly close to the acceptance probability (extractability) and also ensures that the prover's state after extraction is statistically close to the prover's state after interacting with the verifier (simulatability). The seminal work of [Unruh EUROCRYPT'12], and all its followups, satisfied a weaker version of extractability property and moreover, did not achieve simulatability. Our result yields a proof of quantum knowledge system for QMA with better parameters than prior works.

We construct a zero knowledge argument system with polylogarithmic communication complexity where the prover runs in linear time and the verifier runs in polylogarithmic time. This achieves a central goal in the area of efficient zero knowledge.

Our result is a direct consequence of a new interactive oracle proof (IOP) that simultaneously achieves linear-time proving and zero knowledge. We construct an IOP where, for the satisfiability of an $N$-gate arithmetic circuit over any field of size $\Omega(N)$, the prover uses $O(N)$ field operations and the verifier uses $\mathrm{polylog}(N)$ field operations (with proof length $O(N)$ and query complexity $\mathrm{polylog}(N)$. Polylogarithmic verification is achieved in the holographic setting for every circuit (the verifier has oracle access to a linear-time-computable encoding of the circuit whose satisfiability is being proved).

We consider the problem of verifiable and private delegation of computation [Gennaro et al. CRYPTO'10] in which a client stores private data on an untrusted server and asks the server to compute functions over this data. In this scenario we aim to achieve three main properties: the server should not learn information on inputs and outputs of the computation (privacy), the server cannot return wrong results without being caught (integrity), and the client can verify the correctness of the outputs faster than running the computation (efficiency). A known paradigm to solve this problem is to use a (non-private) verifiable computation (VC) to prove correctness of a homomorphic encryption (HE) evaluation on the ciphertexts. Despite the research advances in obtaining efficient VC and HE, using these two primitives together in this paradigm is concretely expensive. Recent work [Fiore et al. CCS'14, PKC'20] addressed this problem by designing specialized VC solutions that however require the HE scheme to work with very specific parameters; notably HE ciphertexts must be over $\mathbb{Z}_q$ for a large prime $q$.

In this work we propose a new solution that allows a flexible choice of HE parameters, while staying modular (based on the paradigm combining VC and HE) and efficient (the VC and the HE schemes are both executed at their best efficiency). At the core of our new protocol are new homomorphic hash functions for Galois rings. As an additional contribution we extend our results to support non-deterministic computations on encrypted data and an additional privacy property by which verifiers do not learn information on the inputs of the computation.

Modern digital signature schemes can provide more guarantees than the standard notion of (strong) unforgeability, such as offering security even in the presence of maliciously generated keys, or requiring to know a message to produce a signature for it. The use of signature schemes that lack these properties has previously enabled attacks on real-world protocols. In this work we revisit several of these notions beyond unforgeability, establish relations among them, provide the first formal definition of non re-signability, and a transformation that can provide these properties for a given signature scheme in a provable and efficient way.

Our results are not only relevant for established schemes: for example, the ongoing NIST PQC competition towards standardizing post-quantum signature schemes has six finalists in its third round. We perform an in-depth analysis of the candidates with respect to their security properties beyond unforgeability. We show that many of them do not yet offer these stronger guarantees, which implies that the security guarantees of these post-quantum schemes are not strictly stronger than, but instead incomparable to, classical signature schemes. We show how applying our transformation would efficiently solve this, paving the way for the standardized schemes to provide these additional guarantees and thereby making them harder to misuse.

ForkAE is a NIST lightweight cryptography candidate that uses the forkcipher primitive in two modes of operation -- SAEF and PAEF -- optimized for authenticated encryption of the shortest messages. SAEF is a sequential and online AEAD that minimizes the memory footprint compared to its alternative parallel mode PAEF, catering to the most constrained devices. SAEF was proven AE secure against nonce-respecting adversaries.

Due to their more acute and direct exposure to device misuse and mishandling, in most use cases of lightweight cryptography, nonce reuse presents a very realistic attack vector. Furthermore, many lightweight applications mandate security for their online AEAD schemes against block-wise adversaries. Surprisingly, very few NIST lightweight AEAD candidates come with provable guarantees against these security threats. In this work, we investigate the provable security guarantees of SAEF when nonces are repeated under a refined version of the notion of online authenticated encryption OAE given by Fleischmann et al. in 2012. We apply Using the coefficient H technique we show that, with no modifications, SAEF is OAE secure up to the birthday security bound, i.e., up to $2^{n/2}$ processed blocks of data, where $n$ is the block size of the forkcipher. The implications of our work are that SAEF is safe to use in a block-wise fashion, and that if nonces get repeated, this has no impact on ciphertext integrity and confidentiality only degrades by a limited extent up to repetitions of common message prefixes.

Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus. Recently Datta et al. (FSE’19), and then Kim et al. (Eurocrypt’20) proved that DbHtS constructions are secure beyond birthday bound in single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in multi-user setting.

In this work, we revisit the security of DbHtS MACs in multi-user setting. We propose a generic framework to prove beyond-birthday-bound security for DbHtS constructions. We demonstrate the usability of this framework with applications to key-reduced variants of DbHtS MACs, including 2k-SUM-ECBC, 2k-PMAC_Plus and 2k-LightMAC_Plus. Our results show that the security of these constructions will not degrade as the number of users grows. On the other hand, our results also indicate that these constructions are beyond-birthday-bound secure in both single-user and multi-user setting without additional domain separation, which are used in prior works to simplify the analysis.

Moreover, we find a severe flaw in 2kf9, which is proved to be secure beyond birthday bound by Datta et al. (FSE’19). We can successfully forge a tag with probability 1 without making any queries. We go further to show attacks with birthday-bound complexity on several variants of 2kf9.

Ledger systems are applications run on peer-to-peer networks that provide strong integrity guarantees. However, these systems often have high participation costs. For a server to join this network, the bandwidth and computation costs grow linearly with the number of state transitions processed; for a client to interact with a ledger system, it must either maintain the entire ledger system state like a server or trust a server to correctly provide such information. In practice, these substantial costs centralize trust in the hands of the relatively few parties with the resources to maintain the entire ledger system state.

The notion of *incrementally verifiable computation*, introduced by Valiant (TCC '08), has the potential to significantly reduce such participation costs. While prior works have studied incremental verification for basic payment systems, the study of incremental verification for a general class of ledger systems remains in its infancy.

In this paper we initiate a systematic study of incremental verification for ledger systems, including its foundations, implementation, and empirical evaluation. We formulate a cryptographic primitive providing the functionality and security for this setting, and then demonstrate how it captures applications with privacy and user-defined computations. We build a system that enables incremental verification, for applications such as privacy-preserving payments, with universal (application-independent) setup. Finally, we show that incremental verification can reduce participation costs by orders of magnitude, for a bare-bones version of Bitcoin.

We present a modification to RingCT protocol with stealth addresses that makes it compatible with Delegated Proof of Stake based consensus mechanisms called Delegated RingCT. Our scheme has two building blocks: a customised version of an Integrated Signature and Encryption scheme composed of a public key encryption scheme and two signature schemes (a digital signature and a linkable ring signature); and non-interactive zero knowledge proofs. We give a description of the scheme, security proofs and a prototype implementation whose benchmarking is discussed. Although Delegated RingCT does not have the same degree of anonymity as other RingCT constructions, we argue that the benefits that the compatibility with DPoS consensus mechanisms brings constitute a reasonable trade-off for being able to develop an anonymous decentralised cryptocurrency faster and more scalable than existing ones.