International Association
for Cryptologic Research

The existence of a provable one-way function is a long-standing open problem. This short note presents an example towards the existence a provable one-way function, example in which both directions are polynomial. Namely, we prove that given a sorted array it takes O(n) operations to randomly permute the array values uniformly over the permutation space, while (comparison based) sorting of the permuted array (of big enough values) requires in the worst case (and in the average case) Omega(n log n) compare operations . We also present a candidate cryptosystem based on permutations of random polynomial values.

Recent research in Dynamic Searchable Symmetric Encryption (DSSE) focuses on efficient search over encrypted data while allowing updates. Unfortunately, as demonstrated by many attacks, updates can be a source of information leakage that can compromise DSSE privacy. To mitigate these attacks, forward and backward privacy of DSSE schemes have been introduced. A concerted effort of the research community has resulted in the publication of many DSSE schemes. To the best of our knowledge, however, there is no DSSE scheme supporting conjunctive queries, which achieves both forward and backward privacy.

We give two DSSE schemes with forward and backward privacy, which support conjunctive queries, and they are suitable for different applications. In particular, we first introduce a new data structure termed the extended bitmap index. Then we describe our forward and backward private DSSE schemes, which support conjunctive queries. Our security analysis proves the claimed privacy characteristics, and experiments show that our schemes are practical. Compared to the state-of-the-art DSSE VBTree supporting conjunctive queries (but not backward privacy), our schemes offer search time that is a few orders of magnitude faster. Besides, our schemes claim better security (called Type-C backward privacy).

In this paper we introduce new algorithms that, based only on the independent round keys assumption, allow to practically compute the exact expected differential probability of (truncated) differentials and the expected linear potential of (multidimensional) linear hulls. That is, we can compute the exact sum of the probability or the potential of all characteristics that follow a given activity pattern. We apply our algorithms to various recent SPN ciphers and discuss the results.

We introduce a novel variant of Lagrange interpolation called modular Lagrange interpolation that allows us to obtain and prove error bounds for explicit low-degree polynomial approximations of a function on a union of equally-spaced small intervals even if the function overall is not continuous. We apply our technique to the mod function and obtain explicit low-degree polynomial approximations with small error. In particular, for every $k$ and $N >>k$, we construct low-degree polynomials that approximate $f(x)\:=\: x$ mod $N$, for $|f(x)| \leq 1$ and $|x| \leq kN$, to within O($1/N$) additive approximation. For $k= O(\log N)$, the result is generalized to give O($d$)-degree polynomial approximations to within O($N^{-d}$) error for any $d \geq 1$. Literature in approximation theory allows for arbitrary precision polynomial approximation of only smooth functions, whereas the mod function is only piecewise linear. These polynomials can be used in bootstrapping for approximate homomorphic encryption, which requires computing the mod function near multiples of the modulus. Our work bypasses the fundamental error of approximation in prior works caused by first approximating the mod function by a scaled sine function. For typical settings of $N$, these polynomials have lower error than the fundamental error introduced by using the scaled sine function at degrees computable in multiplicative depth seven or eight.

We present two new related families of lattice trapdoors based on the inhomogeneous NTRU problem (iNTRU) defined in Genise et. al (ASIACRYPT 2019). Our constructions are ``gadget-based'' and offer compact secret keys and preimages and compatibility with existing, efficient preimage sampling algorithms. Our trapdoors can be used as a fundamental building block in lattice-based schemes relying lattice trapdoors. In addition, we implemented our trapdoors using the PALISADE library.

There are lots of applications of inner-product functional encryption (IPFE). In this paper, we consider two important extensions of it. One is to enhance IPFE with access control such that only users with a pre-defined identity are allowed to compute the inner product, referred as identity-based inner-product functional encryption (IBIPFE). We formalize the definition of IBIPFE, and propose the first adaptive-secure IBIPFE scheme from Decisional Bilinear Diffie-Hellman (DBDH) assumption. In an IBIPFE scheme, the ciphertext is related to a vector $\vec{x}$ and a new parameter, identity ID. Each secret key is also related to a vector $\vec{y}$ and an identity ID'. The decryption algorithm will output the inner-product value $⟨x, y⟩$ only if ID $=$ ID. The other extension is to make IBIPFE leakage resilient. We consider the bounded-retrieval model (BRM) in which an adversary can learn at most $l$ bits information from each secret key. Here, $l$ is the leakage bound determined by some external parameters, and it can be set arbitrarily large. After giving the security definition of leakage-resilient IBIPFE, we extend our IBIPFE scheme into a leakage-resilient IBIPFE scheme in the BRM by hash proof system (HPS).

Byzantine Broadcast is an important topic in distributed systems and improving its round complexity has long been a focused challenge. Under honest majority, the state of the art for Byzantine Broadcast is 10 rounds for a static adversary and 16 rounds for an adaptive adversary. In this paper, we present a Byzantine Broadcast protocol with expected 8 rounds under a static adversary and expected 10 rounds under an adaptive adversary. We also generalize our idea to the dishonest majority setting and achieve an improvement over existing protocols.

Most efficient zero-knowledge arguments lack a concrete security analysis, making parameter choices and efficiency comparisons challenging. This is even more true for non-interactive versions of these systems obtained via the Fiat-Shamir transform, for which the security guarantees generically derived from the interactive protocol are often too weak, even when assuming a random oracle.

This paper initiates the study of {\em state-restoration soundness} in the algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO '18). This is a stronger notion of soundness for an interactive proof or argument which allows the prover to rewind the verifier, and which is tightly connected with the concrete soundness of the non-interactive argument obtained via the Fiat-Shamir transform.

We propose a general methodology to prove tight bounds on state-restoration soundness, and apply it to variants of Bulletproofs (Bootle et al, S\&P '18) and Sonic (Maller et al., CCS '19). To the best of our knowledge, our analysis of Bulletproofs gives the {\em first} non-trivial concrete security analysis for a non-constant round argument combined with the Fiat-Shamir transform.

Many organizations stand to benefit from pooling their data together in order to draw mutually beneficial insights -- e.g., for fraud detection across banks, better medical studies across hospitals, etc. However, such organizations are often prevented from sharing their data with each other by privacy concerns, regulatory hurdles, or business competition.

We present Senate, a system that allows multiple parties to collaboratively run analytical SQL queries without revealing their individual data to each other. Unlike prior works on secure multi-party computation (MPC) that assume that all parties are semi-honest, Senate protects the data even in the presence of malicious adversaries. At the heart of Senate lies a new MPC decomposition protocol that decomposes the cryptographic MPC computation into smaller units, some of which can be executed by subsets of parties and in parallel, while preserving its security guarantees. Senate then provides a new query planning algorithm that decomposes and plans the cryptographic computation effectively, achieving a performance of up to 145$\times$ faster than the state-of-the-art.

In this paper, we investigate the key dependency of differentials in block ciphers by examining the results of numerous experiments applied to the substitution-permutation network (SPN) structure using 4-bit S-boxes. In particular, we consider two cipher structures: a toy 16-bit SPN and a realistic 64-bit SPN. For both ciphers, we generate many different experimental results by inserting the S-boxes used in many lightweight cipher proposals and applying different forms of round key generation. It is demonstrated that, in most circumstances, with enough rounds in the cipher, the probability distribution (across all keys) of the differential probability follows the distribution expected in the theoretically ideal scenario. However, this does not occur consistently for all S-boxes and all approaches to round key generation. Consequently, it is possible that a cipher may have more susceptibility to differential cryptanalysis for some subset of the cipher keys than is implied when employing the standard assumptions used in analyzing a cipher’s security.

We introduce Vetted Encryption (VE), a novel cryptographic primitive, which addresses the following scenario: a receiver controls, or vets, who can send them encrypted messages. We model this as a filter publicly checking ciphertext validity, where the overhead does not grow with the number of senders. The filter receives one public key for verification, and every user receives one personal encryption key.

We present three versions: Anonymous, Identifiable, and Opaque VE (AVE, IVE and OVE), and concentrate on formal definitions, security notions and examples of instantiations based on preexisting primitives of the latter two. For IVE, the sender is identifiable both to the filter and the receiver, and we make the comparison with identity-based signcryption. For OVE, a sender is anonymous to the filter, but is identified to the receiver. OVE is comparable to group signatures with message recovery, with the important additional property of confidentiality of messages.

In this paper we examine the central question that is how well do side channel evaluation regimes capture the true security level of a product. Concretely, answering this question requires considering the optimality of the attack/evaluation strategy selected by the evaluator, and the various steps to instantiate it. We draw on a number of published works and discuss whether state-of-the-art solutions for the different steps of a side-channel security evaluation offer bounds or guarantees of optimality, or if they are inherently heuristic. We use this discussion to provide an informal rating of the steps' optimality and to put forward where risks of overstated security levels remain.

SodsMPC is a quantum-safe smart contract system. SodsMPC permissioned servers (verification nodes) execute contracts by secure multi-party computation (MPC) protocols. MPC ensures the contract execution correctness while trivially keeping the \textit{data privacy}. Moreover, SodsMPC accomplishes the contract \textit{business logic privacy} while protecting the contract user \textit{anonymous identity} simultaneously. We express the logic of a contract by a finite state machine (FSM). A state transition of the FSM is represented by a \textit{blind polynomial} with secret-shared coefficients. When using MPC to compute this blind polynomial, the contract business logic privacy is obtained. These coefficients which control the logic are binary secret shares. We also propose a base conversion method among binary and integer secret shares by MPC. Our contract anonymity comes from the ``mixing-then-contract'' paradigm. The online phase of the SodsMPC mixing is a multiplication between a preprocessed permutation matrix and an input vector in the form of secret sharing, which accomplishes a fully randomized shuffle of the inputs and keeps the secret share form for the following contract execution. All SodsMPC components, including a verifiable secret sharing scheme, are quantum-safe, asynchronous, coping with $t<n/3$ compromised servers, and robust (tolerates Byzantine servers) in both preprocessing and online phases.

Adaptor signatures (AS) are an extension of digital signatures that enable the encoding of a cryptographic hard problem (e.g., discrete logarithm) within the signature itself. An AS scheme ensures that (i) the signature can be created only by the user knowing the solution to the cryptographic problem; (ii) the signature reveals the solution itself; (iii) the signature can be verified with the standard verification algorithm. These properties have made AS a salient building block for many blockchain applications, in particular, off-chain payment systems such as payment-channel networks, payment-channel hubs, atomic swaps or discrete log contracts. Current AS constructions, however, are not secure against adversaries with access to a quantum computer.

In this work, we present IAS, a construction for adaptor signatures that relies on standard cryptographic assumptions for isogenies, and builds upon the isogeny-based signature scheme CSI-FiSh. We formally prove the security of IAS against a quantum adversary. We have implemented IAS and our evaluation shows that IAS can be incorporated into current blockchains while requiring $\sim1500$ bytes of storage size on-chain and $\sim140$ milliseconds for digital signature verification. We also show how IAS can be seamlessly leveraged to build post-quantum off-chain payment applications such as payment-channel networks without harming their security and privacy.

This is an exciting opportunity to join the University of Birmingham’s Centre for Cyber Security and Privacy on an exciting EPSRC funded project ‘CAP-TEE: Capability Architectures in Trusted Execution’. Trusted Execution Environments (TEEs) shield computations using security-sensitive data (e.g. personal data, banking information, or encryption keys) inside a secure "enclave" from the rest of the untrusted operating system. A TEE protects its data and code even if an attacker has gained full root access to the untrusted parts of the system. Today, TEEs like ARM Trustzone and Intel SGX are therefore widely used in general-purposes devices, including most laptops and smartphones. But with increasingly widespread use, TEEs have proven vulnerable to a number of hardware and software-based attacks, often leading to the complete compromise of the protected data. In this project, we will use capability architectures (as e.g. developed by the CHERI project) to protect TEEs against such state-of-the-art attacks. We address a wide range of threats from software vulnerabilities such as buffer overflows to sophisticated hardware attacks like fault injection. CAP-TEE will provide a strong, open-source basis for the future generation of more secure TEEs. When developing such disruptive technologies, it is key to minimise the efforts for porting existing codebases to the new system to facilitate adoption in practice. In CAP-TEE, we therefore focus on techniques to ease the transition to our capability-enabled TEE. In industrial cases studies for the automotive and rail sector, we will demonstrate how complex code written in a memory-unsafe language like C(++) can be seamlessly moved to our platform to benefit from increased security without a full redesign. The successful candidate will be based at the School of Computer Science as part of the Centre for Cyber Security and Privacy and will be working closely with Dr David Oswald. The centre is recognised by NCSC and EPSRC as an Academic Centre of Excellence in Cyber Security Research. 

Closing date for applications:

Contact: Dr David Oswald

More information: https://www.jobs.ac.uk/job/CCF964/research-felllow-in-cyber-security

CISPA is looking for candidates that hold a doctoral degree in computer science or related areas and have an outstanding research track record in all areas related to efficient algorithms and the foundations of theoretical computer science, including theory of cryptography, differential privacy, algorithmic fairness, computational complexity, data structures and the design of efficient algorithms.

CISPA offers two main types of faculty positions.

Tenure track: these positions are intended for candidates with excellent research credentials and the potential to pursue a program of innovative research. The positions are comparable to tenure-track positions at a leading university, and come with two full time research staff positions and generous support for other expenses.

Tenured: these positions are intended for established leading researchers with an outstanding scientific track record, and can be compared to an endowed chair at a leading university. All applicants are expected to build up a research team that pursues an internationally visible research agenda. Candidates for senior positions must be internationally renowned scientists.

All applicants are strongly encouraged to submit their complete application by November 30, 2020 for full consideration. However, applications will continue to be accepted until December 10, 2020.

CISPA values diversity and is committed to equality. We provide special support for dual-career couples. We highly encourage female researchers to apply. For more information about CISPA, see https://cispa.saarland

Closing date for applications:

Contact: scientific-recruiting@cispa.saarland

More information: https://jobs.cispa.saarland/jobs/department/faculty-14

CISPA is looking for candidates that hold a doctoral degree in computer science or related areas and have an outstanding research track record in all areas related to information security and privacy , especially in the fields of software security, security of critical infrastructure and embedded systems.

CISPA offers two main types of faculty positions.

Tenure track: these positions are intended for candidates with excellent research credentials and the potential to pursue a program of innovative research. The positions are comparable to tenure-track positions at a leading university, and come with two full time research staff positions and generous support for other expenses.

Tenured: these positions are intended for established leading researchers with an outstanding scientific track record, and can be compared to an endowed chair at a leading university. All applicants are expected to build up a research team that pursues an internationally visible research agenda. Candidates for senior positions must be internationally renowned scientists.

All applicants are strongly encouraged to submit their complete application by November 30, 2020 for full consideration. However, applications will continue to be accepted until December 10, 2020.

CISPA values diversity and is committed to equality. We provide special support for dual-career couples. We highly encourage female researchers to apply. For more information about CISPA, see https://cispa.saarland

Closing date for applications:

Contact: scientific-recruiting@cispa.saarland

More information: https://jobs.cispa.saarland/de_DE/jobs/department/faculty-14

Prof. Fan Zhang at the Dept. of Computer Science at Duke University, Durham, NC is looking for multiple PhD students to work on related topics in security, privacy, and applied cryptography, including:

• Blockchain and smart contract security
• Trusted hardware security
• Scalable and fair consensus protocols
• Privacy enhancing technology (e.g., anonymous communication)

The positions start in 2021 Fall. Visit http://fanzhang.me to learn more about Prof. Zhang and his research.

Closing date for applications:

Contact: Fan Zhang

More information: https://www.fanzhang.me/opening/ads.html

Symmetric Key and Lightweight Cryptography Lab (SyLLab) at Nanyang Technological University (Singapore) is looking for candidates for 2 Research Fellow / Post-Doc positions (from fresh Post-Docs to Senior Research Fellow, flexible contract duration) on various topics, such as symmetric-key design/cryptanalysis, lightweight cryptography, cryptography for automotive industry, side-channel analysis, machine learning aided cryptanalysis. Candidates are expected to have a proven record of publications in top cryptography/security venues. Salaries are competitive and are determined according to the successful applicants' accomplishments, experience and qualifications. Interested applicants should send their detailed CVs, cover letter and references to Prof. Thomas Peyrin (thomas.peyrin@ntu.edu.sg). Review of applications starts immediately and will continue until positions are filled.

Closing date for applications:

Contact: Thomas Peyrin: thomas.peyrin@ntu.edu.sg

Our Computational Privacy Group at Imperial College London is offering fully funded PhD positions for 2021 to study privacy, data protection, and the impact of algorithms on society.

Topics of current interests include, for instance, individual privacy in large-scale behavioral datasets; re-identification attacks against privacy-preserving data systems or aggregates, privacy of machine learning models, privacy engineering solutions such as differential privacy and query-based systems, ethics and fairness in AI, and computational social science.

For full details, please consult https://cpg.doc.ic.ac.uk/openings/

Deadline: Nov 1th 2020 (first deadline)

Recommended prerequisites. MSc or MEng (4y BEng will be considered) in computer science, statistics, mathematics, physics, electrical engineering, or a related field. Experience in data science, statistics and/or machine learning is a plus.

We encourage all qualified candidates to apply, in particular women, disabled, BAME, and LGBTQIA+ candidates.

About Imperial. Imperial College London, ranked 9th globally, is one of the top universities in the world. A full-time PhD at the South Kensington Campus takes 3-4 years, is fully funded and usually starts in October or January.

Closing date for applications:

Contact:
demontjoye@imperial.ac.uk
- Using as subject: “PhD Application 2020: YOUR NAME”
- Including a link (e.g. Imperial’s Filedrop system or Dropbox) to your CV and transcripts for each degree

More information: https://cpg.doc.ic.ac.uk/openings/