International Association
for Cryptologic Research

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.

This paper presents the first automatic technique for proving not only protocols but also primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Bernstein et al. recently introduced a system ``Elligator'' for steganographic key distribution. At the heart of their construction are invertible maps between a finite field $\mathbb{F}$ and an elliptic curve $\mathcal{E}$ over $\mathbb{F}$. There are two such maps, called $\phi$ in the ``Elligator 1'' system, and $\psi$ in the ``Elligator 2'' system.

Here we show two ways to construct hash functions from $\psi$ which are indifferentiable from a random oracle. Because $\psi$ is relatively simple, our analyses are also simple. One of our constructions uses a novel ``wallpapering'' approach, whereas the other uses the hash-twice-and-add approach of Brier et al.

Benchmarking the performance of companies is essential to identify improvement potentials in various industries. Due to a competitive environment, this process imposes strong privacy needs, as leaked business secrets can have devastating effects on participating companies. Consequently, related work proposes to protect sensitive input data of companies using secure multi-party computation or homomorphic encryption. However, related work so far does not consider that also the benchmarking algorithm, used in today's applied real-world scenarios to compute all relevant statistics, itself contains significant intellectual property, and thus needs to be protected. Addressing this issue, we present PCB — a practical design for Privacy-preserving Company Benchmarking that utilizes homomorphic encryption and a privacy proxy — which is specifically tailored for realistic real-world applications in which we protect companies' sensitive input data and the valuable algorithms used to compute underlying key performance indicators. We evaluate PCB's performance using synthetic measurements and showcase its applicability alongside an actual company benchmarking performed in the domain of injection molding, covering 48 distinct key performance indicators calculated out of hundreds of different input values. By protecting the privacy of all participants, we enable them to fully profit from the benefits of company benchmarking.

The lack of privacy in the first generation of cryptocurrencies such as Bitcoin, Ethereum, etc. is a well known problem in cryptocurrency research. To overcome this problem, several new cryptocurrencies were designed to guarantee transaction privacy and anonymity for their users (examples include ZCash, Monero, etc.).

However, the anonymity provided by such systems appears to be fundamentally problematic in current business and legislation settings: banks and other financial institutions must follow rules such as "Know your customer" (KYC), "Anti Money Laundering" (AML), etc. It is also well known that the (alleged or real) anonymity guarantees provided by cryptocurrencies have attracted ill-intentioned individual to this space, who look at cryptocurrencies as a way of facilitating illegal activities (tax-evasion, ransom-ware, trading of illegal substances, etc.).

The fact that current cryptocurrencies do not comply with such regulations can in part explain why traditional financial institutions have so far been very sceptical of the ongoing cryptocurrency and Blockchain revolution.

In this paper, we propose a novel design principle for identity management in Blockchains. The goal of our design is to maintain privacy, while still allowing compliance with current regulations and preventing exploitations of Blockchain technology for purposes which are incompatible with the social good.

A quantum bit commitment scheme is to realize bit (rather than qubit) commitment by exploiting quantum communication and quantum computation. In this work, we study the binding property of a generic quantum computationally-binding bit commitment scheme composed in parallel, which can be viewed as a quantum string commitment scheme. We show that the resulting scheme satisfies a stronger quantum computational binding property than the trivial honest-binding, which we call the predicate-binding. Intuitively and very roughly, the predicate-binding property guarantees that given any inconsistent predicate pair over a set of strings (i.e. no strings in this set can satisfy both predicates), if a (claimed) quantum commitment can be opened so that the revealed string satisfies one predicate with certainty, then the same commitment cannot be opened so that the revealed string satisfies the other predicate (except for a negligible probability).

As an application, we plug a generic quantum (perfectly/statistically-hiding) computationally-binding bit commitment scheme in Blum's zero-knowledge protocol for the NP-complete language Hamiltonian Cycle. Then the quantum computational predicate-binding property of the commitments immediately translates into the quantum computational soundness of the protocol. Combined with the perfect/statistical zero-knowledge property which can be similarly established as Watrous [Wat09], as well as known constructions of quantum computationally-binding bit commitment scheme, this gives rise to the first quantum perfect/statistical zero-knowledge argument system for all NP languages based solely on quantum-secure one-way functions.

The typical login protocol for authenticating a user to a web service involves the client sending a password over a TLS-secured channel to the service, occasionally deployed with the password being prehashed. This widely-deployed paradigm, while simple in nature, is prone to both inadvertent logging and eavesdropping attacks, and has repeatedly led to the exposure of passwords in plaintext.

Partly to address this problem, symmetric and asymmetric PAKE protocols were developed to ensure that the messages exchanged during an authentication protocol reveal nothing about the passwords. However, these protocols inherently require at least two messages to be sent out: one from each party. This limitation hinders wider adoption, as the most common login flow consists of a single message from client to the login server. The ideal solution would retain the password privacy properties of asymmetric PAKEs while allowing the protocol to be a drop-in replacement into legacy password-over-TLS deployments.

With these requirements in mind, we introduce the notion of credential-hiding login, which enables a client to authenticate itself by sending a single message to the server, while ensuring the correct verification of credentials and maintaining credential privacy in the same strong sense as guaranteed by asymmetric PAKEs. We initiate a formal study of this primitive in the Universal Composability framework, design and implement a practical password-based protocol using identity-based encryption, and report on its performance. We also construct a variant of credential-hiding login for fuzzy secrets (e.g. biometrics), proven secure based on the Learning With Errors (LWE) assumption.

Quantum pseudorandom functions (QPRFs) extend the classical security of a PRF by allowing the adversary to issue queries on input superposition. Zhandry [Zhandry, FOCS 2012] showed a separation between the two notions and proved that common construction paradigms are also quantum secure, albeit with a new ad-hoc analysis. In this work, we revisit the question of constructing QPRFs and propose a new method starting from small-domain (classical) PRFs: At the heart of our approach is a new domain-extension technique based on bipartite expanders. Interestingly, our analysis is almost entirely classical. As a corollary of our main theorem, we obtain the first (approximate) key homomorphic quantum PRF based on the quantum intractability of the learning with errors problem.

RSA key generation requires devices to generate large prime numbers. The na\"ive approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers $\{p_i\}$.

Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against side-channel analysis. Here we describe an improvement on Joye et al.'s sieve based on the Chinese Remainder Theorem (CRT). We also describe a new sieve method using quadratic residuosity which is simpler and faster than previously known methods, and which can produce values in desired RSA parameter ranges such as $(2^{n-1/2}, 2^n)$ with minimal additional work. The same methods can be used to generate strong primes and DSA moduli.

We also demonstrate a technique for RSA private key operations using the Chinese Remainder Theorem (RSA-CRT) without $q^{-1}$ mod $p$. This technique also leads to inversion-free batch RSA and inversion-free RSA mod $p^k q$.

We demonstrate how an embedded device can use our key generation and RSA-CRT techniques to perform RSA efficiently without storing the private key itself: only a symmetric seed and one or two short hints are required.

Side-channel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this tutorial, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman, the public-key cryptosystems in common use today. We categorize the known techniques by the structure of the information that is learned by the attacker, and give simplified examples for each technique to illustrate the underlying ideas.

In this paper we construct and consider a signature scheme with evolving secret key, where there is used Type 3 pairing. The idea is based on some properties of binary trees, with a number of leaves being the same as a number of time periods in the scheme. This lets us to gain such conditions, that allows to prove the forward-security of the considered scheme in the random oracle model. The proof is conducted by reducing the security of the scheme to the difficulty of solving a certain counterpart of the Weak $\ell$-th Bilinear Diffie-Hellman Inversion problem. In addition to that, we construct an interactive signature scheme with evolving private key and justify that it is forward-secure blind scheme.

Seven years ago, a famous case in which data from a Fitbit tracker was used in the courtroom in a personal injury case heralded a new age: the age of testifying wearable devices. Prior to that, data from wearable devices was used in various areas, including medicine, advertising, and scientific research, but the use of such data in the Fitbit case attracted the interest of a new sector: the legal sector. Since then, lawyers, investigators, detectives, and police officers have used data from pacemakers and smartwatches in order to prove/disprove allegations regarding wearable device owners in several well-known cases (sexual assault, arson, personal injury, etc.). In this paper, we discuss testifying wearable devices. We explain the advantages of wearable devices over traditional IoT devices in the legal setting, the parties involved in cases in which a wearable device was used to testify against/for the device owner, and the information flow. We then focus on an interesting area of research: intoxication detection. We explain the motivation to detect whether a subject was intoxicated and explain the primary scientific gap in this area. In order to overcome this gap, we suggest a new method for detecting whether a subject was intoxicated based on free gait data obtained from a wearable device. We evaluate the performance of the proposed method in a user study involving 30 subjects and show that motion sensor data obtained from a smartphone and fitness tracker from eight seconds of free gait can indicate whether a subject is/was intoxicated (obtaining an AUC of 0.97) and thus be used as testimony. Finally, we analyze the current state and the near future of the age of testifying wearable devices and explain why we believe that (1) we are still at the beginning of this age despite the fact that seven years has passed since the original court case, and (2) the number of cases in which wearable device data is used to testify for/against the device owner is expected to increase significantly in the next few years.

CRYSTALS-KYBER and SABER are two lattice-based encryption algorithms in the third round finalists of NIST’s post-quantum cryptography standardization project. In ProvSec 2020, Wang et al. introduced a notion of “meta-PKE” for (ring) Learning With Errors crypto mechanism. They also proposed a key reuse attack on NewHope and LAC cryptosystems which meet the meta-PKE model. In their attack, the encryptor Bob’s partial (or even all) secrets can be recovered under the key reuse scenario. In this paper, we consider the meta-PKE model inCRYSTALS-KYBER and SABER. By improving Wang et al.’s method, we show that our proposed attacks cost only 4, 3, and 4 queries to recover Bob’s secrets for any security levels of I (AES-128), III (AES-192), and V (AES-256), respectively in CRYSTALS-KYBER. Simultaneously, only 6, 4, and 4 queries are required to recover Bob’s secret for security levels I, III, and V in SABER.

In a witness encryption scheme, to decrypt a ciphertext associated with an NP statement, the decrypter takes as input a witness testifying that the statement is in the language. When the statement is not in the language, then the message is hidden. Thus far, the only provably secure constructions assume the existence of indistinguishability obfuscation (iO) and multilinear maps (MMaps).

We make progress towards building polynomially efficient witness encryption for NP without resorting to iO or MMaps. In particular, we give a witness encryption scheme from Yao's garbled circuit technique and a new type of fully homomorphic encryption (FHE) that we call annihilating. Interestingly, we require a version of the annihilating FHE that is circularly insecure, i.e., allows testing the presence of a key cycle. We prove our witness encryption's security from a novel assumption about our annihilating FHE. We formulate the assumption as an interplay between an annihilating FHE and ideal ciphers. We show a candidate (leveled) annihilating FHE built from a multikey variant of the BGV/BFV fully homomorphic cryptosystems.

We present PANCAKE, the first system to protect key-value stores from access pattern leakage attacks with small constant factor bandwidth overhead. PANCAKE uses a new approach, that we call frequency smoothing, to transform plaintext accesses into uniformly distributed encrypted accesses to an encrypted data store. We show that frequency smoothing prevents access pattern leakage attacks by passive persistent adversaries in a new formal security model. We integrate PANCAKE into three key-value stores used in production clusters, and demonstrate its practicality: on standard benchmarks, PANCAKE achieves 229× better throughput than non-recursive Path ORAM - within 3–6× of insecure baselines for these key-value stores.

MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security in the plain model against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT.

In the common random string model, we achieve a constant-round universally composable (UC) OT protocol.