IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
14 September 2021
Yu Dai, Zijian Zhou, Fangguo Zhang, Chang-An Zhao
Marc Joye
Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin, Nurul Nur Hanisah Adenan, Nur Azman Abu
Mike Rosulek, Ni Trieu
For small sets (500 items or fewer), our protocol requires the least time and communication of any known PSI protocol, even ones that are only semi-honest secure and ones that are not based on Diffie-Hellman. It is one of the few significant improvements to the 20-year old classical Diffie-Hellman PSI protocol of Huberman, Franklin, and Hogg (ACM Elec. Commerce 1999).
Our protocol is actually a generic transformation that constructs PSI from a class of key agreement protocols. This transformation is inspired by a technique of Cho, Dachman-Soled, and Jarecki (CT-RSA 2016), which we streamline and optimize in several important ways to achieve our superior efficiency.
Joël Alwen, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak, Michael Walter
A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users' secret keys while the root is the shared group key. For a group of size $N$, each user just holds $\log(N)$ keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting $2\log(N)$ ciphertexts (encrypting each fresh key on the path under the keys of its parents).
In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group.
We show that in an asymptotic setting (where the number $m$ of groups is fixed while the number $N$ of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution.
As our asymptotic ``solution" converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a ``lattice graph", which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code.
To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.
Sacha Servan-Schreiber, Simon Langowski, Srinivas Devadas
Existing protocols for private nearest neighbor search re- quire heavy cryptographic tools, resulting in poor practical performance or large client overheads. In this paper, we present the first lightweight protocol for private nearest neighbor search. Our protocol is instantiated using two non-colluding servers, each holding a replica of the database. The protocol supports an arbitrary number of clients simultaneously querying the database via these servers. Each query is only a single round of communication for the client and does not require any communication between servers.
If at least one of the servers is non-colluding, we ensure that (1) no information is revealed on the clients query, (2) the total communication between the client and the servers is sublinear in the database size, and (3) each query answer only leaks a small and precisely quantified amount of information about the database to the client, even when the client is acting maliciously.
We implement our protocol and report its performance on real-world data. Our construction requires between 10 and 30 seconds of query latency over large databases of 10M feature vectors. Client overhead remained under 10μs of processing time per query and typically less than 4 MB of communication, depending on parameters.
Jyotirmoy Pramanik, Avishek Adhikari
Jonathan Takeshita, Colin McKechney, Justin Pajak, Antonis Papadimitriou, Ryan Karl, Taeho Jung
Elena Andreeva, Amit Singh Bhati, Bart Preneel, Damian Vizar
Our main contribution is the generic CTR encryption mode GCTR that makes parallel calls to an MFC to encrypt a message $M$. We analyze the set of all 36 ``simple and natural'' GCTR variants under the nivE security notion by Peyrin and Seurin from CRYPTO'16. Our proof method makes use of an intermediate abstraction called tweakable CTR (TCTR) that captures the core security properties of GCTR common to all variants, making their analyses easier. Our results show that many of the schemes achieve from well beyond birthday bound (BBB) to full $n$-bit security under nonce respecting adversaries and some even BBB and close to full $n$-bit security in the face of realistic nonce misuse conditions.
We finally present an efficiency comparison of GCTR using $\mathsf{ForkSkinny}$ (an MFC with $s=2$) with the traditional CTR and the more recent CTRT modes, both are instantiated with the $\mathsf{SKINNY}$ TBC. Our estimations show that any GCTR variant with $\mathsf{ForkSkinny}$ can achieve an efficiency advantage of over $20\%$ for moderately long messages, illustrating that the use of an efficient MFC with $s\geq 2$ brings a clear speed-up.
Arpita Patra, Thomas Schneider, Ajith Suresh, Hossein Yalame
In this work, we propose SynCirc, an efficient hardware synthesis framework designed for MPC applications. Our framework is based on Verilog and the open-source tool Yosys-ABC. It provides custom libraries and new constraints that accommodate multi-input AND gates. With this, we improve over TinyGMW by up to 3x in multiplicative depth with a corresponding improvement in online round complexity. Moreover, we provide efficient realizations of several new building blocks including comparison, multiplexers, and equality check. For these building blocks, we achieve improvements in multiplicative depth/online rounds between 22.3% and 66.7%. With these improvements, our framework makes multi-round MPC better-suited for high-latency networks such as the Internet. With respect to the look-up table based approach of Dessouky et al (NDSS17), our framework improves the online communication by 1.3x - 18x.
Simon Masson, Antonio Sanso, Zhenfei Zhang
13 September 2021
SUTD, Singapore
Closing date for applications:
Contact: Prof. Jianying Zhou
11 September 2021
Fujitsu Research of America
Profile Description:
Working hours and start dates are flexible. Internship duration will be 3 to 6 months, it can be either full time or part time. The position is open to candidates based on USA, Canada, UK, EU or Japan.
Closing date for applications:
Contact: Avradip Mandal (amandalATfujitsuDOTcom)
Monash University
## Requirements:
* Ph.D. in Computer Science or Mathematics
* Strong academic background in one of the following areas:
- Blockchain
- Cryptography
- Dependability
- Fault tolerance
- Reliable broadcast
- distributed and parallel computing
- Concurrency
## Starting date: ASAP
## Salary: Approx. $92,792 --$120,093 per year (Australian dollars) plus 17% Superannuation
## Location: Monash University, Clayton, Australia.
## Eligibility: We can only consider Australian or New Zealand citizens, Australian permanent residents, or those in Australia with working rights. Chinese / Malaysian citizens can also be considered to work in Monash Suzhou campus in China / Monash Malaysia campus in Selangor.
## Applications (first-come, first-served):
Please send a copy of
1. your detailed CV
2. research statement, and
3. a copy of 2 selected publications/preprints/thesis.
Closing date for applications:
Contact: Joseph Liu
More information: https://www.monash.edu/blockchain
10 September 2021
Joppe W. Bos, Thorsten Kleinjung, Dan Page
Geoffroy Couteau, Peter Rindal, Srinivasan Raghuraman
José Carlos Bacelar Almeida, Manuel Barbosa, Karim Eldefrawy, Stéphane Graham-Lengrand, Hugo Pacheco, Vitor Pereira
Linsheng Liu, Daniel S. Roche, Austin Theriault, Arkady Yerukhimovich
Kushal Babel, Philip Daian, Mahimna Kelkar, Ari Juels
CFF features three key properties. It is contract complete, meaning that it can model any smart contract platform and all its contracts---Turing complete or otherwise. It does so with asymptotically optimal model size. It is also attack-exhaustive by construction, meaning that it can automatically and mechanically extract all possible economic attacks on users' cryptocurrency across modeled contracts. Thanks to these properties, CFF can support multiple goals: economic security analysis of contracts by developers, analysis of DeFi trading risks by users, and optimization of arbitrage opportunities by bots or miners. Because CFF offers composability, it can support these goals with reasoning over any desired set of potentially interacting smart contract models.
We instantiate CFF as an executable model for Ethereum contracts that incorporates a state-of-the-art deductive verifier. Building on previous work, we introduce extractable value (EV), a new formal notion of economic security in composed DeFi contracts that is both a basis for CFF analyses and of general interest.
We construct modular, human-readable, composable CFF models of four popular, deployed DeFi protocols in Ethereum: Uniswap, Uniswap V2, Sushiswap, and MakerDAO, representing a combined 17 billion USD in value as of August 2021. We uses these models to show experimentally that CFF is practical and can drive useful, data-based EV-based insights from real world transaction activity. Without any explicitly programmed attack strategies, CFF uncovers on average an expected $56 million of EV per month in the recent past.
Shuai Han, Shengli Liu, Dawu Gu
In this paper, we study the achievability of tight ECPA and ECCA security for KEM in the multi-user setting, and present an impossibility result and an optimal security loss factor that can be obtained. The existing meta-reduction technique due to Bader et al. (EUROCRYPT 2016) rules out some KEMs, but many well-known KEMs, e.g., Cramer-Shoup KEM (SIAM J. Comput. 2003), Kurosawa-Desmedt KEM (CRYPTO 2004), run out. To solve this problem, we develop a new technique tool named rank of KEM and a new secret key partitioning strategy for meta-reduction. With this new tool and new strategy, we prove that KEM schemes with polynomially-bounded ranks have no tight ECPA and ECCA security from non-interactive complexity assumptions, and the security loss is at least linear in the number n of users. This impossibility result covers lots of well-known KEMs, including the Cramer-Shoup KEM, Kurosawa-Desmedt KEM and many others. Moreover, we show that the linear security loss is optimal by presenting concrete KEMs with security loss Θ(n). This is justified by a non-trivial security reduction with linear loss factor from ECPA/ECCA security to the traditional multi-challenge CPA/CCA security.