International Association
for Cryptologic Research

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.

The Computer Science and Engineering Department of the University of California, Santa Cruz invites applications for PhD students and Post-doctoral fellows in the topics of (applied) cryptography, security and privacy, secure databases and systems. Applicants should have a background/interest in cryptography, searchable encryption, databases and systems, oblivious RAM and oblivious computation, secure multi-party computation, hardware enclaves, computer & cloud security.

PhD applicants should have a bachelor/master degree in computer science, electrical & computer engineering, information security, mathematics, or any other relevant area. Excellent analytical and mathematical skills are necessary, as well as a strong background in coding and software engineering.

If you are interested in research on either of the above areas you are encouraged to email me directly about your intent to apply---send me your CV and a short description of your research experience and interests, and a link to your personal website (if any). Please also submit your application here https://grad.soe.ucsc.edu/admissions(Computer Science & Engineering→ Apply to PhD) and mention my name in your application. Note that the application fee can be waived under certain conditions---please send me an email if you have any questions.

Post-doctoral applicants please email me your CV and your research statement (if available).

Closing Date for Application: January 11, 2021

Closing date for applications:

Contact: Assistant Prof. Ioannis Demertzis, idemertz (at) ucsc.edu

More information: https://grad.soe.ucsc.edu/admissions

Novi is building a hub of financial services, products and solutions that connect everyone, everywhere, creating greater opportunity for all. Its technical foundation is the open-sourced Diem (formerly known as Libra) blockchain network. Diem’s mission is to create a simple, borderless global currency and financial ecosystem that empowers billions of people. 

Novi Research is the research arm of Novi, and is of great importance due to the cutting-edge nature of the technical challenges and Novi’s openness to scrutiny.

The cryptography team at Facebook’s Novi Research is seeking research scientists/engineers and PhD interns (summer 2021) with expertise in all aspects of cryptography including but not limited to public-key cryptography, secure multiparty computation, zero knowledge proofs, authenticated data structures, accumulators, blockchain compression, auditability and privacy-enhancing technologies. The ideal candidates will have a keen interest in producing new science to advance this interdisciplinary fields, as well as supporting the productization of their results.

Closing date for applications:

Contact: Kostas Chalkias

Research Internships at Microsoft provide a dynamic environment for research careers with a network of world-class research labs led by globally-recognized scientists and engineers. Our researchers and engineers pursue innovation in a range of scientific and technical disciplines to help solve complex challenges in diverse fields, including computing, healthcare, economics, and the environment.

The Cryptography and Privacy Research Group at Microsoft Research seeks graduate students in applied cryptography and privacy for spring and summer internships. Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs.

We offer internship projects ranging from protocol design and security analysis to crypto and privacy engineering, so we encourage PhD students with any relevant experience to apply.

Please apply at: https://careers.microsoft.com/us/en/job/945055/Research-Intern-Privacy-and-Cryptography

Closing date for applications:

Contact: Kim Laine, Melissa Chase, or Esha Ghosh

The Department of Computer Science at the University of Surrey is seeking to recruit a full-time researcher to the Surrey Centre for Cyber Security (SCCS). The successful candidate will join the new DECaDE Next Stage Digital Economy Centre for the Decentralised Digital Economy (http://decade.ac.uk), a multidisciplinary UKRI-funded Centre with the University of Surrey, the University of Edinburgh, and the Digital Catapult.

The Centre is initially focused on three themes: value co-creation in the digital economy, data trusts for identity and data, and the world of work and the gig economy. This post will work on challenges around decentralized identity and personal data, and approaches across distributed platforms such as Distributed Ledgers. The post-holder will also have the freedom and opportunity to shape further projects as the Centre develops.

Surrey is recognized by the National Cyber Security Centre as an Academic Centre of Excellence in Cyber Security Research and offers a thriving research environment with world leading researchers. Our research includes data privacy, privacy preserving security, applied cryptography, distributed and network systems, protocol design and analysis, and security verification.

The position offers the platform for the research fellow to work within a group and develop skills to become an independent researcher and to contribute to the DECaDE vision. The successful candidate will work under the direction of Professor Steve Schneider. Significant interaction with project partners is encouraged, and the dissemination strategy may involve national and international travel, with many personal development opportunities.

We are looking for applicants that demonstrate strong research and analytical skills, have strong communication skills and enthusiasm for developing their own research ideas. Applicants should have an understanding of cyber security, and how to design and reason about systems. Knowledge of Distributed Ledger Technologies would be an advantage.

The post is available for 24 months in the first instance to begin on February 1st 2021 or soon after.

Closing date for applications:

Contact: Professor Steve Schneider: s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=035220-R

Recent analyses reported independently by Bonnetain-Schrottenloher and Peikert in Eurocrypt 2020, significantly reduce the estimated quantum security provided by the isogeny-based commutative group action protocol CSIDH. In this paper the CSIDH quantum security is revisited through a comprehensive analysis of the computational cost associated to the quantum collimation sieve attack. Furthermore, we propose a set of primes that can be applied to obtain large instantiations of CSIDH achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations supported by the new Vélu formulae.

In this paper, we present a strong, formal, and general-purpose cryptographic model for privacy-preserving authenticated key exchange (PPAKE) protocols. PPAKE protocols are secure in the traditional AKE sense but additionally guarantee the confidentiality of the identities used in communication sessions. Our model has several useful and novel features, among others: it is a proper extension of classical AKE models, guarantees in a strong sense that the confidentiality of session keys is independent from the secrecy of the used identities, and it is the first to support what we call dynamic modes, where the responsibility of selecting the identities of the communication partners may vary over several protocol runs. To the best of our knowlegde, this implements the first technical approach to deal with protocol options in AKE security models. We show the validity of our model by applying it to the cryptographic core of IPsec IKEv2 with signature-based authentication where the need for dynamic modes is practically well-motivated. In our analysis, we not only show that this protocol provides strong classical AKE security guarantees but also that the identities that are used by the parties remain hidden in successful protocol runs. Historically, the Internet Key Exchange (IKE) protocol was the first real-world AKE to incorporate privacy-preserving techniques. However, lately privacy-preserving techniques have gained renewed interest in the design process of important protocols like TLS 1.3 (with encrypted SNI) and NOISE. We believe that our new model can be a solid foundation to analyze these and other practical protocols with respect to their privacy guarantees, in particular, in the now so wide-spread scenario where multiple virtual servers are hosted on a single machine.

Recent studies and incidents have shed light on the threat posed by botnets consisting of a large set of relatively weak IoT devices that host an army of bots. However, little is known about the threat posed by a small set of devices that are not infected with malware and do not host bots. In this paper, we present Botnet-IND (indirect), a new type of distributed attack which is launched by a botnet consisting of botless IoT devices. In order to demonstrate the feasibility of Botnet-IND on commercial, off-the-shelf IoT devices, we present Piping Botnet, an implementation of Botnet-IND on smart irrigation systems, a relatively new type of IoT device which is used by both the private and public sector to save water; such systems will likely replace all traditional irrigation systems in the next few years. We perform a security analysis of three of the five most sold commercial smart irrigation systems (GreenIQ, BlueSpray, and RainMachine). Our experiments demonstrate how attackers can trick such irrigation systems (Wi-Fi and cellular) without the need to compromise them with malware or bots. We show that in contrast to traditional botnets that require a large set of infected IoT devices to cause great harm, Piping Botnet can pose a severe threat to urban water services using a relatively small set of smart irrigation systems. We found that only 1,300 systems were required to drain a floodwater reservoir when they are maliciously prog

The security of cryptographic primitives typically relies on the storage of private secrets by each participant in a perfect manner. However, increasingly, side-channel attacks are demonstrating the pitfalls of assuming these cryptographic entities as opaque monolithic objects over the entire duration the primitive remains alive. Motivated by such concerns, there is a significant interest in revisiting well-established cryptographic primitives and their implementations to identify whether their security continues to hold in the presence of such side-channel attacks.

%Fundamental primitives, like secret-sharing schemes when performed over carelessly chosen finite fields lead to devastating security breaches. %For example, linear secret sharing schemes over characteristic 2 fields are susceptible to an adversary who performs only one-bit leakage from the shares of all the parties. Although there are compilers to convert any secret sharing scheme into one that is robust to local leakage on each of their shares, it is not feasible to replace every instance of traditional secret sharing schemes in use with a leakage-resilient counterpart. Beyond efficiency considerations, there may be an appropriate structure in specific secret-sharing schemes that are fundamental to their usage in a particular context. For example, the use of a linear secret sharing scheme helps perform secure aggregation of statistics in parallel (for example, the sum of the private inputs of the participants) even in the presence of malicious parties. The reconstruction threshold of these secret sharing schemes determines the threshold of corruption permissible in the secure computation protocol; a lower reconstruction threshold implies a higher efficiency.

This paper makes a two-fold contribution. First, we continue to study the local leakage resilience of Reed-Solomon codes as initiated by Benhamouda, Degwekar, Ishai, and Rabin (2018). We improve their lower bound on the reconstruction threshold for Reed Solomon codes from $0.907n$ to $0.867n$ for one-bit leakage from each secret share, where $n$ represents the number of parties receiving the secret shares.

Next, we explore whether, in the presence of local leakage, there is something inherent to maximum-distance separable (MDS) codes (Reed Solomon code is a particular example from this class of codes) that innately demands high reconstruction thresholds. Towards this investigation, we study random MDS codes and their necessary reconstruction threshold to remain resilient to a constant local leakage from each share. Given any $\delta\in(0,1/2),$ we prove that most random MDS codes over suitably large fields with reconstruction threshold $(1/2 + \delta)n$ are resilient to constant local leakage.

In terms of techniques, both results rely on a Fourier-analytic approach to this problem. In particular, the second result relies on new and subtle analysis techniques for random MDS codes, which we believe shall be of independent interest.

Finally, we also contribute to the impossibility of designing secret-sharing schemes based on MDS codes over prime-order fields, where the dimension of the code is very small. If one insists on exponentially small indistinguishability among the shares generated by two different secrets, then the dimension of the code needs to be $\Omega(n/\log n)$ even when the adversary obtains only $m=1$ bit leakage from each of the shares and the field size is arbitrarily large.

In this short note, we explain how to reduce the time to compute all $N$ proofs in the Pointproofs vector commitment (VC) scheme by Gorbunov et al., from $O(N^2)$ time to $O(N\log{N})$. The key ingredient is representing the computation of all proofs as a product between a Toeplitz matrix and the committed vector, which can be computed fast using Discrete Fourier Transforms (DFTs). We quickly prototype our algorithm in C++ and show it is much faster than the naive algorithm for computing all proofs in Pointproofs.

Almost perfect nonlinear functions possess the optimal resistance to the differential cryptanalysis and are widely studied. Most known APN functions are obtained as functions over finite fields $GF(2^n)$ and very little is known about combinatorial constructions of them in $\mathbb{F}_2^n$. In this work we propose two approaches for obtaining quadratic APN functions in $\mathbb{F}_2^n$. The first approach exploits a secondary construction idea, it considers how to obtain a quadratic APN function in $n+1$ variables from a given quadratic APN function in $n$ variables using special restrictions on new terms. The second approach is searching quadratic APN functions that have matrix form partially filled with standard basis vectors in a cyclic manner. This approach allowed us to find a new APN function in 7 variables. We proved that the updated list of quadratic APN functions in dimension 7 is complete up to CCZ-equivalence.

The Coding and Information Transmission Group at the Institute of Computer Science, the University of Tartu, Estonia, is looking for a Research Fellow (post-doc). The position is available almost immediately (subject to necessary paperwork), and could last until 31 December 2022. The ideal candidate will have strength in one or more of the following areas:

• algebraic/combinatorial coding theory;
• coding techniques/coded modulations/practical LDPC and LDPC-like codes;
• coding for distributed data storage/PIR/load balancing;
• code-based cryptography.

University of Tartu offers internationally-competitive salary packages. Cost of living in Estonia is quite low, see e.g. http://www.expatistan.com/cost-of-living. During the COVID pandemic, it is possible to start working remotely, and then to move to Estonia once the situation normalizes.

A successful candidate should:
• hold a Ph.D. degree;
• have a strong publication record at outstanding venues.

To apply, please submit the following documents (by email):
• Application letter
• Curriculum vitae
• Publication list

Deadline for applications: 15th December 2020

Closing date for applications:

Contact: Vitaly Skachek, e-mail vitaly.skachek at ut.ee, see http://www.cs.ut.ee/~vitaly/ . Do not hesitate to contact us in the case of questions.

The fixed-Hessian minimisation method can be used to implement privacy-preserving machine learning training from homomorphic encryption. This is a relatively under-explored part of the literature, with the main prior work being that of Bonte and Vercauteren (BMC Medical Genomics, 2018), who proposed a simplified Hessian method for logistic regression training over the BFV homomorphic encryption scheme. Our main contribution is to revisit the fixed- Hessian approach for logistic regression training over the CKKS homomorphic encryption scheme. We improve on the prior work in several aspects, most notably showing how the native encoding in CKKS can be used to take advantage of SIMD operations. We implement our new fixed-Hessian approach in SEAL and compare it to more commonly-used minimisation methods, based on Gradient Descent and Nesterov’s Accelerated Gradient Descent. We find that the fixed-Hessian approach exhibits fast run time and comparable accuracy to these alternative approaches. Moreover, it can be argued to be more practical in the privacy-preserving training context, as no step size parameter needs to be chosen.

As an additional contribution, we describe and implement three distinct training algorithms, based on Gradient Descent, Nesterov’s Accelerated Gradient Descent, and a fixed-Hessian method respec- tively, to achieve privacy-preserving ridge regression training from homomorphic encryption. To the best of our knowledge, this is the first time homomorphic encryption has been used to implement ridge regression training on encrypted data.