International Association
for Cryptologic Research

We propose and evaluate a secure-multiparty-computation (MPC) solution, in the semi-honest model with dishonest majority, based on multiparty homomorphic encryption (MHE). To support this solution, we introduce a multiparty version of the Brakerski-Fan-Vercauteren lattice-based homomorphic cryptosystem, implement it in an open-source library, and evaluate its performance. We show that such MHE-based MPC solutions have several advantages over current approaches: Their public transcripts and non-interactive circuit-evaluation capabilities enable a broad variety of computing paradigms, ranging from the traditional peer-to-peer setting to cloud-outsourcing and smart-contract technologies. Exploiting these properties, the communication complexity of MPC tasks can be reduced from quadratic to linear in the number of parties, thus enabling secure computation among thousands of parties. Additionally, MHE-based approaches can outperform the state-of-the-art even for a small number of parties. We demonstrate this for three circuits: component-wise vector multiplication with application to private-set intersection, private input selection with application to private-information retrieval, and multiplication triples generation. For the first circuit evaluated among eight parties, our approach is 8.6 times faster and requires 39.3 times less communication than the state-of-the-art approach. The input selection circuit over eight thousand parties completed in 61.7 seconds and required 1.31 MB of communication per party.

Payment channel networks have been introduced to mitigate the scalability issues inherent to permissionless decentralized cryptocurrencies such as Bitcoin. Launched in 2018, the Lightning Network (LN) has been gaining popularity and consists today of more than 5000 nodes and 30000 payment channels that jointly hold 895 bitcoins (7.6M USD as of February 2020). This adoption has motivated research from both academia and industry.

Payment channels suffer from security vulnerabilities, such as the wormhole attack, anonymity issues, and scalability limitations related to the upper bound on the number of concurrent payments per channel, which have been pointed out by the scientific community but never quantitatively analyzed.

In this work, we first analyze the proneness of the LN to the wormhole attack and attacks against anonymity. We observe that an adversary needs to control only 2% of LN nodes to learn sensitive payment information (e.g., sender, receiver and payment amount) or to carry out the wormhole attack. Second, we study the management of concurrent payments in the LN and quantify its negative effect on scalability. We observe that for micropayments, the forwarding capability of up to 50% of channels is restricted to a value smaller than the overall channel capacity. This phenomenon not only hinders scalability but also opens the door for DoS attacks: We estimate that a network-wide DoS attack costs within 1.5M USD, while isolating the biggest community from the rest of the network costs only 225k USD.

Our findings should prompt the LN community to consider the security, privacy and scalability issues of the network studied in this work when educating users about path selection algorithms, as well as to adopt multi-hop payment protocols that provide stronger security, privacy and scalability guarantees.

We present a stochastic method for breaking general periodic polyalphabetic substitution ciphers using only the ciphertext and without using any additional constraints that might come from the cipher’s structure. The method employs a hill-climbing algorithm for individual key alphabets, with occasional slipping down the hill. We implement the method with a computer and achieve reliable results for a sufficiently long ciphertext (150 characters per key alphabet). Because no constraints among the key alphabets are used, this method applies to any periodic polyalphabetic substitution cipher.

We present a toy cipher that has two novel features: Two plaintexts are concealed by the same ciphertext in different schemes, and the enumeration of the permutations of ciphertext symbols (not the permutations of plaintext symbols, as used in transposition ciphers) forms the basis of one of the schemes. The other scheme uses mixed-radix numbers as substitutes for plaintext symbols. Both schemes use the same symbols, but with different interpretations, and this allows two plaintexts to be encrypted in the same ciphertext.

Event date: 20 November to 22 November 2020
Submission deadline: 21 June 2020
Notification: 31 July 2020

The School of Cyber Science and Engineering (formerly known as the School of Information Security Engineering) of Shanghai Jiao Tong University was founded in October 2000. It was the first school-level training base for high-level information security professionals in China and was jointly established by the Ministry of Education of China, the Ministry of Science and Technology of China, and the Shanghai Municipal People’s Government. The undergraduate and postgraduate students of the school mainly come from the top 100 key high schools and 985/double first-class universities in China. The school is ranked among the best cyberspace security nationwide every year. The school has a solid foundation and strength in the field of academic research and technological innovation on cyberspace security. The school is committed to building a world-class academic research center, cultivating the talents of the country and society. The school is in great demand of a number of world renowned professors, outstanding young researchers, full-time research fellows and post-doctors. The school now has about 20 positions available at the rank of tenure-track Assistant Professors, tenure-track Associate Professors, or tenured Full Professors in theory and practice of cyberspace security. Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching. The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “1000 Youth Talents Program”, Shanghai “Oriental Scholar Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.

Closing date for applications:

Contact: Chaoping Xing, emial: xingcp@sjtu.edu.cn Linjie Li, email: lilinjie@sjtu.edu.cn

More information: http://english.seiee.sjtu.edu.cn/english/info/14810.htm

This is an exciting opportunity to join the University of Birmingham’s Centre for Cyber Security and Privacy on an exciting EPSRC funded project ‘SIPP - Secure IoT Processor Platform with Remote Attestation’. The proposed project brings together the core partners of the NCSC/EPSRC-funded Research Institute in Secure Hardware and Embedded Systems (RISE), that is, Queen's University Belfast and the Universities of Cambridge, Bristol and Birmingham, with the leading academics in the field of hardware security and security architecture design from the National University of Singapore and Nanyang Technological University, to develop a novel secure IoT processor platform with remote attestation implemented on the RISC-V architecture. To download the full job description and details of this position and submit an electronic application online please click on the Apply Online button below or visit our careers website; https://bham.taleo.net/careersection/external/jobsearch.ftl?lang=en&portal=101430233, please quote Job Ref 95352 in all enquiries.

Closing date for applications:

Contact: For informal inquiries please contact Mark Ryan; ryanmd@adf.bham.uk

More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=190005S3&tz=GMT%2B00%3A00&tzname=Europe%2FLondon

NuCypher is a cryptography company that builds privacy-preserving infrastructure and protocols. We are backed by Y Combinator and Polychain Capital.

A successful candidate will lead engineering for the new open-source cryptographic product from the ground up. They will work on problems at the forefront of cryptography and have a leadership role in design decisions of the system. As such, competency in algorithms and low-level design is a must. An interest in compilers and/or optimization would be nice to have.

Given the nature of an early stage product, a successful candidate should work in a fast and iterative style when it comes to prototyping. They will be be motivated by solving tough open-ended problems. Additionally, they should be highly comfortable working in a system programming language such as C or Rust (whether through work experience or side projects).

We offer extremely competitive compensation and a highly flexible working environment (remote-first, headquartered in San Francisco).

Closing date for applications:

Contact: Ravital Solomon

Event date: 14 September to 18 September 2020
Submission deadline: 10 April 2020
Notification: 15 June 2020

Event date: 11 June to 12 June 2020

Protocols for secure multiparty computation (MPC) enable a set of parties to interact and compute a joint function of their private inputs while revealing nothing but the output. The potential applications for MPC are huge: privacy-preserving auctions, private DNA comparisons, private machine learning, threshold cryptography, and more. Due to this, MPC has been an intensive topic of research in academia ever since it was introduced in the 1980s by Yao for the two-party case (FOCS 1986), and by Goldreich, Micali and Wigderson for the multiparty case (STOC 1987). Recently, MPC has become efficient enough to be used in practice, and has made the transition from an object of theoretical study to a technology being used in industry. In this article, we will review what MPC is, what problems it solves, and how it is being currently used.

We note that the examples and references brought in this review article are far from comprehensive, and due to the lack of space many highly relevant works are not cited.

State channels are an attractive layer-two solution for improving the throughput and latency of blockchains. They offer optimistic fast offchain settlement of payments and rapid offchain evolution of smart contracts between multiple parties without imposing any additional assumptions beyond those of the underlying blockchain. In the case of disputes, or if a party fails to respond, cryptographic evidence collected in the offchain channel is used to settle the last confirmed state onchain, such that in-progress contracts can be continued under mainchain consensus. A serious disadvantage present in current layer-two state channel protocols is that existing layer-one smart contract infrastructure and contract code cannot be reused offchain without change. In this paper, we introduce Hydra, an isomorphic multi-party state channel. Hydra simplifies offchain protocol and contract development by directly adopting the layer-one smart contract system. We present the onchain contracts to open and close Hydra heads (our isomorphic state channels) and a novel offchain protocol for fast evolution of heads. We establish strong security properties for the protocol, and we present and evaluate extensive simulation results that demonstrate that Hydra approaches the physical limits of the network in terms of transaction confirmation time and throughput while keeping storage requirements at the lowest possible.

The NIST PQC standardization project evaluates multiple new designs for post-quantum Key Encapsulation Mechanisms (KEMs). Some of them present challenging tradeoffs between communication bandwidth and computational overheads. An interesting case is the set of QC-MDPC based KEMs. Here, schemes that use the Niederreiter framework require only half the communication bandwidth compared to schemes that use the McEliece framework. However, this requires costly polynomial inversion during the key generation, which is prohibitive when ephemeral keys are used. One example is BIKE, where the BIKE-1 variant uses McEliece and the BIKE-2 variant uses Niederreiter. This paper shows an optimized constant-time polynomial inversion method that makes the computation costs of BIKE-2 key generation tolerable. We report a speedup of 11.8x over the commonly used NTL library, and 55.5 over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions on a laptop machine, 14.3x over NTL and 96.8x over OpenSSL. With this, BIKE-2 becomes a competitive variant of BIKE.

Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an Abelian group, called the *Arakelov class group*. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to significant cryptanalytic advances: the class group and the unit torus.

In the present article, we show that the Arakelov class group has more to offer. We start with the development of a new versatile tool: we prove that, subject to the Riemann Hypothesis for Hecke $L$-functions, certain random walks on the Arakelov class group have a rapid mixing property. We then exploit this result to relate the average-case and the worst-case of the Shortest Vector Problem in ideal lattices. Our reduction appears particularly sharp: for Hermite-SVP in ideal lattices of certain cyclotomic number fields, it loses no more than a $\tilde O(\sqrt n)$ factor on the Hermite approximation factor.

Furthermore, we suggest that this rapid-mixing theorem should find other applications in cryptography and in algorithmic number theory.

This work considers the security of systems that process encrypted multi-dimensional range queries with only access pattern leakage. Recent work of Kellaris et al. (CCS 2016) showed that in one dimension, an adversary could use the access patterns of several uniformly random range queries to reconstruct a plaintext column of numbers “up to reflection.” We extend this attack to two dimensions and find that the situation is much more complicated: Information theoretically it is complex to describe even what is possible to recover for the adversary in general. We provide a classification of these limits under certain technical conditions. We also give a faster algorithm that works for “dense” databases that contain at least one record for each possible value. Finally we explore the implications for our classification with real data sets.

In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (2018), when the starting function is a Gold function. In particular, we derive a general construction of APN functions which produces one new APN function for $n=8$ and fifteen new APN functions for $n=9$.

We revisit the problem of proving that a user algorithm selected and correctly used a truly random seed in the generation of her cryptographic key. A first approach was proposed in 2002 by Juels and Guajardo for the validation of RSA secret keys. We present a new security model and general tools to efficiently prove that a private key was generated at random according to a prescribed process, without revealing any further information about the private key. In addition to formalizing randomness verifiability in key generation, which turns out to be highly non-trivial, we give a generic protocol for all key-generation algorithms based on probabilistic circuits and prove its security. We also propose a new protocol for factoring-based cryptography that we prove secure in the aforementioned model, as well as a practical instantiation. This latter relies on a new efficient zero-knowledge argument for the double discrete logarithm problem that achieves an exponential improvement in communication complexity compared to the state of the art, and is of independent interest.

Dear IACR Member,

As a consequence of the COVID-19 crisis, the Greek Health ministry took on March 8 the decision to suspend all conference events for the next four weeks (the announcement in Greek can be found here.).

Under these force majeure circumstances, FSE 2020 is postponed.

More details will follow soon.

For any questions please contact the General Chairs at fse2020@iacr.org

Event date: 16 July to 17 July 2020
Submission deadline: 24 April 2020
Notification: 4 May 2020

We introduce a family of extensions to the one-out-of-many proofs of Groth and Kohlweiss (Eurocrypt 2015), which efficiently prove statements about many messages among a list of commitments. These extensions prove knowledge of a secret subset of the list, and assert that the commitments in the subset satisfy certain properties (expressed as linear equations). Our communication remains logarithmic; our computation increases only by a logarithmic multiplicative factor. Our work introduces a new "circular rotation" technique, and a novel instantiation of the number-theoretic transform.

Applying these techniques, we construct a protocol for the Anonymous Zether payment system—as proposed in Bünz, Agrawal, Zamani, and Boneh (FC'20)—which improves upon the communication complexity attained by existing efforts. We describe an open-source, Ethereum-based implementation of our protocol.