International Association
for Cryptologic Research

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism; an indispensable feature for practical cryptographic schemes. Due to this extra feature, RIBE is often required to satisfy a strong security notion unique to the revocation setting called decryption key exposure resistance (DKER). Additionally, hierarchal IBE (HIBE) is another orthogonal extension of IBE that supports key delegation functionalities allowing for scalable deployments of cryptographic schemes. Thus far, R(H)IBE constructions with DKER are only known from bilinear maps, where all constructions rely heavily on the so-called key re-randomization property to achieve the DKER and/or hierarchal feature. Since lattice-based schemes seem to be inherently ill-fit with the key re-randomization property, we currently do not know of any lattice-based R(H)IBE schemes with DKER.

In this paper, we propose the first lattice-based RHIBE scheme with DKER without relying on the key re-randomization property, departing from all the previously known methods. We start our work by providing a generic construction of RIBE schemes with DKER, which uses as building blocks any two-level standard HIBE scheme and (weak) RIBE scheme without DKER. Based on previous lattice-based RIBE constructions, our result implies the first lattice-based RIBE scheme with DKER. Then, building on top of our generic construction, we construct the first lattice-based RHIBE scheme with DKER, by further exploiting the algebraic structure of lattices. To this end, we prepare a new tool called the level conversion keys, which allows us to achieve the hierarchal feature without relying on the key re-randomization property.

We continue the study of Homomorphic Secret Sharing (HSS), recently introduced by Boyle et al. (Crypto 2016, Eurocrypt 2017). A (2-party) HSS scheme splits an input x into shares (x0, x1) such that (1) each share computationally hides x, and (2) there exists an efficient homomorphic evaluation algorithm Eval such that for any function (or “program”) P from a given class it holds that Eval(x0,P)+Eval(x1,P) = P(x). Boyle et al. show how to construct an HSS scheme for branching programs, with an inverse polynomial error, using discrete-log type assumptions such as DDH.

We make two types of contributions.

Optimizations. We introduce new optimizations that speed up the previous optimized implementation of Boyle et al. by more than a factor of 30, significantly reduce the share size, and reduce the rate of leakage induced by selective failure.

Applications. Our optimizations are motivated by the observation that there are natural application scenarios in which HSS is useful even when applied to simple computations on short inputs. We demonstrate the practical feasibility of our HSS implementation in the context of such applications.

Software side channel attacks have become a serious concern with the recent rash of attacks on speculative processor architectures. Most attacks that have been demonstrated exploit the cache tag state as their exfiltration channel. While many existing defense mechanisms that can be implemented solely in software have been proposed, these mechanisms appear to patch specific attacks, and can be circumvented. In this paper, we propose minimal modifications to hardware to defend against a broad class of attacks, including those based on speculation, with the goal of eliminating the entire attack surface associated with the cache state covert channel.

We propose DAWG, Dynamically Allocated Way Guard, a generic mechanism for secure way partitioning of set associative structures including memory caches. DAWG endows a set associative structure with a notion of protection domains to provide strong isolation. When applied to a cache, unlike existing quality of service mechanisms such as Intel's Cache Allocation Technology (CAT), DAWG isolates hits and metadata updates across protection domains. We describe how DAWG can be implemented on a processor with minimal modifications to modern operating systems. We argue a non-interference property that is orthogonal to speculative execution and therefore argue that existing attacks such as Spectre Variant 1 and 2 will not work on a system equipped with DAWG. Finally, we evaluate the performance impact of DAWG on the cache subsystem.

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