International Association
for Cryptologic Research

A multisignature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of two highly efficient Schnorr-based multisignature schemes designed to scale up to thousands of signers, namely CoSi by Syta et al. (S&P 2016) and MuSig by Maxwell et al. (ePrint 2018). The MuSig scheme was presented with a proof under the one-more discrete-logarithm assumption, while the provable security of CoSi has so far remained an open question. In this work, we prove that CoSi and MuSig cannot be proved secure without radically departing from currently known techniques (and point out a flaw in the proof of MuSig). We then present DG-CoSi, a double-generator variant of CoSi based on the Okamoto (multi)signature scheme, and prove it secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that the second generator in DG-CoSi barely affects scalability compared to CoSi, allowing 8192 signers to collaboratively sign a message in under 1.5 seconds, making it a highly practical and provably secure alternative for large-scale deployments.

Cryptocurrencies have popularized public ledgers, known colloquially as "blockchains". While the Bitcoin blockchain is relatively simple to reason about as, effectively, a hash chain, more complex public ledgers are largely designed without any formalization of desired cryptographic properties such as authentication or integrity. These designs are then implemented without assurances against real-world bugs leading to little assurance with regards to practical, real-world security.

Ledger Design Language (LDL) is a modeling language for describing public ledgers. The LDL compiler produces two outputs. The first output is a an applied-pi calculus symbolic model representing the public ledger as a protocol. Using ProVerif, the protocol can be played against an active attacker, whereupon we can query for block integrity, authenticity and other properties. The second output is a formally verified read/write API for interacting with the public ledger in the real world, written in the F* programming language. F* features such as dependent types allow us to validate a block on the public ledger, for example, by type-checking it so that its signing public key be a point on a curve. Using LDL's outputs, public ledger designers obtain automated assurances on the theoretical coherence and the real-world security of their designs with a single framework based on a single modeling language.

The term near or weak blocks describes Bitcoin blocks whose PoW does not meet the required target difficulty to be considered valid under the regular consensus rules of the protocol. Near blocks are generally associated with protocol improvement proposals striving towards shorter transaction confirmation times. Existing proposals assume miners will act rationally based solely on intrinsic incentives arising from the adoption of these changes, such as earlier detection of blockchain forks.

In this paper we present Flux, a protocol extension for proof-of-work blockchains that leverages on near blocks, a new block reward distribution mechanism, and an improved branch selection policy to incentivize honest participation of miners. Our protocol reduces mining variance, improves the responsiveness of the underlying blockchain in terms of transaction processing, and can be deployed without conflicting modifications to the underlying base protocol as a velvet fork. We perform an initial analysis of selfish mining which suggests Flux not only provides security guarantees similar to pure Nakamoto consensus, but potentially renders selfish mining strategies less profitable.

Aggregate signature allows non-interactively condensing multiple individual signatures into a compact one. Besides the faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency. For example, aggregate signature can mitigate some bottlenecks emerged with the Bitcoin systems (and actually almost all blockchain-based systems): low throughput, capacity, scalability, high transaction fee, etc. Unfortunately, achieving aggregate signature from general elliptic curve group (without bilinear maps) is a long-standing open question. Recently, there is also renewed interest in deploying Schnorr's signature in Bitcoin, for its efficiency and flexibility. In this work, we investigate the applicability of the Gamma-signature scheme proposed by Yao and Zhao. Akin to Schnorr's, Gamma-signature is generated with linear combination of ephemeral secret-key and static secret-key, and enjoys almost all the advantages of Schnorr's signature. Besides, Gamma-signature has salient features in online/offline performance, stronger provable security, and deployment flexibility with interactive protocols like IKE. In this work, we identify one more key advantage of Gamma-signature in signature aggregation, which is particularly crucial for applications to blockchain and cryptocurrency. Specifically, we first observe the incapability of Schnorr's for aggregating signatures in the Bitcoin system. This is demonstrated by concrete attacks. Then, we show that aggregate signature can be derived from the Gamma-signature scheme. To the best of our knowledge, this is the first aggregate signature scheme from general groups without bilinear maps. The security of aggregate Gamma-signature is proved based on a new assumption proposed and justified in this work, referred to as non-malleable discrete-logarithm (NMDL), which might be of independent interest and could find more cryptographic applications in the future. When applying the resultant aggregate Gamma-signature to Bitcoin, the storage volume of signatures reduces about 50%, and the signature verification time can even reduce about 80%. Finally, we specify in detail the implementation of aggregate Gamma-signature in Bitcoin, with minimal modifications that are in turn more friendly to segregated witness (SegWit) and provide better protection against transaction malleability attacks.

Secure authentication and authorization within Facebook’s infrastructure play important roles in protecting people using Facebook’s services. Enforcing security while maintaining a flexible and performant infrastructure can be challenging at Facebook’s scale, especially in the presence of varying layers of trust among our servers. Providing authentication and encryption on a per-connection basis is certainly necessary, but also insufficient for securing more complex flows involving multiple services or intermediaries at lower levels of trust.

To handle these more complicated scenarios, we have developed two token-based mechanisms for authentication. The first type is based on certificates and allows for flexible verification due to its public-key nature. The second type, known as “crypto auth tokens”, is symmetric-key based, and hence more restrictive, but also much more scalable to a high volume of requests. Crypto auth tokens rely on pseudorandom functions to generate independently-distributed keys for distinct identities.

Finally, we provide (mock) examples which illustrate how both of our token primitives can be used to authenticate real-world flows within our infrastructure, and how a token-based approach to authentication can be used to handle security more broadly in other infrastructures which have strict performance requirements and where relying on TLS alone is not enough.

Decentralized cryptocurrencies based on blockchains provide attractive features, including user privacy and system transparency, but lack active control of money supply and capabilities for regulatory oversight, both existing features of modern monetary systems. These limitations are critical, especially if the cryptocurrency is to replace, or complement, existing fiat currencies. Centralized cryptocurrencies, on the other hand, provide controlled supply of money, but lack transparency and transferability. Finally, they provide only limited privacy guarantees, as they do not offer recipient anonymity or payment value secrecy.

We propose a novel digital currency, called PRCash, where the control of money supply is centralized, money is represented as value-hiding transactions for transferability and improved privacy, and transactions are verified in a distributed manner and published to a public ledger for verifiability and transparency. Strong privacy and regulation are seemingly conflicting features, but we overcome this technical problem with a new regulation mechanism based on zero-knowledge proofs. Our implementation and evaluation shows that payments are fast and large-scale deployments practical. PRCash is the first digital currency to provide control of money supply, transparency, regulation, and privacy at the same time, and thus make its adoption as a fiat currency feasible.

In the context of Fully Homomorphic Encryption, which allows computations on encrypted data, Machine Learning has been one of the most popular applications in the recent past. All of these works, however, have focused on supervised learning, where there is a labeled training set that is used to configure the model. In this work, we take the first step into the realm of unsupervised learning, which is an important area in Machine Learning and has many real-world applications, by addressing the clustering problem. To this end, we show how to implement the K-Means-Algorithm. This algorithm poses several challenges in the FHE context, including a division, which we tackle by using a natural encoding that allows division and may be of independent interest. While this theoretically solves the problem, performance in practice is not optimal, so we then propose some changes to the clustering algorithm to make it executable under more conventional encodings. We show that our new algorithm achieves a clustering accuracy comparable to the original K-Means-Algorithm, but has less than $5\%$ of its runtime.

Clauser-Horne-Shimony-Holt inequality, an extension of Bell's inequality, is of great importance to modern quantum computation and quantum cryptography. So far, all experimental demonstrations of entanglement are designed to check Bell's inequality or Clauser-Horne-Shimony-Holt inequality. In this note, we specify the math assumptions needed in the argument for Clauser-Horne-Shimony-Holt inequality. We then show the math argument for this inequality is totally indispensable of any physical interpretation, including the hidden variable interperation for EPR thought experiment and the Copenhagen interpretation for quantum mechanics.

We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit $f$ into a small digest. Bob can encrypt some data $x$ under this digest in a way that enables Alice to recover $f(x)$ without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of $f$. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties:

* We construct a 2-round 2PC protocol between Alice and Bob with respective inputs $x_A,x_B$ in which Alice learns the output $f(x_A,x_B)$ in the second round. This is the first such protocol which is "Bob-optimized", meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit $f$ or even Alice's input $x_A$. In contrast, prior solutions based on fully homomorphic encryption are "Alice-optimized".

* We construct an MPC protocol, which allows $N$ parties to securely evaluate a function $f(x_1,...,x_N)$ over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit $f$ before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.

In this paper, we propose cryptanalyses of all existing indistinguishability obfuscation (iO) candidates based on branching programs (BP) over GGH13 multilinear map. To achieve this, we introduce two novel techniques, program converting and matrix zeroizing, which can be applied to a wide range of obfuscation structures and BPs. We then prove that the existing general-purpose BP obfuscations over GGH13 multilinear map with the current parameters cannot achieve indistinguishability. More precisely, the recent BP obfuscation suggested by Garg et al. which is still secure against all known attack, and the rst candidate indistinguishability obfuscation with input-unpartitionable branching programs is not secure against our attack. Previously, there has been no known probabilistic polynomial time attack for these two cases.

Proof of Work (PoW), a fundamental blockchain protocol, has been widely applied and thoroughly testified in various decentralized cryptocurrencies, due to its intriguing merits including trustworthy sustainability, robustness against sybil attack, delicate incentive-compatibility, and openness to any participant. Meanwhile, PoW-powered blockchains still suffer from poor efficiency, potential selfish mining, to-be-optimized fairness and extreme inconvenience of protocol upgrading. Therefore, it is of great interest to design new PoW-based blockchain protocol to address or relieve the above issues so as to make it more applicable and feasible.

To do so, firstly we take advantage of the basic framework (i.e., two-layer chain structure) adopted in Bitcoin-NG which was introduced by Eyal et al. to extend the throughput of Bitcoin-derived blockchains significantly via blocks of a two-layer structure, inheriting the high throughput merit while ridding off the vulnerability to the attack of microblock swamping in Bitcoin-NG as well as attaining a better fairness property, by presenting two-level mining mechanism and incorporating this mechanism into the two-layer chain structure. Furthermore, to tackle the selfish mining issue, strengthen the robustness against the "51%" attack of PoW miners, and offer the flexibility for future protocol updating effectively, we borrow the idea of ticket-voting mechanism from DASH and Decred, and combine it with our improved structure elaborately to build a novel efficient, robust and flexible blockchain protocol (named Goshawk). Last but not the least, this scheme has been implemented and deployed in the testnet of the public blockchain project Hcash for months, and has demonstrated its stability and high efficiency with such real-world test.

Cryptographic security is built on two ingredients: a sufficiently large key space, and sufficiently complex processing algorithm. Driven by historic inertia we use fixed size small keys, and dial up the complexity metric in our algorithms. It's time to examine this trend. Effective cryptographic complexity is difficult to achieve, more difficult to verify, and it keeps the responsibility for security in the hands of a few cipher implementers and fewer cipher designers. By contrast, adding more key bits over simple-to-analyze mathematics may guarantee a security advantage per increased key size. What is more revolutionary is the fact that the decision how much randomness to deploy may be relegated to the owner of the protected data, (the cipher user) which is where it should reside. Such shift of security responsibility will deny government the ability to violate its citizens privacy on a wholesale basis. In order to catch on, we need a new class of ciphers. We point to several published options, and invite a community debate on this strategic proposition.

In modern as well as ancient ciphers of public key cryptography, substitution boxes find a permanent seat. Generation and cryptanalysis of 4-bit as well as 8-bit crypto S-boxes is of utmost importance in modern cryptography. In this paper, a detailed review of cryptographic properties of S-boxes has been illustrated. The generation of crypto S-boxes with 4-bit as well as 8-bit Boolean functions (BFs) and Polynomials over Galois field GF(p^q) has also been of keen interest of this paper. The detailed analysis and comparison of generated 4-bit and 8-bit S-boxes with 4-bit as well as 8-bit S-boxes of Data Encryption Standard (DES) and Advance Encryption Standard (AES) respectively, has incorporated with example. Detailed analysis of generated S-boxes claims a better result than DES and AES in view of security of crypto S-boxes.

We give a language-based security treatment of domain-specific languages and compilers for secure multi-party computation, a cryptographic paradigm that enables collaborative computation over encrypted data. Computations are specified in a core imperative language, as if they were intended to be executed by a trusted-third party, and formally verified against an information-flow policy modelling (an upper bound to) their leakage. This allows non-experts to assess the impact of performance-driven authorized disclosure of intermediate values.

Specifications are then compiled into multi-party protocols. We formalize protocol security using (distributed) probabilistic information-flow and prove that compilation is security-preserving: protocols do not leak more than allowed by the source policy. The proof exploits a natural but previously missing correspondence between simulation-based cryptographic proofs and (composable) probabilistic non-interference.

Finally, we extend our framework to justify leakage cancelling, a domain-specific optimization that allows to, first, write an efficiently computable specification that fails to meet the allowed leakage upper-bound, and then apply a probabilistic pre-processing that brings the overall leakage to within the acceptable range.

Machine learning is widely used to produce models for a range of applications and is increasingly offered as a service by major technology companies. However, the required massive data collection raises privacy concerns during both training and prediction stages.

In this paper, we design and implement a general framework for privacy-preserving machine learning and use it to obtain new solutions for training linear regression, logistic regression and neural network models. Our protocols are in a three-server model wherein data owners secret share their data among three servers who train and evaluate models on the joint data using three-party computation (3PC).

Our main contribution is a new and complete framework ($ABY^3$) for efficiently switching back and forth between arithmetic, binary, and Yao 3PC which is of independent interest. Many of the conversions are based on new techniques that are designed and optimized for the first time in this paper. We also propose new techniques for fixed-point multiplication of shared decimal values that extends beyond the three-party case, and customized protocols for evaluating piecewise polynomial functions. We design variants of each building block that is secure against malicious adversaries who deviates arbitrarily.

We implement our system in C++. Our protocols are up to four orders of magnitude faster than the best prior work, hence significantly reducing the gap between privacy-preserving and plaintext training.

Event date: 23 July to 27 July 2018

The Research Group at Nanyang Technological University (NTU), Singapore, led by Prof. Anupam Chattopadhyay is seeking skilled and motivated candidates for the position of Post-Doctoral Research Fellows to participate in multiple ongoing projects focusing on system/architecture/hardware security. The research team is currently funded by several large and strategic research grants in the aforementioned areas. Salaries are highly competitive and are decided according to the successful applicants’ accomplishments, experience and qualifications. Interested applicants are encouraged send their detailed CV, cover letter and two letters of references to Prof. Anupam Chattopadhyay (anupam at ntu.edu.sg).

We are soliciting candidates to have an introductory knowledge in cryptography and strong background in digital/system design, including relevant experience in managing large-scale programming projects in C/C++/VHDL/Verilog. Candidates with prior industrial experience and familiarity with state-of-the-art tools in these domains are preferred.

Review of applications starts immediately and will continue until positions are filled.

Closing date for applications: 31 December 2018

Contact: Asst. Prof. Anupam Chattopadhyay, Nanyang Technological University (Singapore), anupam at ntu.edu.sg

NuCypher is a data privacy layer for blockchain, decentralized applications, and other distributed systems. We\'re back by Y Combinator, Polychain Capital, and many other leading investors.

We\'re looking for a scientist with expertise in fully homomorphic encryption (FHE) to assist with our research efforts on performance improvements and potential applications for smart contracts. Familiarity with related technologies like proxy re-encryption (PRE) and multi-party computation (MPC) is helpful.

Ideally, candidates have an understanding of the surrounding issues and problems and have an interest in identifying potential solutions. Due to the unproven and highly theoretical nature of these schemes, candidates should be willing to pivot research when practical solutions cannot be found. Qualified candidates are likely (but not required) to have a PhD or similarly extensive experience in cryptography.

Closing date for applications: 31 December 2018

Contact: Please email founders (at) nucypher.com with your CV and any previous research/publications you\'re able to share.

More information: http://www.nucypher.com/

Simula@UiB (simula-uib.com) has a three-year PhD position available in the field of cryptography. The position is associated with the project “qsIoT: Quantum safe cryptography for the Internet of Things”, awarded by the Research Council of Norway.

Closing date for applications: 15 June 2018

Contact: Professor Øyvind Ytrehus, Simula@UiB

Email: oyvindy (at) simula.no

More information: https://www.simula.no/about/job/call-phd-student-cryptography-simulauib

Each researcher will work on a separate project in one of the following three related areas. It is expected that all researchers will collaborate and meet together regularly as a team. The project is a collaboration between members of the NTNU Applied Cryptology Laboratory.

• Post-quantum primitives. Post-quantum public-key primitives are the main focus of the ongoing NIST standardization process that officially started on 30 November 2017. Initially 69 proposed schemes were proposed in three main categories: encryption schemes, key encapsulation mechanisms, and digital signatures. Those, and possibly new primitives, are the subject of the research for this position.

• Post-quantum ecosystem. Current public key cryptosystems have a large associated ecosystem of auxiliary protocols and tools, such as proofs of knowledge, proofs of relations, verifiable decryption, and shuffles of ciphertexts. This ecosystem is sparse for most post-quantum schemes. Our group has already begun working on new tools, such as shuffles and verifiable decryption, mostly for lattice-based cryptosystem. We intend to continue this line of research, with a focus on lattice-based cryptography, but we will also work on code-based and multivariate cryptography.

• Post-quantum key exchange. This project will focus on how to achieve efficient quantum-secure key exchange which can achieve some useful key exchange properties, such as: forward secrecy, key compromise impersonation, deniability, anonymity, contributiveness, and key control. Strong models of security, such as those accounting for ephemeral key leakage and side channels, and different settings, such as password-based key exchange and group key exchange, will also be investigated.

  Closing date for applications: 1 June 2018

  Contact: Professor Kristian Gjøsteen (kristian.gjosteen (at) ntnu.no), or Professor Colin Boyd (colin.boyd (at) ntnu.no), or Professor Danilo Gligoroski (danilo.gligoroski (at) ntnu.no)

  More information: https://www.jobbnorge.no/en/available-jobs/job/152421/