International Association
for Cryptologic Research

The Lightning Network is a second layer technology running on top of Bitcoin and other Blockchains. It is composed of a peer-to-peer network, used to transfer raw information data. Some of the links in the peer-to-peer network are identified as payment channels, used to conduct payments between two Lightning Network clients (i.e., the two nodes of the channel). Payment channels are created with a fixed credit amount, the channel capacity. The channel capacity, together with the IP address of the nodes, is published to allow a routing algorithm to find an existing path between two nodes that do not have a direct payment channel. However, to preserve users' privacy, the precise balance of the pair of nodes of a given channel (i.e. the bandwidth of the channel in each direction), is kept secret. Since balances are not announced, second-layer nodes probe routes iteratively, until they find a successful route to the destination for the amount required, if any. This feature makes the routing discovery protocol less efficient but preserves the privacy of channel balances. In this paper, we present an attack to disclose the balance of a channel in the Lightning Network. Our attack is based on performing multiple payments ensuring that none of them is finalized, minimizing the economical cost of the attack. We present experimental results that validate our claims, and countermeasures to handle the attack.

A generalized Feistel cipher is one of the methods to construct block ciphers, and it has several variants. Dong, Li, and Wang showed quantum distinguishing attacks against the $(2d-1)$-round Type-1 generalized Feistel cipher with quantum chosen-plaintext attacks, where $d\ge 3$, and they also showed key recovery attacks [Dong, Li, Wang. Sci China Inf Sci, 2019, 62(2): 022501].

In this paper, we show a polynomial time quantum distinguishing attack against the $(3d-3)$-round version, i.e., we improve the number of rounds by $(d-2)$. We also show a quantum distinguishing attack against the $(d^2-d+1)$-round version in the quantum chosen-ciphertext setting. We apply these quantum distinguishing attacks to obtain key recovery attacks against Type-1 generalized Feistel ciphers.

The need for structured and trusted common parameters is often cited as one of the major drawbacks of pairing-based SNARKs. Although multiparty computation techniques can be used to address this, the resulting parameters are circuit dependent and this costly process must be repeated for every circuit. Recent proposals to switch to a weaker updatable model for parameter generation are not yet sufficiently efficient. We propose a new model for updatability which generates the common reference string in two phases, each of them updatable: in the first phase, parameters are generated for a set of universal quadratic constraints and in the second phase specific circuit dependent parameters which impose some affine constraints can be derived from them non-interactively. We propose a concrete construction based on (but more efficient than) Pinocchio.

An additional contribution of the paper is to obtain a very efficient argument for verifiable computation using the same design principles which is based on weaker assumptions. The communication is approximately 4d group elements and verifying a proof requires computing around 4d pairings and O(n+d) exponentiations, where n is the input size and d the circuit depth. While the argument for the quadratic constraints is based on standard falsifiable assumptions, the argument for the linear constraints is based on a very ad-hoc assumption about certain properties of arguments of membership in linear spaces.

A decision graph is a well-studied classifier and has been used to solve many real-world problems. We assumed a typical scenario between two parties in this study, in which one holds a decision graph and the other wants to know the class label of his/her query without disclosing the graph and query to the other. We propose a novel protocol for this scenario that can obliviously evaluate a graph that is designed by an efficient data structure called the graph level order unary degree sequence (GLOUDS). The time and communication complexities of this protocol are linear to the number of nodes in the graph and do not include any exponential factors. The experiment results revealed that the actual runtime and communication size were well concordant with theoretical complexities. Our method can process a graph with approximately 500 nodes in only 11 s on a standard laptop computer. We also compared the runtime of our method with that of previous methods and confirmed that it was one order of magnitude faster than the previous methods.

Traceable ring signatures are a variant of ring signatures which allows the identity of a user to be revealed, when it signs two different messages with respect to the same group of users. It has applications in e-voting and in cryptocurrencies, such as the well-known Monero. We propose the first traceable ring signature scheme whose security is based on the hardness of the Syndrome Decoding problem, a problem in coding theory which is conjectured to be unsolvable by both classical and quantum algorithms. To construct the scheme, we use a variant of Stern's protocol and, by applying the Fiat-Shamir transform to it in an ingenious way, we obtain a ring signature that allows traceability. We prove that the resulting protocol has the standard security properties for traceable ring signatures in the random oracle model: tag-linkability, anonymity and exculpability. As far as we know, this is the first proposal for a traceable ring signature scheme in the post-quantum setting.

We introduce the concept of computationally independent pair of one-way functions (CI-OWF). We also provide two rich classes of examples of such functions based on standard assumptions. We revisit two-party interactive protocols for proving possession of computational power and existing two-flow challenge-response protocols. We analyze existing protocols for proof of computation power and propose a new two-flow protocol using CI-OWF based on square Diffie-Hellman problem.

In this paper, we present a high-speed constant time hardware implementation of NTRUEncrypt Short Vector Encryption Scheme (SVES), fully compliant with the IEEE 1363.1 Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. Our implementation follows an earlier proposed Post-Quantum Cryptography (PQC) Hardware Application Programming Interface (API), which facilitates its fair comparison with implementations of other PQC schemes. The paper contains the detailed flow and block diagrams, timing analysis, as well as results in terms of latency (in clock cycles), maximum clock frequency, and resource utilization in modern high-performance Field Programmable Gate Arrays (FPGAs). Our design takes full advantage of the ability to parallelize the major operation of NTRU, polynomial multiplication, in hardware. As a result, the execution time bottleneck shifts to the hash function, SHA-256, which is sequential in nature and as a result cannot be easily sped up in hardware. The obtained FPGA results for NTRU Encrypt SVES are compared with the equivalent results for Classic McEliece, a competing, well-established Post-Quantum Cryptography encryption scheme, with a long history of unsuccessful attempts at breaking. Our code for NTRUEncrypt SVES is being made open-source to speed-up further design-space exploration and benchmarking on multiple hardware platforms.

Elliptic curves based algorithms are nowadays widely spread among embedded systems. They indeed have the double advantage of providing efficient implementations with short certicates and of being relatively easy to secure against side-channel attacks. As a matter of fact, when an algorithm with constant execution flow is implemented together with randomization techniques, the obtained design usually thwarts classical side-channel attacks while keeping good performances. Recently, a new technique that makes randomization ineffective, has been successfully applied in the context of RSA implementations. This method, related to a so-called horizontal modus operandi, introduced by Walter in 2001, turns out to be very powerful since it only requires leakages on a single algorithm execution. In this paper, we combine such kind of techniques together with the collision correlation analysis, introduced at CHES 2010 by Moradi et al., to propose a new attack on elliptic curves atomic implementations (or unified formulas) with input randomization. We show how it may be applied against several state-of-the art implementations, including those of Chevallier-Mames et al., of Longa and of Giraud-Verneuil and also Bernstein and Lange for unied Edward's formulas. Finally, we provide simulation results for several sizes of elliptic curves on different hardware architectures. These results, which turn out to be the very rst horizontal attacks on elliptic curves, open new perspectives in securing such implementations. Indeed, this paper shows that two of the main existing countermeasures for elliptic curve implementations become irrelevant when going from vertical to horizontal analysis.

Many advanced lattice based cryptosystems require to sample lattice points from Gaussian distributions. One challenge for this task is that all current algorithms resort to floating-point arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for high-precision, lazy/backtracking techniques for efficiency, and may suffer from weak determinism which can completely break certain schemes.

In this paper, we give techniques to implement Gaussian sampling over general lattices without using FPA. To this end, we revisit the approach of Peikert, using perturbation sampling. Peikert's approach uses the Cholesky decomposition $\mathbb{\Sigma} = \mathbb{A} \mathbb{A}^t$ of the target covariance matrix $\mathbb{\Sigma}$, giving rise to a square matrix $\mathbb{A}$ with real (not integer) entries. Our idea, in a nutshell, is to replace this decomposition by an integral one. While there is in general no integer solution if we restrict $\mathbb{A}$ to being a square matrix, we show that such a decomposition can be efficiently found by allowing $\mathbb{A}$ to be wider (say $n \times 9n$). This can be viewed as an extension of Lagrange's four-square theorem to matrices. In addition, we adapt our integral decomposition algorithm to the ring setting: for power-of-2 cyclotomics, we can exploit the tower of rings structure for improved complexity and compactness.

Due to the public visible nature of blockchain, the seminal cryptocurrencies such as Bitcoin and Ethereum do not provide sufficient level of privacy, i.e., the addresses of sender and receiver and the transfer amount are all stored in plaintexts on blockchain. As the privacy concerns grow, several newly emerged cryptocurrencies such as Monero and ZCash provide strong privacy guarantees (including anonymity and confidentiality) by leveraging cryptographic technique.

Despite strong privacy is promising, it might be overkilled or even could be abused in some cases. In particular, anonymity seems contradict to accountability, which is a crucial property for scenarios requiring disputes resolving mechanism, e.g. e-commerce.

To address the above issues, we introduce accountability to blockchain-based confidential transaction system for the first time. We first formalize a general framework of confidential transaction system with accountability from digital signature, homomorphic public-key encryption and non-interactive zero-knowledge arguments, then present a surprisingly simple and efficient realization called PGC. To avoid using general-purpose zero-knowledge proofs (such as zk-SNARK and zk-STARK), we twist the ElGamal encryption as the underlying homomorphic PKE and develop ciphertext-refreshing approach. This not only enables us to prove transaction validity/correctness by using efficient Sigma protocols and zero-knowledge range proofs, but also makes PGC largely compatible with Bitcoin and Ethereum, which could be used as a drop-in to provide confidential enforcements with accountability.

Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty.

In this paper, we give more improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give new quantum polynomial-time distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\geq3$, which gain $d-2$ more rounds than the previous distinguishers. Hence, we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$. In qCCA setting, we get $(3d-3)$-round quantum distinguishers on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers.

In addition, we give some quantum attacks on CAST-256 block cipher. We find 12-round and 13-round polynomial-time quantum distinguishers in qCPA and qCCA settings, respectively, while the best previous one is only 7 rounds. Hence, we could derive quantum key-recovery attack on 19-round CAST-256. While the best previous quantum key-recovery attack is on 16 rounds. When comparing our quantum attacks with classical attacks, our result also reaches 16 rounds on CAST-256 with 128-bit key under a competitive complexity.

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both O(d log C) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.

For all vectorial boolean functions up to dimension 4, we present canonical representatives for all extended affine (EA) and CCZ equivalence classes. We also answer the following questions: How large are these classes? Which of these classes contain bijective functions? And how are these classes grouped into CCZ equivalence classes?

We put forth a new class of search problems, iterated search problems (ISP), and study their relation to the design of secure blockchain protocols. We prove that (i) any blockchain protocol implies a hard ISP problem, i.e., ISP hardness is necessary for secure blockchain protocols---but not sufficient by itself, and (ii) a suitably enhanced class of ISPs is sufficient to imply, via construction, a secure blockchain protocol in the common reference string (CRS) model. We then put forth a specific proposal for an enhanced ISP based on an underlying cryptographic hash function. The resulting blockchain protocol's security reduces to the ISP hardness of the hash-based scheme and to a randomness extraction property of the hash function. As a corollary, we obtain a blockchain protocol secure in the standard model under falsifiable assumptions; in contrast, all previous blockchain protocols were shown secure in the random oracle model.

The Faculty of Mathematics, Informatics and Mechanics at University of Warsaw (MIM UW) invites applications for positions of an assistant professor (“adiunkt” in Polish) in Computer Science, starting on 1st October 2019. The position is addressed to candidates working in computer systems, in particular operating systems, computer networks, web applications, security and cryptography

MIM UW is one of the strongest computer science faculties in Europe. It is known for talented students (e.g., two wins and 13 times in top ten at the ACM International Collegiate Programming Contest) and strong research teams, especially in theoretical aspects of computer science like algorithms, logic and automata, cryptography (e.g., 8 ERC grants in these fields, 4 of them running at the moment). For an overview of research areas represented in the Faculty, see http://www.mimuw.edu.pl/en/dziedziny-badan

Requirements:

- PhD degree in computer science or mathematics achieved during the last 10 years

- Strong publication record in international computer science journals or conferences

- Teaching experience

- Mobility record (participation in conferences, research visits, postdoc positions, etc.)

The position is for 4 years, with the possibility of extending for an indefinite period of time after a positive result of employee evaluation. The position comes with teaching load of 210 hrs/year.

Deadline for applications: 25th April 2019.

More details, including application procedure can be found under the following link:

https://www.mimuw.edu.pl/rozne/konkursy-pliki/2019/assistant-professor-comp-systems-2019-04-25.pdf

For more information about the procedure, requirements, conditions, etc. please contact a vice-director of Institute of Informatics, Lukasz Kowalik (kowalik (at) mimuw.edu.pl).

Closing date for applications: 25 April 2019

Contact: Lukasz Kowalik (kowalik (at) mimuw.edu.pl)

More information: https://www.mimuw.edu.pl/rozne/konkursy-pliki/2019/assistant-professor-comp-systems-2019-04-25.pdf

Full-time PhD EPSRC iCASE Studentship in collabration with UrbanChain

Project Description

Since the privatisation of the energy market in the UK, the inefficiency of its structures have resulted in unaffordable energy for micro consumers such as households and SMEs. Similar market structures distributed worldwide have also experienced the same issue. A few contributing factors leading to this issue are complicated switching process between suppliers, current high-cost technical infrastructure for administration and billing purposes and fixed rate supply system. With the use of blockchain as an infrastructure, there is a significant opportunity to disrupt the current energy market with automation and integration of services, provide savings in the energy provision process and reduce energy bills for end users. However, little scientific information is available regarding the costs associated with running a blockchain-based energy market and the best methods for scaling up such a platform.

eChain is a blockchain-based energy trading platform developed by UrbanChain, which uses hyperledger as a building block. The embedded features of the platform are real-time switching, automated billing and administration, P2P trading between energy generators and consumers, and demand side management.

Funding note

The candidate must be a UK/EU national as required by the funding agency.

Person Specification

Candidates must hold a minimum of an upper Second Class UK Honours degree or international equivalent in a relevant science or engineering discipline.

Skills and Qualifications

- A passion for blockchain technology, preferably concerning the energy sector

- Enthusiasm for working with cloud services and virtual machines

- Capable of producing highly original work and an enquiring mind with well-developed analytical and investigative skills

- A track record in software and/or electronic engineering, distributed ledger systems and/or system security

Closing date for applications: 15 April 2019

Contact: Candidates are encouraged to send their CV, a transcript with a list of courses and grades, and a description of their research interests to Dr Mustafa A. Mustafa as soon as possible for informal discussion about their suitability.

https://www.research.manchester.ac.uk/portal/mustafa.mustafa.html

More information: http://www.cs.manchester.ac.uk/study/postgraduate-research/projects/description/?projectid=20154

Event date: 1 October to 4 October 2019
Submission deadline: 31 May 2019
Notification: 5 July 2019

The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Today we are pleased to announce six members that have been elevated to the rank of Fellow for 2019:

• Jonathan Katz, for broad contributions, especially in public-key encryption and cryptographic protocols, and for dedication to service and education.
• Kaoru Kurosawa, for seminal contributions spanning anonymity, e-voting, and public-key cryptography, and for service to the Japanese and international communities.
• Daniele Micciancio, for pioneering work on lattice-based cryptography and the complexity of lattice problems, and for service to the IACR.
• Vincent Rijmen, for co-designing AES, contributions to the design and cryptanalysis of symmetric primitives, and service to the IACR.
• Amit Sahai, for fundamental contributions, including to secure computation, zero knowledge, and functional encryption, and for service to the IACR.
• Xiaoyun Wang, for essential contributions to the cryptanalysis and design of hash functions, and for service to the IACR.

Congratulations to the new fellows! More information about the IACR Fellows Program can be found at https://iacr.org/fellows/.

The theoretical cryptography group at Ruhr University Bochum is looking for an outstanding and highly motivated PhD student (m/f/d) in the area of theoretical cryptography. The group offers an excellent working environment as a part of theHorst Görtz Institute for IT Security (HGI hgi.rub.de/en/home/ ) including more than 200 scientists active in all areas of IT security and cryptography. We are looking for candidates (m/f/d) with a Masters or equivalent degree with outstanding grades in computer science, mathematics or related fields.

We offer a three-year position with salary according to the remuneration group E 12/13 TV-L (39,83 Wochenstunden). The position is based in Bochum, Germany and will involve international travel to conduct and present research.

The load of teaching will be calculated according to §3 of Lehrverpflichtungsverordnung (state of North Rhine-Westphalia).

If you are interested, send your complete application documents in one single pdf file (max. 10 MB) with subject line *Application for PhD* directly to Nils Fleischhacker. ( nils.fleischhacker (at) rub.de )

Required documents are:

1. Letter of motivation
2. Curriculum vitae (including a list of publications if appropriate)
3. Master\'s certificate and transcript of records

At Ruhr-Universität Bochum, we wish to promote careers of women in areas in which they have been underrepresented, and we would therefore like to encourage female candidates to send us their applications. Applications by suitable candidates with severe disabilities and other applicants with equal legal status are likewise most welcome.

Closing date for applications: 14 April 2019

Contact: Nils Fleischhacker, nils.fleischhacker (at) rub.de

More information: https://goo.gl/FSxDbC

Isogeny-based cryptography offers one of the most promising approach for post-quantum cryptography and achieves forward secrecy in communications, a highly desirable feature currently available in TLS protocol suite. Protocols based on isogeny problems enjoy very small public keys compared to all other post-quantum candidates, a very useful feature since those keys are routinely transmitted as part of public key certificates. While all these properties make isogeny-based cryptography very appealing, it is also a relatively new field. As a result, it is less mature than other post-quantum candidates, and arguably not ready yet to meet the requirements of real-life security applications. In particular, there is very little work on hardware implementations of isogeny-based protocols.

The main goal of this studentship is to develop optimized, side-channel protected hardware implementations of isogeny-based protocols.

The student will be integrated within the University of Birmingham’s Centre for Cyber Security and Privacy and they will collaborate with more experienced researchers on this research program. They will be supervised by Dr. Sujoy Sinha Roy, Dr. Christophe Petit and Dr. Flavio Garcia. All three are members of Birmingham’s Academic Center of Excellence in Cyber security.

Person specification:

2:1 Honours undergraduate degree and/or postgraduate degree with Distinction (or an international equivalent) in Electrical and Electronics Engineering, Computer Science, Mathematical Engineering or closely related discipline. The ideal candidate for this position will be familiar with low-level programming, hardware architecture design and cryptography, but other candidates with a strong academic record will also be considered.

Funding Notes: The candidate must be a UK national as required by the funding agency.

Total stipend to student: £22,000 (year1), £22,500 (year2), £23,000 (year3), £11,750 (6 months of year4). The stipend is tax free. This is a research position with limited or no teaching requirements.

Application link: https://sits.bham.ac.uk/lpages/EPS003.htm

Closing date for applications: 15 May 2019

Contact: Candidates are encouraged to send their CV, a transcript with a list of courses and grades, and a description of their research interests to Sujoy Sinha Roy and Christophe Petit and Flavio Garcia as soon as possible for informal discussion about their suitability.

https://www.cs.bham.ac.uk/~sinharos/

https://www.cs.bham.ac.uk/~petitcz/

http://www.cs.bham.ac.uk/~garciaf/