International Association
for Cryptologic Research

A major approach to overcoming the performance and scalability limitations of current blockchain protocols is to use sharding, which is to split the overheads of processing transactions among multiple, smaller groups of nodes. These groups work in parallel to maximize performance while requiring significantly smaller communication, computation, and storage per node, allowing the system to scale to large networks. However, existing sharding-based blockchain protocols still require a linear amount of communication (in the number of participants) per transaction, and hence, attain only partially the potential benefits of sharding. We show that this introduces a major bottleneck to the throughput and latency of these protocols. Aside from the limited scalability, these protocols achieve weak security guarantees due to either a small fault resiliency (e.g., $1/8$ and $1/4$) or high failure probability, or they rely on strong assumptions (e.g., trusted setup) that limit their applicability to mainstream payment systems.

We propose RapidChain, the first sharding-based public blockchain protocol that is resilient to Byzantine faults from up to a $1/3$ fraction of its participants, and achieves complete sharding of the communication, computation, and storage overhead of processing transactions without assuming any trusted setup. We introduce an optimal intra-committee consensus algorithm that can achieve very high throughputs via block pipelining, a novel gossiping protocol for large blocks, and a provably-secure reconfiguration mechanism to ensure robustness. Using an efficient cross-shard transaction verification technique, RapidChain avoids gossiping transactions to the entire network. Our empirical evaluations suggest that RapidChain can process (and confirm) more than 7,300 tx/sec with an expected confirmation latency of roughly 8.7 seconds in a network of 4,000 nodes with an overwhelming time-to-failure of more than 4,500 years.

We present an oblivious transfer (OT) protocol that combines the OT scheme of Chou and Orlandi together with the supersingular isogeny Diffie-Hellman (SIDH) primitive of De Feo, Jao, and Plût. Our construction is a candidate for post-quantum secure OT and demonstrates that SIDH naturally supports OT functionality. We consider the protocol in the simplest configuration of $\binom{2}{1}$-OT and analyze the protocol to verify its security.

Linicrypt (Carmer & Rosulek, Crypto 2016) refers to the class of algorithms that make calls to a random oracle and otherwise manipulate values via fixed linear operations. We give a characterization of collision-resistance and second-preimage resistance for a significant class of Linicrypt programs (specifically, those that achieve domain separation on their random oracle queries via nonces). Our characterization implies that collision-resistance and second-preimage resistance are equivalent, in an asymptotic sense, for this class. Furthermore, there is a polynomial-time procedure for determining whether such a Linicrypt program is collision/second-preimage resistant.

Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure.

Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results.

1) A two round semi-honest MPC protocol in the plain model secure against up to (n-1) corruptions with communication complexity proportional only to the depth of the circuit being computed assuming LWE. Prior two round protocols that achieved this communication complexity required a common reference string.

2) A functional encryption combiner based on pseudorandom generators (PRGs) in NC^1. Such PRGs can be instantiated from assumptions such as DDH and LWE. Previous constructions of FE combiners were known only from the learning with errors assumption. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption based only on the assumptions that functional encryption exists and PRGs in NC^1.

We present an efficient key recovery attack on code based encryption schemes using some quasi–dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.

We consider single and multiple attacker scenarios in guessing and obtain bounds on various success parameters in terms of Renyi entropies. We also obtain a new derivation of the union bound.

Cryptocurrencies and blockchains are set to play a major role in the financial and supply-chain systems. Their presence and acceptance across different geopolitical corridors, including in repressive regimes, have been one of their striking features. In this work, we leverage this popularity for bootstrapping censorship resistant (CR) communication. We formalize the notion of stego-bootstrapping scheme and formally describe the security notions of the scheme in terms of rareness and security against chosen-covertext attacks. We present R3C3, a Cryptographically secure Censorship-Resistant Rendezvous using Cryptocurrencies. R3C3 allows a censored user to interact with a decoder entity outside the censored region, through blockchain transactions as rendezvous, to obtain bootstrapping information such as a CR proxy and its public key. Unlike the usual bootstrapping approaches (e.g., emailing) with heuristic security if any, R3C3 employs public-key steganography over blockchain transactions to ensure cryptographic security, while the blockchain transaction costs may deter the entry-point harvesting attacks. We develop bootstrapping rendezvous over Bitcoin, Zcash, Monero and Ethereum as well as the typical mining process, and analyze their effectivity in terms of cryptocurrency network volume and introduced monetary cost. With its highly cryptographic structure, Zcash is an outright winner for normal users with 1168 byte bandwidth per transaction costing only 0.03 USD as the fee, while mining pool managers have a free, extremely high bandwidth rendezvous when they mine a block.

We present the first lattice-based group signature scheme whose cryptographic artifacts are of size small enough to be usable in practice: for a group of $2^{25}$ users, signatures take 910 kB and public keys are 501 kB. Our scheme builds upon two recently proposed lattice-based primitives: the verifiable encryption scheme by Lyubashevsky and Neven (Eurocrypt 2017) and the signature scheme by Boschini, Camenisch, and Neven (IACR ePrint 2017). To achieve such short signatures and keys, we first re-define verifiable encryption to allow one to encrypt a function of the witness, rather than the full witness. This definition enables more efficient realizations of verifiable encryption and is of independent interest. Second, to minimize the size of the signatures and public keys of our group signature scheme, we revisit the proof of knowledge of a signature and the proofs in the verifiable encryption scheme provided in the respective papers.

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