International Association
for Cryptologic Research

Using recent results on solving the equation $X^{2^k+1}+X+a=0$ over a finite field $\GF{2^n}$, we address an open question raised by the first author in WAIFI 2014 concerning the APN-ness of the Kasami functions $x\mapsto x^{2^{2k}-2^k+1}$ with $gcd(k,n)=1$, $x\in\GF{2^n}$

Event date: 24 May to 26 May 2020

Event date: 2 September to 4 September 2020
Submission deadline: 23 March 2020
Notification: 22 May 2020

Hybrid Authenticated Key Exchange (AKE) protocols combine keying material from different sources (post-quantum, classical, and quantum key distribution (QKD)) to build protocols that are resilient to catastrophic failures of the different components. These failures may be due to advances in quantum computing, implementation vulnerabilities, or our evolving understanding of the quantum (and even classical) security of supposedly quantum-secure primitives. This hybrid approach is a prime candidate for initial deployment of post-quantum-secure cryptographic primitives because it hedges against undiscovered weaknesses. We propose a general framework HAKE for analysing the security of such hybrid AKE protocols. HAKE extends the classical Bellare-Rogaway model for AKE security to encompass forward security, post-compromise security, fine-grained compromise of different cryptographic components, and more. We use the framework to provide a security analysis of a new hybrid AKE protocol named Muckle. This protocol operates in one round trip and leverages the pre-established symmetric keys that are inherent to current QKD designs to provide message authentication, avoiding the need to use expensive post-quantum signature schemes. We provide an implementation of our Muckle protocol, instantiating our generic construction with classical and post-quantum Diffie-Hellman-based algorithmic choices. Finally, we report on benchmarking exercises against our implementation, examining its performance in terms of clock cycles, elapsed wall-time, and additional latency in both LAN and WAN settings.

We give an algorithm for key recovery of the Legendre pseudorandom function that supersedes the best known algorithms so far. The expected number of operations is $O(\sqrt{p\log{\log{p}}})$ on a $\Theta(\log{p})$-bit word machine, under reasonable heuristic assumptions, and requires only $\sqrt[4]{p~{\log^2{p}}\log{\log{p}}}$ oracle queries. If the number of queries $M$ is smaller, the expected number of operations is $\frac{{p}\log{p}\log\log{p}}{M^2}$. We further show that the algorithm works in many different generalisations -- using a different character instead of the Legendre symbol, using the Jacobi symbol, or using a degree $r$ polynomial in the Legendre symbol numerator. In the latter case we show how to use Möbius transforms to lower the complexity to $O(p^{\operatorname{max}\{r-3,r/2\}}r^2\log{p})$ Legendre symbol computations, and $O(p^{\operatorname{max}\{r-4,r/2\}}r^2\log{p})$ in the case of a reducible polynomial. We also give an $O(\sqrt[3]{p})$ quantum algorithm that does not require a quantum oracle, and comments on the action of the Möbius group in the linear PRF case. On the practical side we give implementational details of our algorithm. We give the solutions of the $64, 74$ and $84$-bit prime challenges for key recovery with $M=2^{20}$ queries posed by Ethereum, out of which only the $64$ and $74$-bit were solved earlier.

The survey deals with elliptic curves which are implemented in the OpenSSL 1.1.1d software library. The objective of this work is to highlight the elliptic curves which comply with the Russian national digital signature standard, namely the GOST R 34.10--2012. For this reason the paper focuses on the OpenSSL elliptic curves over a finite field of a prime order and provides the results of testing those curves for compliance with the GOST R 34.10--2012 requirements. Two cases are observed. The first case covers a complete set of restrictions imposed on elliptic curves parameters, whereas the second one differs in that a restriction on a bit length of a number of points on the curve is omitted. For both cases the paper presents tables which list the curves tested along with corresponding match marks. In order to conduct tests the Wolfram Mathematica computing system was employed, and the Wolfram language source code is given in the appendices. Note, that the paper does not address to a rationale of the requirements of the standard nor does it focus on the parameters generation issues.

We provide the first systematic analysis of (Non-Interactive) Fully Distributed Verifiable Random Functions (DVRFs), including their syntax, definition of integrity and privacy properties, and describe and analyse three concrete constructions, two of which are original. Building on recent work (Agrawal, Mohassel, Mukherjee, Rindal: CCS 2018), we strengthen the standard pseudorandomness property by allowing an adversary to make partial queries on the challenge value, and call the resulting property strong pseudorandomness. We show how a prominent DVRF construction in the blockchain space meets standard pseudorandomness, and provide two other instantiations that meet strong pseudorandomness, under widely accepted cryptographic assumptions. We review how to generically build a Decentralized Random Beacon (DRB) from any DVRF instance. DRBs have recently gained a lot traction as a key component for leader(s) election in decentralized ledger technologies. We provide implementations and experimental evaluations of three concrete DVRFs, using different cryptographic libraries. Our two new DRB instantiations are strongly pseudorandom and strongly unbiasable, while exhibiting high performance and linear communication complexity (as they are in essence non-interactive). We provide a C++ reference implementation that is available in open source form.

We propose a new family of public key encryption (PKE) and key encapsulation mechanism (KEM) schemes based on the plain learning with errors (LWE) problem. Two new design techniques are adopted in the proposed scheme named SCloud: the sampling method and the error-reconciliation mechanism. The new sampling method is obtained by studying the property of the convolution of central binomial distribution and bounded uniform distribution which can achieve higher efficiency and more flexibility w.r.t the parameter choice. Besides, it is shown to be more secure against the dual attack due to its advantage in distinguish property. The new error-reconciliation mechanism is constructed by combining the binary linear codes and Gray codes. It can reduce the size of parameters, and then improve the encryption/decryption efficiency as well as communication efficiency, by making full use of the encryption space. Based on these two techniques, SCloud can provide various sets of parameters for refined security level.

The selfish mining attack allows cryptocurrency miners to mine more than their "fair share" of blocks, stealing revenue from other miners while reducing the overall security of payments. This malicious strategy has been extensively studied in Bitcoin, but far less attention has been paid to how the strategy may impact other cryptocurrencies. Because selfish mining is an attack against the difficulty adjustment algorithm (DAA) of a cryptocurrency, it may have a different effect when used on coins with different DAAs. In this work, we study the degree to which selfish mining can increase the revenue of miners for a wider variety of cryptocurrencies than have been studied before, including Bitcoin, Litecoin, Bitcoin Cash, Dash, Monero, and Zcash. To do so, we generalize the selfish mining strategy to blockchains with variable difficulty, and use simulations to measure how profitable the strategy is. We find that the other cryptocurrencies under consideration are far more susceptible to selfish mining than Bitcoin is, and that the strategy is profitable for miners with a lower hash rate. We also show that by dishonestly reporting block timestamps, selfish miners can generate enormously disproportionate revenues up to 2.5 times larger than they would through honest mining for some DAAs. For each DAA, we consider what happens when parameters are changed, and suggest parameter sets that would improve the algorithm’s resilience against selfish mining.

We give the first public-key functional encryption that supports the generation of functional decryption keys for degree-2 polynomials, with succinct ciphertexts, whose semi-adaptive simulation-based security is proven under standard assumptions. At the heart of our new paradigm lies a so-called partially function-hiding functional encryption scheme for inner products, which admits public-key instances, and that is sufficient to build functional encryption for degree-2 polynomials. Doing so, we improve upon prior works, such as the constructions from Lin (CRYPTO 17) or Ananth Sahai (EUROCRYPT 17), both of which rely on function-hiding inner product FE, that can only exist in the private-key setting. The simplicity of our construction yields the most efficient FE for quadratic functions from standard assumptions (even those satisfying a weaker security notion). The interest of our methodology is that the FE for quadratic functions that builds upon any partially function-hiding FE for inner products inherits the security properties of the latter. In particular, we build a partially function-hiding FE for inner products that enjoys simulation security, in the semi-adaptive setting, where the challenge sent from the adversary can be chosen adaptively after seeing the public key (but before corrupting functional decryption keys). This is in contrast from prior public-key FE for quadratic functions from Baltico et al. (CRYPTO 17), which only achieved an indistinguishability-based, selective security. As a bonus, we show that we can obtain security against Chosen-Ciphertext Attacks straightforwardly. Even though this is the de facto security notion for encryption, this was not achieved by prior functional encryption schemes for quadratic functions, where the generic Fujisaki Otamoto transformation (CRYPTO 99) does not apply.

Composable security definitions, sometimes called simulation-based definitions, provide very strong security guarantees. In particular, they assure that the guarantees hold in any context. However, they are also met with some skepticism because of many impossibility results; goals such as commitments and zero-knowledge that are achievable in a stand-alone sense were shown to be unachievable composably (without a setup) since provably no efficient simulator exists. In particular, in the context of adaptive security, the so-called simulator commitment problem arises: once a party gets corrupted, an efficient simulator is unable to be consistent with its pre-corruption outputs. A natural question is whether such impossibility results are unavoidable or only artifacts of frameworks being too restrictive.

In this work, we propose a new type of composable security statement that evades the commitment problem by a specific instantiation of the concept of system specifications in the Constructive Cryptography (CC) framework, capturing the intersection of several interval-wise guarantees, each specifying the guarantees between two events. We develop the required theory within the CC framework and present the corresponding new composition theorem.

We present three applications of our notion. First, we show in the context of symmetric encryption with adaptive corruption how our notion naturally captures the expected confidentiality guarantee---the messages remain confidential until either party gets corrupted---and that it can be achieved by any standard semantically secure scheme (negating the need for non-committing encryption). Second, we present a composable formalization of commitments that is instantiable without a trusted setup like a CRS, and show its application to coin tossing over the telephone, one of the early intuitive applications of commitments. Third, we reexamine a result by Hofheinz, Matt, and Maurer [Asiacrypt'15] implying that IND-ID-CPA security is not the right notion for identity-based encryption, unmasking this claim as an unnecessary framework artifact.

Though Fully Homomorphic Encryption (FHE) has been realized, most practical implementations utilize leveled Somewhat Homomorphic Encryption (SHE) schemes, which have limits on the multiplicative depth of the circuits they can evaluate and avoid computationally intensive bootstrapping. Many SHE schemes exist, among which those based on Ring Learning With Error (RLWE) with operations on large polynomial rings are popular. Of these, variants allowing operations to occur fully in Residue Number Systems (RNS) have been constructed. This optimization allows homomorphic operations directly on RNS components without needing to reconstruct numbers from their RNS representation, making SHE implementations faster and highly parallel. In this paper, we present a set of optimizations to a popular RNS variant of the B/FV encryption scheme that allow for the use of significantly larger ciphertext moduli (e.g., thousands of bits) without increased overhead due to excessive numbers of RNS components or computational overhead, as well as computational optimizations. This allows for the use of larger ciphertext moduli, which leads to a higher multiplicative depth with the same computational overhead. Our experiments show that our optimizations yield runtime improvements of up to 4.48 for decryption and 14.68 for homomorphic multiplication for large ciphertext moduli.

We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an $\mathbf{NP}$ statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a ``lossy'' deterministic-prover, non-interactive proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an ``extractable'' mode to a CWM.

\medskip

Our main construction is a DMWM for all $\mathbf{NP}$ relations, assuming sub-exponentially secure indistinguishability obfuscation ($i\mathcal{O}$), along with standard cryptographic assumptions. The DMWM construction relies on a CWM and a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF), both of which are in turn instantiated based on $i\mathcal{O}$ and other primitives. Our instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct, from standard assumptions, Puncturable Digital Signatures and a new primitive called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure $i\mathcal{O}$ and sub-exponentially secure OWF.

\medskip

As an application of our constructions, we show how to use a DMWM to construct the first leakage and tamper-resilient signatures with a deterministic signer, thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of $1 - o(1)$.

Conditional differential attacks were proposed by Knellwolf et al. at ASIACRYPT 2010 which targeted at cryptographic primitives based on non-linear feedback shift registers. The main idea of conditional differential attacks lies in controlling the propagation of a difference through imposing some conditions on public/key variables. In this paper, we improve the conditional differential attack by introducing the mixed integer linear programming (MILP) method to it. Let $J=\{f_i(\boldsymbol{x},\boldsymbol{v})=\gamma_i| 1\le i\le N\}$ be a set of conditions that we want to impose, where $\boldsymbol{x}=(x_1,x_2,\ldots,x_n)$ (resp. $ \boldsymbol{v}=(v_1,v_2,\ldots,v_n)$) represents key (resp. public) variables and $\gamma_i \in\{0,1\}$ needs evaluating. Previous automatic conditional differential attacks evaluate $\gamma_1,\gamma_2,\ldots,\gamma_N$ just in order with the preference to zero. Based on the MILP method, conditions in $J$ could be automatically analysed together. In particular, to enhance the effect of conditional differential attacks, in our MILP models, we are concerned with minimizing the number of 1's in $\{\gamma_1,\gamma_2,\ldots,\gamma_N\}$ and maximizing the number of weak keys.

~~~We apply our method to analyse the security of Trivium. As a result, key-recovery attacks are preformed up to the 978-round Trivium and non-randomness is detected up to the 1108-round Trivium of its 1152 rounds both in the weak-key setting. All the results are the best known so far considering the number of rounds and could be experimentally verified. Hopefully, the new method would provide insights on conditional differential attacks and the security evaluation of Trivium.

In the past five years or so, numerous blockchain projects have made tremendous progress towards improving permissioned consensus protocols (partly due to their promised applications in Proof-of-Stake cryptocurrencies). Although a significant leap has silently taken place in our understanding of consensus protocols, it is rather difficult to navigate this body of work, and knowledge of the new techniques appears scattered. In this paper, we describe an extremely simple and natural paradigm for constructing con- sensus protocols called Streamlet. Our protocols are inspired by the core techniques that have been uncovered in the past five years of work; but to the best of our knowledge our embodiment is simpler than ever before and we accomplish this by taking a “streamlining” idea to its full potential. We hope that our textbook constructions will help to decipher the past five year’s of work on consensus partly driven by the cryptocurrency community — in particular, how remarkably simple the new generation of consensus protocols have become in comparison with classical schemes such as PBFT and Paxos.

A blockchain protocol (also called state machine replication) allows a set of nodes to agree on an ever-growing, linearly ordered log of transactions. The classical consensus literature suggests two approaches for constructing a blockchain protocol: 1) through composition of single-shot consensus instances often called Byzantine Agreement; and 2) through direct construction of a blockchain where there is no clear-cut boundary between single-shot consensus instances. While conceptually simple, the former approach precludes cross-instance optimizations in a practical implementation. This perhaps explains why the latter approach has gained more traction in practice: specifically, well-known protocols such as Paxos and PBFT all follow the direct-construction approach. In this tutorial, we present a new paradigm called “streamlined blockchains” for directly constructing blockchain protocols. This paradigm enables a new family of protocols that are extremely simple and natural: every epoch, a proposer proposes a block extending from a notarized parent chain, and nodes vote if the proposal’s parent chain is not too old. Whenever a block gains enough votes, it becomes notarized. Whenever a node observes a notarized chain with several blocks of consecutive epochs at the end, then the entire chain chopping off a few blocks at the end is final. By varying the parameters highlighted in blue, we illustrate two variants for the partially synchronous and synchronous settings respectively. We present very simple proofs of consistency and liveness. We hope that this tutorial provides a compelling argument why this new family of protocols should be used in lieu of classical candidates (e.g., PBFT, Paxos, and their variants), both in practical implementation and for pedagogical purposes.

FHEW and TFHE are fully homomorphic encryption (FHE) cryptosystems that can evaluate arbitrary Boolean circuits by bootstrapping after each gate evaluation. The FHEW cryptosystem was originally designed based on standard (Ring) LWE assumptions, and its initial implementation was able to run bootstrapping in less than 1 second. The TFHE cryptosystem used somewhat stronger assumptions, such as LWE over torus and binary secret distribution, and applied several other optimizations to reduce the bootstrapping runtime to less than 0.1 second. Up to now, the gap between the underlying security assumptions prevented a fair comparison of the cryptosystems for same security settings.

We present a unified framework that includes the original and extended variants of both FHEW and TFHE cryptosystems, and implement it in PALISADE using modular arithmetic. Our analysis shows that the main distinction between the cryptosystems is the bootstrapping procedure used: Alperin-Sherif--Peikert (AP) for FHEW vs. Gama--Izabachene--Nguyen--Xie (GINX) for TFHE. All other algorithmic optimizations in TFHE equally apply to both cryptosystems. We extend the GINX bootstrapping to ternary uniform and Gaussian secret distributions, which are included in the HE community security standard. Our comparison of the AP and GINX bootstrapping methods for different secret distributions suggests that the TFHE/GINX cryptosystem provides better performance for binary and ternary secrets while FHEW/AP is faster for Gaussian secrets. We make a recommendation to consider the variants of FHEW and TFHE cryptosystems based on ternary and Gaussian secrets for standardization by the HE community.

The ST Engineering-SUTD Cyber Security Laboratory @ SUTD looks for one Postdoctoral Fellow position and one Research Assistant position, for a project on the security of avionics systems with emphases on the aircraft data bus and network technologies.

 

Post-Doc

Requirements:

• Ph.D. in Computer Science or related areas;
• Background in Security, Software Engineering, and/or Data Science;
• Track record of publications in high-quality journals and/or conferences;
• Good written/oral communication skills in English, and ability to work effectively in a collaborative team;
• Skills and experience in both analytical and empirical research;
• Programming skills in one or more of the following: Python, Java, C++;
• Interest to work in:
  1. Avionics data bus and network technologies
  2. Computer and network security
  3. Attack emulation
  4. Machine learning with application to intrusion detection

 

Research Assistant

Requirements:

• Master degree in Computer Science or related areas;
• Strong programming skills in one or more of the following: Python, Java, C++;
• Familiarity with (i) applied software and/or systems security, and (ii) machine learning;
• Good written/oral communication skills in English, and ability to work effectively in a collaborative team;
• Interest to work in:
  1. Avionics data bus and network technologies
  2. Computer and network security
  3. Attack emulation
  4. Machine learning with application to intrusion detection

 

A full-time appointment will be offered for one year renewable. SUTD offers an internationally competitive salary that will be determined based on the applicant's experience and qualifications.

Closing date for applications:

Contact: Interested persons please email with a cover letter and updated curriculum vitae to cyberlab@sutd.edu.sg . Positions will be available until filled; only short-listed candidates will be notified.

About

Our mission at Zama is to protect people’s privacy by preventing data breaches and surveillance.

Our first product is a deep learning framework that enables fast and accurate inference over encrypted data, without any changes to the neural network architecture.

We believe privacy-enabling technologies should benefit the widest possible community of developers and security researchers, which is why everything we create will be published and open-sourced.

Zama is founded by Pascal Paillier and Rand Hindi

Responsibilities

discovering new cryptographic techniques to compute on encrypted data

working with the engineering and product teams to implement your research into our products

design robust benchmarks to test your research and its implementation

review the latest published research, and inform the team on potential new applications or changes to our approach

work with the entire team to define the research and product roadmaps

publishing papers, filing patents and presenting your work at academic conferences

Requirements

PhD in cryptography or equivalent

deep knowledge of homomorphic encryption

optionally knowledge of machine learning

be based in or willing to relocate to Paris, France

passionate about privacy and open science

Closing date for applications:

Contact: hello@zama.ai

More information: https://zama.ai/jobs/senior-researcher-cryptography/

We are hiring one more junior postdoc, for two years, to work on blue-sky research, real world crypto, cryptanalysis, side channels, or interdisciplinary studies of crypto-system failures. Positions available immediately with internationally competitive salaries and first-rate research support, but start dates are negotiable.

Our track records include award-winning papers at Usenix Security, ACM CCS, ACSAC and SOUPS; making a finalist for the Pwnie Award for most innovative research; and trailblazing a number of subjects such as usable security and differential imaging forensics.

Our research philosophy: have fun; write papers that matter; and make an impact.

Closing date for applications:

Contact: Prof Jeff.Yan@liu.se