IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
25 February 2019
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai
Our new type of proof system is motivated by applications in which the input statement is not fully available to any single verifier, but can still be efficiently accessed via linear queries. This situation arises in scenarios where the input is partitioned or secret-shared between two or more parties, or alternatively is encoded using an additively homomorphic encryption or commitment scheme. This setting appears in the context of secure messaging platforms, verifiable outsourced computation, PIR writing, private computation of aggregate statistics, and secure multiparty computation (MPC). In all these applications, there is a need for fully linear proof systems with short proofs.
While several efficient constructions of fully linear proof systems are implicit in the interactive proofs literature, many questions about their complexity are open. We present several new constructions of fully linear zero-knowledge proof systems with sublinear proof size for "simple" or "structured" languages. For example, in the non-interactive setting of fully linear PCPs, we show how to prove that an input vector $x\in\mathbb{F}^n$ satisfies a single degree-2 equation with a proof of size $O(\sqrt n)$ and $O(\sqrt n)$ linear queries, which we show to be optimal. More generally, for languages that can be recognized by systems of constant-degree equations, we can reduce the proof size to $O(\log n)$ at the cost of $O(\log n)$ rounds of interaction.
We use our new proof systems to construct new short zero-knowledge proofs on distributed and secret-shared data. These proofs can be used to improve the performance of many of the example systems mentioned above.
Finally, we observe that zero-knowledge proofs on distributed data provide a general-purpose tool for protecting protocols for secure multiparty computation (MPC) against malicious parties. Applying our short fully linear PCPs to "natural" MPC protocols in the honest-majority setting, we can achieve unconditional protection against malicious parties with sublinear additive communication cost. We use this to improve the communication complexity of recent honest-majority MPC protocols. For instance, using any pseudorandom generator, we obtain a 3-party protocol for Boolean circuits in which the amortized communication cost is only one bit per AND gate per party (compared to 10 bits in the best previous protocol), matching the best known protocols for semi-honest adversaries.
Antoine Joux
In terms of performance, our test implementation of the proposed scheme is slower than the current speed records but remains within a comparable range. We hope that the detailed study of our simplified scheme by the community can make it competitive and provide new insights into FHE constructions at large.
Jiangshan Yu, Man Ho Allen Au, Paulo Esteves-Verissimo
Unlike previous cascade effect attacks (ESORICS 17 and PETS 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call The Sun-Tzu Survival Problem, to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P−complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.
Ralph Ankele, Christoph Dobraunig, Jian Guo, Eran Lambooij, Gregor Leander, Yosuke Todo
William Diehl, Farnoud Farahmand, Abubakr Abdulgadir, Jens-Peter Kaps, Kris Gaj
Katherine E. Stange
Prasanna Ravi, Sourav Sen Gupta, Anupam Chattopadhyay, Mustafa Khairallah, Zakaria Najm, Shivam Bhasin
Jesper Buus Nielsen, Mark Simkin
In this work, we study leakage-resilient secret sharing schemes with information-theoretic security and prove a lower bound on the share size and the required amount randomness of any such scheme. We prove that for any leakage-resilient secret sharing scheme either the amount of randomness across all shares or the share size has to be linear in $n$. More concretely, for a secret sharing scheme with $p$-bit long shares, $\ell$-bit leakage per share, where $\widehat{t}$ shares uniquely define the remaining $n - \widehat{t}$ shares, it has to hold that $$ p \ge \frac{\ell (n - t)}{\widehat{t}}\ . $$
We use our lower bound to gain further insights into a question that was recently posed by Benhamouda et al. (CRYPTO'18), who ask to what extend existing regular secret sharing schemes already provide protection against leakage. The authors proved that Shamir's secret sharing is leakage-resilient for very large thresholds $t = n - \mathcal{O}(\log n)$ and conjectured that it is also $1$-bit leakage-resilient for any threshold that is a constant fraction of the total number of shares. We do not disprove their conjecture, but show that two mild and natural strengthenings thereof are false, thus concluding that their conjecture is essentially the best one could hope for.
The results described above only apply to secret sharing schemes with information-theoretic security, since the lower bound proof relies on an adversary that can enumerate all possible secret sharings and thus runs in time exponential in at least the share size $p$ and the full reconstruction threshold $\widehat{t}$. In addition, we present a conceptually simple and highly efficient attack for the specific case of $2$-out-of-$n$ Shamir secret sharing that only requires $1$ bit of leakage, has a running time of $\bigO{n}$ field operations, and could easily be run in practice by a computationally bounded adversary.
David Wong
Yue Guo, Rafael Pass, Elaine Shi
Rohit Sinha, Sivanarayana Gaddam, Ranjit Kumaresan
Recently, trusted execution environments (TEEs), such as Intel SGX and Sanctum enclaves, are finding applications in outsourced computing on sensitive data. However, since TEEs are at the mercy of an untrusted host for storage and network communication, they are incapable of enforcing history-dependent policies or fairness. For instance, against a user's wish that only an aggregate function over her entire data is revealed, an adversarial host can repeatedly evaluate that aggregate function on different subsets of her dataset, and learn the individual records. The adversary may also collude and deliver the output only to a subset of the output recipients, thus violating fairness.
This paper presents LucidiTEE, the first system to enable multiple parties to jointly compute on large-scale private data, while guaranteeing that the aforementioned policies are enforced even when the input providers are offline, and guaranteeing fairness to all output recipients. To that end, LucidiTEE develops a set of novel protocols between a network of TEEs and a distributed, shared, append-only ledger. LucidiTEE uses the ledger only to enforce policies; it does not store inputs, outputs, or state on the ledger, nor does it duplicate execution amongst the participants, which allows it to scale to large data and large number of parties.
We demonstrate several policy-based applications including personal finance, federated machine learning, fair $n$-party information exchange, and private set intersection for medical records.
E.V. Flynn, Yan Bo Ti
Nicholas Genise, Craig Gentry, Shai Halevi, Baiyu Li, Daniele Micciancio
Satrajit Ghosh, Mark Simkin
Prior to this work, all previous protocols had a communication complexity of $\Omega(n)$. Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter $t$ and only logarithmically on the set size $n$.
Kasper Green Larsen, Mark Simkin
Vanesa Daza, Alonso González, Zaira Pindado, Carla Ràfols, Javier Silva
Danping Shi, Siwei Sun, Yu Sasaki, Chaoyun Li, Lei Hu
We apply this method to analyze the linear trails of MORUS (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of MORUS-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of MORUS-like key-stream generators. As a result, a set of trails with correlation $2^{-38}$ is identified for all versions of full MORUS, while the correlations of previously published best trails for MORUS-640 and MORUS-1280 are $2^{-73}$ and $2^{-76}$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on MORUS-1280-256 from $2^{152}$ to $2^{76}$. These new trails also lead to the first distinguishing and message-recovery attacks on MORUS-640-128 and MORUS-1280-128 with surprisingly low complexities around $2^{76}$.
Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.
23 February 2019
Hyderabad, INDIA, 16 December - 20 December 2019
Submission deadline: 12 July 2019
Notification: 25 September 2019
Fuhou, China, 25 October - 27 October 2019
Submission deadline: 6 May 2019
Notification: 8 July 2019
21 February 2019
Department of Engineering at Aarhus University, Denmark
Title: Verifiable cryptographic software
Zero-knowledge proofs are integral for deploying privacy-preserving cryptocurrencies and other blockchain applications, as they represent a fundamental building block for proving statements about confidential data. The most popular framework for such proofs is based on cryptographic pairings defined over elliptic curves, where pairing-based zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) underlie private transactions.
The PhD candidate will investigate techniques to develop a formally verified efficient software library for pairing-based cryptography, as means to support current blockchain projects relying on zero-knowledge proofs. The PhD candidate will also be involved in other educational activities, such as serving as teaching assistant in courses related to his/her expertise.
The project is a collaboration between researchers from the Departments of Engineering and Computer Science; the DIGIT Centre for Digitalisation, Big Data and Data Analytics; and the recently opened Concordium Blockchain Research Center.
Qualifications:
We are looking for dedicated and enthusiastic applicants, preferably with a Master’s degree in Computer Science/Engineering, Mathematics or related discipline. A theoretical background with cryptography or formal verification will be important for the project. Practical experience with software development and the Coq proof assistant will be seen as a plus. Analytical and critical thinking are naturally essential to pursuing a PhD degree. Further requirements are fluency in English, good reporting/organization skills and being able to work independently.
Closing date for applications: 1 May 2019
Contact: Diego F. Aranha, Assistant Professor, dfaranha (at) eng.au.dk; or Bas Spitters, Associate Professor, spitters (at) cs.au.dk
More information: https://phd.scitech.au.dk/for-applicants/apply-here/may-2019/verifiable-cryptographic-software/