International Association
for Cryptologic Research

We initiate the study of indifferentiability for public key encryption and other public key primitives. Our main results are definitions and constructions of public key cryptosystems that are indifferentiable from ideal cryptosystems, in the random oracle model. Cryptosystems include Public key encryption, Digital signatures, Non-interactive key agreement. Our schemes are based on standard public key assumptions. By being indifferentiable from an ideal object, our schemes satisfy any security property that can be represented as a single-stage game and can be composed to operate in higher-level protocols.

Recently Budaghyan, Calderini and Villa (2018) introduced a procedure for investigating if CCZ-equivalence can be more general than EA-equivalence together with inverse transformation (when applicable). In this paper, we show of it is possible to use this procedure for classifying, up to EA-equivalence, all known APN functions in dimension 6. We also give some discussion for dimension 7, 8 and 9. In particular, in these cases it is possible to give an upper bound on the EA-classes contained in the CCZ-classes of the known APN functions.

Proxy Re-Encryption (PRE), introduced by Bellare et. al, allows a ciphertext encrypted using a key pki to be re-encrypted by a third party so that it is an encryption of the same message under a new key pkj , without revealing the message. Post-Compromise Security (PCS) was first introduced for messaging protocols, and ensures that a ciphertext remains confidential even when past keys have been corrupted. We define PCS in the context of PRE, which ensures that an adversary cannot distinguish which ciphertext a re-encryption was created from even given the old secret key, potential old ciphertexts and update token used to perform the re-encryption. We argue that this formal notion accurately captures the most intuitive form of PCS. We give separating examples demonstrating how our definition is stronger than existing ones, before showing that PCS can be met using a combination of existing security definitions from the literature. In doing so, we show that there are existing PRE schemes that satisfy PCS. We also show that natural modifications of more practical PRE schemes can be shown to be PCS without relying on this combination of existing security definitions. Finally, we discuss the relationship between PCS with selective versus adaptive key corruptions, giving a theorem that shows how adaptive security can be met for certain re-encryption graphs.

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the "Authenticated Key Exchange" (AKE) model (as done by previous work), but also in the "Authenticated and Confidential Channel Establishment" (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

Cryptographic libraries often feature multiple implementations of primitives to meet both the security needs of handling private information and the performance requirements of modern services when the handled information is public. OpenSSL, the de-facto standard free and open source cryptographic library, includes mechanisms to differentiate the confidential data and its control flow, including runtime flags, designed for hardening against timing side-channels, but repeatedly accidentally mishandled in the past. To analyze and prevent these accidents, we introduce Triggerflow, a tool for tracking execution paths that, assisted by source annotations, dynamically analyzes the binary through the debugger. We validate this approach with case studies demonstrating how adopting our method in the development pipeline would have promptly detected such accidents. We further show-case the value of the tooling by presenting two novel discoveries facilitated by Triggerflow: one leak and one defect.

Attribute-based Encryption (ABE), first introduced by [SW05,GPSW06], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).

In this work we construct for the first time a lattice-based (ciphertext-policy) ABE scheme for the function class $t$-CNF, which consists of CNF formulas where each clause depends on at most $t$ bits of the input, for any constant $t$. This class includes NP-verification policies, bit-fixing policies and $t$-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest.

For $1\leq m \leq n$, we consider a natural $m$-out-of-$n$ multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given $n$ independent instances of PKE, wins if he breaks at least $m$ out of the $n$ instances. In this work, we are interested in the scaling factor of PKE schemes, $\mathrm{SF}$, which measures how well the difficulty of breaking $m$ out of the $n$ instances scales in $m$. That is, a scaling factor $\mathrm{SF}=\ell$ indicates that breaking $m$ out of $n$ instances is at least $\ell$ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).

For Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor $\mathrm{SF}=m$; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor $\mathrm{SF}=\sqrt{m}$. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.

As our main technical contribution, we derive new generic-group lower bounds of $\Omega(\sqrt{m p})$ on the difficulty of solving both the $m$-out-of-$n$ Gap Discrete Logarithm and the $m$-out-of-$n$ Gap Computational Diffie-Hellman problem over groups of prime order $p$, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem.

This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP’s, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP’s, which themselves are of unbounded size and input length.

Blockchain technology has immense potential. At the same time, it is not always possible to scale blockchains. State Channels solve the problem of scalability while increasing the blockchain's speed and efficiency. State Channels present a workaround to current blockchains' TPS (transaction per second) bottleneck. We used State Channels as a foundation and created Game Channels. We built it around the needs of the gambling market. We also developed Signidice PRNG as well as a dispute resolution mechanism. Signidice uses unique digital signatures and is also described below. The potential use of Game Channels technology is not only gambling; some types of online gaming may also be able to use it.

Nearly all secret sharing schemes studied so far are linear or multi-linear schemes. Although these schemes allow to implement any monotone access structure, the share complexity may be suboptimal -- the gap between the best known lower bounds and best known upper bounds is exponential for some access structures. There is growing evidence in the literature, that non-linear schemes can improve share complexity for some access structures - with the work of Beimel and Ishai (CCC 01') being among the first to demonstrate it. This motivates further study of non linear schemes.

We initiate a systematic study of polynomial secret sharing schemes, where shares are (multi-variate polynomials) of secret and randomness vectors over some finite field. Our main hope is that the nice algebraic structure of polynomials would help obtain better lower bounds than those known for the general setting, extending over the class of multi-linear schemes.

Some of the concrete new results we prove in this work are as follows.\\ \textbf{On share complexity of polynomial schemes.}\\ First we studied degree 1 in randomness (where the degree of secret is unlimited). We have shown that a large subclass of these schemes are equivalent to multi-linear schemes, in the sense that for any such scheme, there exists an equivalent multi-linear scheme with very similar share complexity. Also, we have shown that the class of schemes of polynomials of degree exactly 2 in r, without degree 1 in r monomials, is very weak, and can implement only trivial access structures where the minterms consist of single parties.\\ Another observation we make refers to the share complexity (per bit) of multi linear schemes (polynomial schemes of total degree 1). We observe that the scheme by Liu et. al obtaining share complexity $O(2^{0.994n})$ can be transformed into a multi-linear scheme with similar share complexity per bit, for sufficiently long secrets. It is interesting to check, whether similar ideas could be applied to the recent improvement of Beimel et al. with share complexity $O(2^{0.862n})$ for general schemes, transforming it into a . \textbf{On the randomness complexity of polynomial schemes.}\\ We prove that for every degree 2 polynomial secret sharing scheme, there exists an equivalent degree-2 scheme with identical share complexity with randomness complexity bounded by $O(2^{2^n})$. For general polynomial secret sharing schemes, randomness complexity can be bounded by $SC^{O(SC)^2}$, where $SC$ is the share complexity of the original scheme. So far, bounds on randomness complexity were known only for multi linear schemes, demonstrating that $RC \leq SC$ is always achievable. Our bounds are not nearly as practical, and may be viewed as a proof of concept. One nice application of low (say polynomial) randomness complexity is transforming polynomial schemes with polynomial (in $n$) algebraic formulas $C(s,r)$, into a degree-3 scheme with only polynomial blowup in share complexity (using standard randomizing polynomials constructions).

Blockchains have the potential to revolutionize markets and services, yet, currently exhibit high latencies and fail to handle loads comparable to those managed by traditional custodian financial systems. Layer-two protocols, built on top of (layer-one) blockchains, avoid disseminating every transaction to the whole network by sending transactions off-chain and instead utilize the blockchain only as a recourse for disputes. The promise of layer-two protocols is to complete transactions in sub-seconds, reduce fees, and allow blockchains to scale. With this Systematization of Knowledge, we are the first to structure the complete rich and multifaceted body of research on layer-two transactions. Categorizing the research into payment and state channels as well as commit-chains, we provide a comparison of the protocols and their properties. We contribute a systematization of the associated synchronization and routing protocols along with their privacy and security aspects. Contrary to common belief in the blockchain community, we show that layer-two can scale blockchains; that layer-two protocols are secure without full collateralization; that privacy of layer-two transaction is not granted by default; and that fees depend on the transmitted transaction value. The SoK clears the layer-two fog, highlights the potential of layer-two solutions and identifies their unsolved challenges and promising avenues of future work.

We present new secure protocols for approximate $k$-nearest neighbor search ($k$-NNS) over the Euclidean distance in the semi-honest model. Our implementation is able to handle massive datasets efficiently. On the algorithmic front, we show a new circuit for the approximate top-$k$ selection from $n$ numbers that is built from merely $O(n + \mathrm{poly}(k))$ comparators. Using this circuit as a subroutine, we design new approximate $k$-NNS algorithms and two corresponding secure protocols: 1) optimized linear scan; 2) clustering-based sublinear time algorithm.

Our secure protocols utilize a combination of additively-homomorphic encryption, garbled circuit and Oblivious RAM. Along the way, we introduce various optimizations to these primitives, which drastically improve concrete efficiency.

We evaluate the new protocols empirically and show that they are able to handle datasets that are significantly larger than in the prior work. For instance, running on two standard Azure instances within the same availability zone, for a dataset of 96 dimensional descriptors of 10000000 images, we can find 10 nearest neighbors with average accuracy 0.9 in under 10 seconds improving upon prior work by at least two orders of magnitude.

Profiling attacks, especially those based on machine learning proved as very successful techniques in recent years when considering side-channel analysis of block ciphers implementations. At the same time, the results for implementations public-key cryptosystems are very sparse. In this paper, we consider several machine learning techniques in order to mount a power analysis attack on EdDSA using the curve Curve25519 as implemented in WolfSSL. The results show all considered techniques to be viable and powerful options. The results with convolutional neural networks (CNNs) are especially impressive as we are able to break the implementation with only a single measurement in the attack phase while requiring less than 500 measurements in the training phase. Interestingly, that same convolutional neural network was recently shown to perform extremely well for attacking the AES cipher. Our results show that some common grounds can be established when using deep learning for profiling attacks on distinct cryptographic algorithms and their corresponding implementations.

In this paper we present the first fully post-quantum proof of a shuffle for RLWE encryption schemes. Shuffles are commonly used to construct mixing networks (mix-nets), a key element to ensure anonymity in many applications such as electronic voting systems. They should preserve anonymity even against an attack using quantum computers in order to guarantee long-term privacy. The proof presented in this paper is built over RLWE commitments which are perfectly binding and computationally hiding under the RLWE assumption, thus achieving security in a post-quantum scenario. Furthermore we provide a new definition for a secure mixing node (mix-node) and prove that our construction satisfies this definition.

Applications are open for a PhD studentship looking at Post-Quantum Cryptography.

Research supervision

If successful, you will conduct your research under the supervision of the Chair of Cyber Security Professor Delaram Kahrobaei: https://sites.google.com/a/nyu.edu/delaram-kahrobaei/ at University of York; and Director of York Interdisciplinary Centre for Cyber Security www.cs.york.ac.uk/security

Award funding

If successful, you will be supported for three years. Funding includes:

- £14,777 (2018/19 rate) per year stipend

- Home/EU tuition fees

- RTSG (training/consumables/travel) provision

Funding requirements

To be considered for this funding you must:

- meet the entrance requirements for a PhD in Computer Science

- be eligible to pay home/EU fees

We will look favourably on applicants that can demonstrate knowledge of cryptography, algebra, quantum computation, and who have strong programming and mathematical skills.

Apply for this studentship

1. Apply to study

- You must apply online for a full-time PhD in Computer Science.

- You must quote the project title Post-Quantum Cryptography in your application.

- There is no need to write a full formal research proposal (2,000-3,000 words) in your application to study as this studentship is for a specific project.

2. Provide a personal statement. As part of your application please provide a personal statement of 500-1,000 words with your initial thoughts on the research topic.

Deadlines

Applications are accepted all year round.

The start date for the studentship is flexible.

Project enquiries

Professor Delaram Kahrobaei, Chair of Cyber Security (delaram.kahrobaei (at) york.ac.uk):

https://sites.google.com/a/nyu.edu/delaram-kahrobaei/

Application enquiries

cs-pg-admissions (at) york.ac.uk

+44 (0)1904 325404

Closing date for applications: 24 July 2019

Contact: Professor Delaram Kahrobaei, Chair of Cyber Security

https://sites.google.com/a/nyu.edu/delaram-kahrobaei/

Director of York Interdisciplinary Centre for Cyber Security www.cs.york.ac.uk/security

More information: https://www.findaphd.com/phds/project/post-quantum-cryptography/?p104181

The aim of the thesis is to explore how to modify a low power processor architecture in order to include a security dedicated non-volatile operator inside its execution flow. In addition, computation paradigm using this new types of operators will be investigated in order to provide automatic compilation, normally off computation possibilities and a new concept of near sensor cryptography.

In particular, problematic sub-operations (non-linear operations leading to side channel leakage for example) of cryptographic algorithm will be implemented using the new operator in order to evaluate either its security and the energy consumption of the resulting change in the computation paradigm.

Closing date for applications: 10 May 2019

Contact: Cédric Marchand

More information: http://inl.cnrs.fr/files/Th%C3%A8ses20192020/INL04_EDEEA_Navarro_Marchand_2019.pdf

The Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS) of Nanyang Technological University in Singapore is the one-stop centre for knowledge, technologies, and solutions for privacy-preserving problems. We seek highly motivated researchers to fill several R&D positions ranging from fresh postdoc research fellows to senior research scientists. The successful applicant is expected to have strong system and privacy research experiences and software development skills in the areas including but not limited to Fully Homomorphic Encryption (FHE), Multi-Party Computation (MPC), Searchable Encryptions (SE), and Differential Privacy (DP). The applicant is also expected to have proven record of top publications (IACR conferences, S&P, CCS, Usenix, NDSS, etc).

We offer a globally competitive salary package and low income tax, plus an excellent research environment in Singapore. The initial contract will be for 2 years, and renewable subject to the performance. Interested candidates are to send their CV, and 2 reference letters to Dr. Le Su. Review of application will start immediately until the positions are filled.

Closing date for applications: 7 October 2019

Contact: Dr. Le Su, le.su (at) ntu.edu.sg

The Strategic Centre for Research in Privacy-Preserving Technologies & Systems (SCRIPTS) of Nanyang Technological University in Singapore is the one-stop centre for knowledge, technologies, and solutions for privacy-preserving problems. We seek highly motivated researchers to fill several R&D positions ranging from fresh postdoc research fellows to senior research scientists. The successful applicant is expected to have strong system and privacy research experiences and software development skills in the areas including but not limited to Fully Homomorphic Encryption (FHE), Multi-Party Computation (MPC), Searchable Encryptions (SE), and Differential Privacy (DP). The applicant is also expected to have proven record of top publications (IACR conferences, S&P, CCS, Usenix, NDSS, etc).

We offer a globally competitive salary package and low income tax, plus an excellent research environment in Singapore. The initial contract will be for 2 years, and renewable subject to the performance. Interested candidates are to send their CV, and 2 reference letters to Dr. Le Su. Review of application will start immediately until the positions are filled.

Closing date for applications: 7 October 2019

Contact: Dr. Le Su, le.su (at) ntu.edu.sg

Job description:

The professorship will be dedicated to the combination of artificial intelligence and IT security. We seek a broad range of applicants with experience and focus in at least one of the following domains:

AI methods that improve the security of IT systems

IT security methods for AI-based systems.

KIT has research competence in various fields of IT security and artificial intelligence. In particular, the candidate is planned to be affiliated with the Competence Center for Applied Security Technology (KASTEL) as well as IT security research at KIT within the framework of the Helmholtz Association. In addition, it is expected that the candidate strengthens a strategic focus of secure and dependable systems at the Faculty of Informatics.

The new professor is expected to teach courses in the core curriculum of the department of Informatics, in both mandatory and elective areas. During the first three years, the teaching can be performed in English language.

The candidate is expected to actively shape research at KIT, to advance the personal development of her/himself and independently supervise doctoral researchers as well as graduate and undergraduate students. The new professor shall successfully combine collaborative work attitude with strong communication skills.

The initial appointment is for six years as a temporary civil servant or as an employee. An interim evaluation is carried out in the third year of service. If the final tenure evaluation is positive, the successful candidate will be promoted to a tenured full professorship (W3) in accordance with §15 (2) KITG.

Starting date:as soon as possible

Closing date for applications: 8 April 2019

Contact: Prof. Dr. Bernhard Beckert, email: bernhard.beckert (at) kit.edu

More information: https://www.pse.kit.edu/karriere/567.php

Requirements:

- PhD degree in Computer Science

- Good track record in top conferences

- With system background (e.g., Linux)

- Experience in blockchain (e.g., Ethereum, Hyperledger)

Closing date for applications: 1 July 2019

Contact: Send your CV to ericlo (at) cse.cuhk.edu.hk using the email subject \"Post-doc applicant: [Your Name]\" (e.g., \"Post-doc applicant: Harry Porter\").