International Association
for Cryptologic Research

Performance of cryptanalytic quantum search algorithms is mainly inferred from query complexity which hides overhead induced by an implementation. To shed light on quantitative complexity analysis removing hidden factors, we provide a framework for estimating times-pace complexity, with carefully accounting for characteristics of target cryptographic functions. Processor and circuit parallelization methods are taken into account, resulting in the time-space trade-offs curves in terms of depth and qubit. The method guides how to rank different circuit designs in order of their efficiency. The framework is applied to representative cryptosystems NIST referred to as a guideline for security parameters, reassessing the security strengths of AES and SHA-2.

In (STOC, 2008), Gentry, Peikert, and Vaikuntanathan proposed the first identity-based encryption (GPV-IBE) scheme based on a post-quantum assumption, namely, the learning with errors (LWE) assumption. Since their proof was only made in the random oracle model (ROM) instead of the quantum random oracle model (QROM), it remained unclear whether the scheme was truly post-quantum or not. In (CRYPTO, 2012), Zhandry developed new techniques to be used in the QROM and proved the security of GPV-IBE in the QROM, hence answering in the affirmative that GPV-IBE is indeed post-quantum. However, since the general technique developed by Zhandry incurred a large reduction loss, there was a wide gap between the concrete efficiency and security level provided by GPV-IBE in the ROM and QROM. Furthermore, regardless of being in the ROM or QROM, GPV-IBE is not known to have a tight reduction in the multi-challenge setting. Considering that in the real-world an adversary can obtain many ciphertexts, it is desirable to have a security proof that does not degrade with the number of challenge ciphertext.

In this paper, we provide a much tighter proof for the GPV-IBE in the QROM in the single-challenge setting. We also show that a slight variant of the GPV-IBE has an almost tight reduction in the multi-challenge setting both in the ROM and QROM, where the reduction loss is independent of the number of challenge ciphertext. Our proof departs from the traditional partitioning technique and resembles the approach used in the public key encryption scheme of Cramer and Shoup (CRYPTO, 1998). Our proof strategy allows the reduction algorithm to program the random oracle the same way for all identities and naturally fits the QROM setting where an adversary may query a superposition of all identities in one random oracle query. Notably, our proofs are much simpler than the one by Zhandry and conceptually much easier to follow for cryptographers not familiar with quantum computation. Although at a high level, the techniques used for the single and multi-challenge setting are similar, the technical details are quite different. For the multi-challenge setting, we rely on the Katz-Wang technique (CCS, 2003) to overcome some obstacles regarding the leftover hash lemma.

We discuss the widely increasing range of applications of a cryptographic technique called Multi-Party Computation. For many decades this was perceived to be of purely theoretical interest, but now it has started to find application in a number of use cases. We highly in this paper a number of these, ranging from securing small high value items such as cryptographic keys, through to securing an entire database.

The keyed sponge is a well-accepted method for message authentication. It processes data at a certain rate by sequential evaluation of an underlying permutation. If the key size $k$ is smaller than the rate, currently known bounds are tight, but if it exceeds the rate, state of the art only dictates security up to $2^{k/2}$. We take closer inspection at the key prediction security of the sponge and close the remaining gap in the existing security analysis: we confirm key security up to close to $2^k$, regardless of the rate. The result impacts all applications of the keyed sponge and duplex that process at a rate smaller than the key size, including the STROBE protocol framework, as well as the related constructions such as HMAC-SHA-3 and the sandwich sponge.

This paper applies non-adaptive group testing to aggregate message authentication code (MAC) and introduces non-adaptive group-testing aggregate MAC. After formalization of its syntax and security requirements, simple and generic construction is presented, which can be applied to any aggregate MAC scheme formalized by Katz and Lindell in 2008. Then, two instantioations of the construction is presented. One is based on the aggregate MAC scheme by Katz and Lindell and uses addition for tag aggregate. The other uses cryptographic hashing for tag aggregate. Provable security of the generic construction and two instantiations are also discussed.

Division property is a distinguishing property against block ciphers proposed by Todo at EURO- CRYPT 2015. To give a new approach to division property, Christina et al. proposed a new notion called the parity set at CRYPTO 2016. Using parity sets, they successfully took further properties of S-boxes and linear layers into account and found improved distinguishers against PRESENT. However, the time and memory complexities to compute parity sets are expensive. In this paper, we introduce the idea of meet-in-the-middle to the integral distinguisher search along with a variety of techniques to reduce computation complexity. As a result, we obtain a new distinguisher against 9-round PRESENT which has 22 balanced bits.

Traditional cryptography is under huge threat along of the evolution of quantum information and computing. In this paper, we propose a new post-quantum voting scheme based on physical laws by using encrypted no-key protocol to transmit message in the channel, which ensures the post-quantum security. Unlike lattice-based and multivariate-based electronic voting schemes, whose security is based on the computational problems assumption that has not been solved by effective quantum algorithms until now, the security of the voting scheme based on the physical laws is depended on inherent limitations of quantum computers and not influenced by the evolution of new quantum algorithms. In detail, we also rigorously demonstrate that the scheme achieves the post-quantum security and all properties necessary for voting scheme such as the completeness, robustness, privacy, eligibility, unreusability, fairness, and verifiability.

At CSIT we focus on securing our digital tomorrow. Our world-leading research into cyber-security is breaking new ground in making devices and networks more resilient to attack, not just for the technology limits of today but for the challenges of the next generation.

The Centre for Secure Information Technologies (CSIT) is the UK national Innovation and Knowledge Centre for cyber security. With a remit to conduct world leading research into applied cryptography, network security and security analytics (Big Data) the centre also has responsibility to commercialise that research and support the growth of the cyber security industry in the UK

You will lead projects and initiatives that turn fundamental concepts into reliable maintainable code that is usable and extensible by the cryptographic community.

CSIT employs a team of 15 experienced product developers in both software and hardware systems to further develop these ideas into well-engineered prototypes and technology demonstrators.

The CSIT engineering function sits between in-house research teams and the R&D labs of our industrial partners such as BAE Systems, Thales, Infosys, Allstate, Direct Line Group, Seagate, First Derivatives etc.

CSIT hosts the UK Research Institute in Secure Hardware and Embedded systems (RISE) (www.ukrise.org).

In return you for your commitment you will be working on emerging technology and at the forefront of this innovation. QUB provides a strong commitment to professional development and opportunities for part time study and post-graduate research are available.

Closing date for applications: 13 June 2018

Contact: Gavin McWilliams, Director of Engineering, CSIT, QUB (Email: g.mcwilliams (at) qub.ac.uk)

More information: http://www.ecit.qub.ac.uk/Jobs/

Have you heard about the Streamr project? https://www.streamr.com

Have you worked on crypto projects, blockchains, or ICO projects? Do you have skills with decentralized protocols, IPFS, Swarm? Interested in showing your magic in an open source project?

Streamr (based in Zug, Switzerland) is creating an open source platform for the free and fair exchange of the world’s real-time data. Our blockchain-backed data Marketplace and powerful tools put your data back where it belongs – with you!

Data in Chains (based in Helsinki) is the primary development arm for Streamr. We have a dozen highly talented software engineers and blockchain specialists who are hard at work building the Streamr Platform in conjunction with Streamr developers in Switzerland.

So, here is the job:

Participate in planning and implementation of the security aspects and proof/token mechanics on the Streamr Network

Dig deep into end-to-end encryption, multicast encryption, key management and delivery, content signing, security best practices, game theoretical implications of adversarial networks

Work together with the overall Streamr team to make the Network layer work seamlessly with other components of the Streamr system and the companion blockchain (in the beginning, Ethereum)

Requirements:

Working experience in cryptography / security

Highly analytical mind with good math skills and ability to read and understand academic papers

Good programming fluency in JavaScript, Go, Java, or similar

Interest in decentralized technology and blockchains

Excellent English and communication skills

We Appreciate Experience In:

Experience with end-to-end encrypted messaging protocols (Matrix, Signal)

Familiarity with peer-to-peer networking, especially protocols and libraries used in the decentralized/blockchain space (Whisper, PPS (Swarm), libp2p, devp2p)

Code contributions to blockchains or other P2P networks

Ethereum smart contract development in Solidity

Experience with real-time data or messaging

Closing date for applications: 14 September 2018

Contact: Gavin Roush

Recruiter

gavin (at) datainchains.com

More information: https://www.linkedin.com/jobs/view/664561386/

Event date: 28 May 2018

Event date: 9 December to 12 December 2018
Submission deadline: 25 August 2018
Notification: 12 October 2018

Event date: 24 June to 27 June 2019
Submission deadline: 28 February 2019

Event date: 10 September to 12 September 2018
Submission deadline: 20 June 2018
Notification: 27 July 2018

Event date: 10 December to 13 December 2018
Submission deadline: 26 May 2018
Notification: 14 August 2018

Event date: 4 March to 8 March 2019
Submission deadline: 14 September 2018
Notification: 19 November 2018

We propose a detailed construction of Collision Resistance Preimage Sampleable Functions $($CRPSF$)$ over any cyclotomic field based on NTRU, hence give a provably secure NTRU Signature scheme $($NTRUSign$)$, which is strongly existentially unforgeable under adaptive chosen-message attacks in the random oracle module. The security of CRPSF $($NTRUSign$)$ is reduced to the corresponding small integer solution problem over rings $($Ring-SIS$)$. More precisely, the security of our scheme is based on the worst-case approximate shortest independent vectors problem $($SIVP$_\gamma$$)$ over ideal lattices. For any fixed cyclotomic field, we give a probabilistic polynomial time $($PPT$)$ key generation algorithm which shows how to extend the secret key of NTRUEncrypt to the secret key of NTRUSign. This conversion is important for constructions of many cryptographic primitives based on NTRU, for example, CRPSF, NTRUSign, identity-based encryption and identity-based signature. We also delve back into former construction of NTRUEncrypt and enrich the choices of the module $q$. Some useful results about $q$-ary lattices, regularity and uniformity of distribution of the public key of NTRUEncrypt are also generalized to more general algebraic field $K$, as long as $K$ is Galois over $\mathbb{Q}$.

Oblivious transfer (OT) is a fundamental primitive in cryptography. Halevi-Kalai OT (Halevi, S. and Y. Kalai (2012), Journal of Cryptology 25(1)), which is based on smooth projective hash(SPH), is a famous and the most efficient framework for $1$-out-of-$2$ oblivious transfer ($\mbox{OT}^{2}_{1}$) against malicious adversaries in plain model. However, it does not provide simulation-based security. Thus, it is harder to use it as a building block in secure multiparty computation (SMPC) protocols. A natural question however, which so far has not been answered, is whether it can be can be made fully-simulatable. In this paper, we give a positive answer. Further, we present a fully-simulatable framework for general $\mbox{OT}^{n}_{t}$ ($n,t\in \mathbb{N}$ and $n>t$). Our framework can be interpreted as a constant-round blackbox reduction of $\mbox{OT}^{n}_{t}$ (or $\mbox{OT}^{2}_{1}$) to SPH. To our knowledge, this is the first such reduction. Combining Kilian's famous completeness result, we immediately obtain a black-box reduction of SMPC to SPH.

Fully homomorphic encryption (FHE) is a powerful notion of encryption which allows data to be encrypted in such a way that anyone can perform arbitrary computations over the encrypted data without decryption or knowledge of the secret key. Traditionally, FHE only allows for computations over data encrypted under a single public key. Lopez-Alt et al. (STOC 2012) introduced a new notion of FHE, called multi-key FHE (MFHE), which permits joint computations over data encrypted under multiple independently-generated (unrelated) keys such that any evaluated ciphertext could be (jointly) decrypted by the parties involved in the computation. Such MFHE schemes could be readily used to delegate computation to cloud securely.

Recently a number of works have studied the problem of constructing quantum homomorphic encryption (QHE) which is to perform quantum computations over encrypted quantum data. In this work we initiate the study of quantum multi-key homomorphic encryption (QMHE) and obtain the following results:

1) We formally define the notion of quantum multi-key homomorphic encryption and construct such schemes from their classical counterpart. Building on the framework of Broadbent and Jeffery (Crypto 2015) and Dulek et al. (Crypto 2016), we show that any classical multi-key leveled homomorphic encryption can be used to build a quantum multi-key leveled homomorphic encryption if we also have certain suitable error-correcting quantum gadgets. The length of the evaluation key grows linearly with the number of $T$-gates in the quantum circuit, thereby giving us a quantum multi-key leveled homomorphic encryption for circuits with polynomial but bounded number of $T$-gates.

2) To enable a generic transformation from any classical multi-key scheme, we introduce and construct a new cryptographic primitive which we call conditional oblivious quantum transform (COQT). A COQT is a distributed non-interactive encoding scheme that captures the essence of error-correcting gadgets required for quantum homomorphic encryption in the multi-key setting. We then build COQTs themselves from any classical multi-key leveled homomorphic encryption with $\boldsymbol{\mathrm{NC}}^1$ decryption. We believe that COQTs might be an object of independent interest.

3) We also show that our quantum multi-key homomorphic encryption schemes support distributed decryption of multi-key ciphertexts as well as allows ciphertext re-randomizability (thereby achieves quantum circuit privacy) if the underlying classical scheme also supports distributed decryption and satisfies classical circuit privacy. We show usefulness of distributed decryption and ciphertext re-randomizability for QMHE by providing efficient templates for building multi-party delegated/server-assisted quantum computation protocols from QMHE.

Additionally, due to our generic transformation, our quantum multi-key HE scheme inherits various features of the underlying classical scheme such as: identity/attribute-based, multi-hop, etc.

Neural Networks (NN) provide a powerful method for machine learning training and prediction. For effective training, it is often desirable for multiple parties to combine their data -- however, doing so conflicts with data privacy. In this work, we provide novel three-party and four-party secure computation protocols for various NN building blocks such as matrix multiplication, Rectified Linear Units, MaxPool, normalization etc. This enables us to construct three-party and four-party information-theoretically secure protocols for training and prediction of CNNs, DNNs and a number of other NN architectures such that no single party learns any information about the data.

Experimentally, we build a system and train a (A) 3-layer DNN (B) 4-layer CNN from MiniONN, and (C) 4-layer LeNet network. Compared to the state-of-the-art prior work SecureML (Mohassel and Zhang, IEEE S&P 2017) that provided (computationally-secure) protocols for only the network A in the 2 and 3-party setting, we obtain 93X and 8X improvements, respectively. In the WAN setting, these improvements are more drastic - for example, we obtain an improvement of 407X. Our efficiency gains come from a >8X improvement in communication, coupled with the complete elimination of expensive oblivious transfer protocols. In fact, our results show that the overhead of executing secure training protocols is only between 17-33X of the cleartext implementation even for networks that achieve >99% accuracy.

In a $k$-party CDS protocol, each party sends one message to a referee (without seeing the other messages) such that the referee will learn a secret held by the parties if and only if the inputs of the parties satisfy some condition (e.g., if the inputs are all equal). This simple primitive is used to construct attribute based encryption, symmetrically-private information retrieval, priced oblivious transfer, and secret-sharing schemes for any access structure. Motivated by these applications, CDS protocols have been recently studied in many papers. In this work, we study linear CDS protocols, where each of the messages of the parties is a linear function of the secret and random elements taken from some finite field. Linearity is an important property of CDS protocols as many applications of CDS protocols required it.

Our main result is a construction of linear $k$-party CDS protocols for an arbitrary function $f:[N]^{k}\rightarrow \{0,1\}$ with messages of size $O(N^{(k-1)/2})$. By a lower bound of Beimel et al. [TCC 2017], this message size is optimal. We also consider functions with few inputs that return one, and design more efficient CDS protocols for them.

CDS protocols can be used to construct secret-sharing schemes for uniform access structures, where for some $k$ all sets of size less than $k$ are unauthorized, all sets of size greater than $k$ are authorized, and each set of size $k$ can be either authorized or unauthorized. We show that our results imply that every $k$-uniform access structure with $n$ parties can be realized by a linear secret-sharing scheme with share size $\min\{ (O(n/k))^{(k-1)/2},O(n \cdot 2^{n/2})\}$. Furthermore, the linear $k$-party CDS protocol with messages of size $O(N^{(k-1)/2})$ was recently used by Liu and Vaikuntanathan [STOC 2018] to construct a linear secret-sharing scheme with share size $O(2^{0.999n})$ for any $n$-party access structure.