IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
31 May 2022
Yaobin Shen and Ferdinand Sibleyras
In this work, we revisit previous constructions of key-reduced variants of 3kf9 and analyze what went wrong in security analyzes. Interestingly, we find that a single doubling at the end can not only fix 2kf9 to go beyond the birthday bound, but also help 1kf9 to go beyond the birthday bound. We then propose two new key-reduced variants of 3kf9, called n2kf9 and n1kf9. By leveraging previous attempts, we prove that n2kf9 is secure up to 2^{2n/3} queries, and prove that n1kf9 is secure up to 2^{2n/3} queries when the message space is prefix-free. We also provide beyond-birthday analysis of n2kf9 in the multi-user setting. Note that compared to EMAC and CBC-MAC, the additional cost to provide a higher security guarantee is expected to be minimal for n2kf9 and n1kf9. It only requires one additional blockcipher call and one doubling.
Pascal Reisert, Marc Rivinius, Toomas Krips, and Ralf Küsters
Ivana Ivkovic and Nikolay Kaleyski
Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, and Chun-Yen Chou
Qian Liu, Zhiwei Huang, Jianrui Xie, Ximeng Liu, and Jian Zou
Harsh Chaudhari, Matthew Jagielski, and Alina Oprea
Midhul Vuppalapati, Kushal Babel, Anurag Khandelwal, and Rachit Agarwal
Aisling Connolly, Jerome Deschamps, Pascal Lafourcade, and Octavio Perez Kempner
Dana Dachman-Soled, Seung Geol Choi, S. Dov Gordon, Linsheng Liu, and Arkady Yerukhimovich
Hanjun Li, Huijia Lin, and Ji Luo
* We construct the first key-policy ABE scheme for circuits with constant-size secret keys, |sk_f|=poly(lambda), which concretely consist of only three group elements. The previous state-of-the-art construction by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth d of the policy circuits, |sk_f|=poly(d,lambda). Our new scheme removes this dependency of key size on d while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, |ct|=|x|poly(d,lambda).
* We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, in particular, |sk_f|=poly(lambda) and |ct_x|=poly(|x|,lambda). Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non constant-size keys [Agrawal--Yamada, Eurocrypt '20; Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size, as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them.
Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18] the constructions become adaptively secure.
Ghada Almashaqbeh, Ran Canetti, Yaniv Erlich, Jonathan Gershoni, Tal Malkin, Itsik Pe’er, Anna Roitburd-Berman, and Eran Tromer
Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios Dimou, Ingrid Verbauwhede, Frederik Vercauteren, and David W. Archer
BASALISC exploits data representation in residue number systems and number-theoretic transforms to realize massive FHE parallelism. We propose a new generalized version of bootstrapping that can be implemented with optimized Montgomery multipliers that cost 46% less in silicon area and 40% less in power consumption versus traditional approaches. BASALISC is a Reduced Instruction Set Computing (RISC) architecture with a four-layer memory hierarchy, including a two-dimensional conflict-free inner memory layer that enables 32 Tb/s radix-256 number-theoretic transform (NTT) computations without pipeline stalls. Our conflict-resolution data permutation hardware is re-used to compute BGV automorphisms without additional hardware and without throughput penalty. BASALISC additionally includes a custom multiply-accumulate unit familiar in Digital Signal Processing (DSP) architectures, with which we accelerate tight BGV key switching loops. The BASALISC computation units and inner memory layers are designed in asynchronous logic, allowing them to run at different speeds to optimize each function. BASALISC is designed for Application-Specific Integrated Circuit (ASIC) implementation with a 1 GHz operational frequency, and is already underway toward tape-out with a 150mm2 die size in a 12nm Global Foundries process.
The BASALISC toolchain comprises both a custom compiler and a joint performance and correctness simulator. We evaluate BASALISC in multiple ways: we study its physical realizability; we emulate and formally verify its core functional units; and we study its performance on a single iteration of logistic regression training over encrypted data. For this application, comprising from up to 900K high-level BASALISC instructions (including 513 bootstraps) down to 27B low-level instructions, we show a speedup of at least 2,025x over HElib - a popular software FHE library - running on a Xeon-class processor.
Martin R. Albrecht and Yixin Shen
On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).
Keewoo Lee
Péter Kutas and Christophe Petit
The best-known protocol following that approach is the supersingular isogeny Diffie-Hellman protocol (SIDH); this protocol was turned into the CCA-secure key encapsulation mechanism SIKE, which was submitted to and remains in the third round of NIST's post-quantum standardization process as an ``alternate'' candidate.
Isogeny-based cryptography generally relies on the conjectured hardness of computing an isogeny between two isogenous elliptic curves, and most cryptanalytic work referenced on SIKE's webpage exclusively focuses on that problem.
Interestingly, the hardness of this problem is sufficient for neither SIDH nor SIKE. In particular, these protocols reveal additional information on the secret isogeny, in the form of images of specific torsion points through the isogeny.
This paper surveys existing cryptanalysis approaches exploiting this often called ``torsion point information'', summarizes their current impact on SIKE and related algorithms, and suggests some research directions that might lead to further impact.
Binbin Tu, Yu Chen, Qi Liu, and Cong Zhang
In this work, we propose a generic framework of using the leveled fully homomorphic encryption and a newly introduced protocol called permute matrix Private EQuality Test (pm-PEQT) to construct the \emph{unbalanced} PSU that is secure against semi-honest adversaries. By instantiating the pm-PEQT, we obtain fast unbalanced PSU protocols with a small communication overhead. Our protocol has communication complexity \emph{linear in the size of the smaller set, and logarithmic in the larger set}. More precisely, if the set sizes are $|X|\ll |Y|$, our protocol achieves a communication overhead of $O(|X|\log |Y|)$.
Finally, we implement our protocols that can compare with the state-of-the-art PSU. Experiments show that our protocols are more efficient than all previous protocols in the unbalanced case, especially, the larger the difference of two set sizes, the better our protocols perform. Our running-time-optimized benchmarks show that it takes 18.782 seconds of computation and 2.179 MB of communication to compute the union between $2^{10}$ strings and $2^{19}$ strings. Compared to prior secure PSU proposed by Jia et al. (Usenix Security 2022), this is roughly a $300 \times$ reduction in communication and $20 \times$ reduction in computational overhead with a single thread in WAN/LAN settings.
Yu Chen, Min Zhang, Cong Zhang, and Minglang Dong
We demonstrate the practicality of our framework with implementations. By plugging our cwPRF-based mqRPMT to the general framework, we obtain the first PSU protocol with strict linear complexity. For input sets of size $2^{20}$, the resulting PSU protocol requires roughly 80 MB bandwidth, and 50 seconds using 8 threads. To the best of our knowledge, it requires the least communication among all the known PSU protocols. By plugging our FHE-based mqRPMT$^*$ to the general framework, we obtain a PSU$^*$ suitable for unbalanced setting, whose communication complexity is linear in the size of the smaller set, and logarithmic in the larger set.
29 May 2022
Mysten Labs
Successful applicants will work closely with experts in both academia and industry including George Danezis, Konstantinos Chalkias, Foteini Baldimtsi, Alberto Sonnino, François Garillot, Sam Blackshear, Lefteris Kokoris-Kogias, while enjoying a high degree of ownership & autonomy in working conditions & task prioritization.
Ideal candidate expectations:
- PhD or PostDoc researcher - or - engineer in cryptography, software security or distributed systems.
- at least one publication in any of the top cryptography, privacy and security conferences, such as: CCS, S&P, CRYPTO, USENIX SECURITY, EUROCRYPT, ASIACRYPT, NDSS, FC, AsiaCCS, EUROS&P, PETS, CT-RSA, ESORICS etc.
- Understanding of fundamental cryptographic schemes & underlying math for any of the following: hash functions, finite field arithmetic, polynomials (FFT) & elliptic curves, bilinear pairings, threshold signatures.
- Experience implementing high-performance & parallelizable protocols in languages such as Rust, Go, Java, or C/C++, and Github portfolio or productionized implementation will be a plus.
Our team is 100% remote & we are hiring across the world. Here at Mysten Labs, you’ll be joining a world class team with tremendous growth potential. We raised our 1st funding round ($36m series A) from top Silicon Valley VCs led by Andreessen Horowitz (a16z) with participation from Redpoint, Lightspeed, Coinbase Ventures, Electric Capital, Standard Crypto, NFX, Slow Ventures, Scribble Ventures, Samsung Next, Lux Capital etc.
HOW TO APPLY: Applicants are invited to e-mail their CV (use title: Summer 2022 Cryptography Internship) to jobs@mystenlabs.com
Closing date for applications:
Contact: Kostas Chalkias (Chief Cryptographer)
JP Morgan Chase, various locations in US
We are looking for a cryptography engineer who will be part of the Blockchain Technology Security Group to build foundational services for JP Morgan distributed ledger technology initiatives. In this role, you will be designing and coding security components and applications. You will have the exciting challenge of working on cutting-edge technology and building enterprise solutions that cater to all the lines of business. You’ll work in a collaborative, trusting, thought-provoking environment—one that encourages diversity of thought and creative solutions that are in the best interests of our customers globally
Qualifications
- Experience as applied cryptographer
- Experience with OpenSSL /TLS API; threading and socket programming in Linux, HSMs, and PKCS #11
- Solid understanding of Linux OS with strong knowledge of object oriented programming; specifically high-level languages such as Java, Python, Go, and node.js, C, C++ and Bash
- Familiar/Experience building solutions for digital assets and distributed ledger technology (blockchain) with focus on algorithms and data structures
- Desirable: Experience with multi-party computation (MPC) & HSMs and custody crypto assets
Closing date for applications:
Contact: France Law (france.law@jpmchase.com)
Telecom Paris, Institut Polytechnique de Paris
Closing date for applications:
Contact: Hieu Phan (hieu.phan@telecom-paris.fr)
More information: https://institutminestelecom.recruitee.com/l/en/o/chaire-de-professeur-ou-professeure-junior-en-securite-des-grandes-infrastructures-numeriques-a-telecom-paris