IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
15 September 2023
Jan Lauinger, Jens Ernstberger, Andreas Finkenzeller, Sebastian Steinhorst
Nir bitansky, Tomer Solomon
We prove a new bootstrapping theorem relying on functional encryption, which is known based on standard polynomial hardness assumptions. As a result we obtain the first fully homomorphic encryption scheme that avoids both circular security assumptions and super-polynomial hardness assumptions. The construction is secure against uniform adversaries, and can be made non-uniformly secure, under a widely-believed worst-case complexity assumption (essentially that non-uniformity does not allow arbitrary polynomial speedup).
At the heart of the construction is a new proof technique based on cryptographic puzzles. Unlike most cryptographic reductions, our security reduction does not fully treat the adversary as a black box, but rather makes explicit use of its running time (or circuit size).
Karim M. Abdellatif, Olivier Hériveaux
Koji Nuida, Tomoko Adachi
Giuseppe Manzoni
The existing proofs of the expansion work by first compiling the gadgets multiple times, and then by compiling the circuit with the resulting gadgets while assuming the worst from the original circuit. Instead, we reframe the expansion as a security reduction from the compiled circuit to the original one. Additionally, we extend it to support a broader range of encodings, and arbitrary probabilistic gates with an arbitrary number of inputs and outputs.
This allows us to obtain two concrete results: (i) At the cost of an additional size factor $\mathcal{O}(\log(d)^3)$, any $d$-probing secure compiler can be used to produce stateless circuits with security $2^{-d}$ against any adversary that sees all wires with a constant SD-noise of $2^{-7.41}/p$, where $p$ is the characteristic of the circuit's field. (ii) Any $n$-shares compiler with $(t,f)$-RPE gadgets needs $t+1$ (which in practice is $\lceil\frac{n}{2}\rceil$) randoms in the random gadget instead of $n$.
Gideon Samid
Minki Hhan, Aaram Yun
Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski
In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry's reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of \emph{small-norm prime ideals}. Using the reduction from Pellet-Mary and Stehl\'e [ASIACRYPT'21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.
Hongqing Liu, Chaoping Xing, Yanjiang Yang, Chen Yuan
In this paper, we propose the ramp hyper-invertible matrix which can be seen as the generalization of hyper-invertible matrix. Our ramp hyper-invertible matrix can be defined over constant-size field regardless of the size of this matrix. Similar to the arithmetic secret sharing scheme, to apply our ramp hyper-invertible matrix to perfectly secure MPC protocol, the maximum number of corruptions has to be compromised to $\frac{(1-\epsilon)n}{3}$. As a consequence, we present the first perfectly secure MPC protocol in the presence of $\frac{(1-\epsilon)n}{3}$ malicious corruptions with constant communication complexity. Besides presenting the variant of hyper-invertible matrix, we overcome several obstacles in the construction of this MPC protocol. Our arithmetic secret sharing scheme over constant-size field is compatible with the player elimination technique, i.e., it supports the dynamic changes of party number and corrupted party number. Moreover, we rewrite the public reconstruction protocol to support the sharings over constant-size field. Putting these together leads to the constant-size field variant of celebrated MPC protocol in [5].
We note that although it was widely acknowledged that there exists an MPC protocol with constant communication complexity by replacing Shamir secret sharing scheme with arithmetic secret sharing scheme, there is no reference seriously describing such protocol in detail. Our work fills the missing detail by providing MPC primitive for any applications relying on MPC protocol of constant communication complexity. As an application of our perfectly secure MPC protocol which implies perfect robustness in the MPC-in-the-Head framework, we present the constant-rate zero-knowledge proof with $3$ communication rounds. The previous work achieves constant-rate with $5$ communication rounds [32] due to the statistical robustness of their MPC protocol. Another application of our ramp hyper-invertible matrix is the information-theoretic multi-verifier zero-knowledge for circuit satisfiability[43]. We manage to remove the dependence of the size of circuit and security parameter from the share size.
University of Surrey
The role will be based in the Surrey Centre for Cyber Security (SCCS) within the School of Computer Science and Electronic Engineering at the University of Surrey and we offer the opportunity for hybrid working – some time on campus and some from home. We welcome applicants who wish to pursue the role through flexible working patterns.
You will have the opportunity to conduct research within the context of the Defence Data Research Centre, funded by DSTL, in which SCCS is a partner, alongside the Universities of Exeter and Liverpool, and the Digital Catapult. The Centre is focusing on problems related to the use of data for Artificial Intelligence applications, particularly around the challenges of bringing raw data to the state where it can be used. We consider these problems within a defence context, such as logistics support, object tracking and data wrangling. SCCS is focused on the area of data resilience, security and privacy, considering problems such as the trustworthiness of data and issues around anonymisation. The successful candidate will work under the direction of Professor Steve Schneider together with the support of other colleagues at Surrey and DDRC. The post holder will have exposure to the Centre’s broader research agenda in the areas of trusted computing, data privacy, privacy preserving security, applied cryptography, and a range of cyber security topics and as such provides an excellent opportunity to influence research directions during the course of the appointment.
Closing date for applications:
Contact: Professor Steve Schneider
More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13521
Paderborn University, Department of Computer Science, Paderborn, Germany
Postdoc (f/m/d)
(salary is according to E13 TV-L)
A position with 100 % of the regular working hours is available as of the next possible date. The employment is initially limited to three years and is based on the legal regulations of the Wissen-schaftszeitvertragsgesetzes (WissZeitVG).
Your duties and responsibilities:
• Support in the construction and operation of a (photonic) quantum communication network and its combination with classical communication networks.
• Support for users of a quantum network
• Development and optimisation of quantum communication protocols, e.g. for key exchange protocols
• Organising and running courses on the basics and use of quantum networks and quantum communication protocols (basic to advanced)
• Leading a team for the operation of a quantum network and its integration into classical net-works
Hiring requirements:
• Completed PhD in computer science, mathematics or physics or comparable qualification
• Experience in the operation of communication networks and the design of network protocols (classical and/or quantum)
• High motivation and willingness for interdisciplinary cooperation between computer science and physics
• Good knowledge of German and English, both written and spoken
• Friendliness, flexibility, ability to work in a team, initiative and willingness to work independently
Closing date for applications:
Contact: Please send your application including a CV (preferably in a single pdf file) using the Ref. No. 6106 by 30th September, 2023 to: bloemer@upb.de
More information: https://cs.uni-paderborn.de/en/cuk
San Francisco, USA, 6 May - 9 May 2024
Submission deadline: 2 October 2023
Notification: 18 December 2023
13 September 2023
Nouri Alnahawi, Kathrin Hövelmanns, Andreas Hülsing, Silvia Ritsch, Alexander Wiesmaier
To pave the way towards reasoning post-quantum security, we therefore resort to a (still classical) game-based security proof in the BPR model (EUROCRYPT 2000). We consider this a crucial stepping stone towards a full proof of post-quantum security. We prove security of (a minor variation of) OCAKE generically, assuming the underlying KEM satisfies common notions of ciphertext indistinguishability, anonymity, and (computational) public key uniformity. To achieve tight security bounds, we relate security of OCAKE to multi-user variants of the aforementioned properties.
We provide a full detailed proof, something often omitted in publications concerned with game-based security of PAKE. As a side-contribution, we demonstrate how to handle password guesses in a game-based proof in detail. Something we were unable to find in the existing literature.
Zhelei Zhou, Bingsheng Zhang, Hong-Sheng Zhou, Kui Ren
In this work, we propose the first practical 2-round protocol for SIF against \emph{a dishonest majority} in the preprocessing model; moreover, the online phase is highly efficient as it requires no cryptographic operations and achieves information theoretical security. For SIF among 5 parties, our construction takes 152.34ms (total) to evaluate an AES-128 circuit with 7.36ms online time. Compared to the state-of-the-art (honest majority) solution (Baum et al., CCS 2022), our construction is roughly 2$\times$ faster in the online phase, although more preprocessing time is needed. Compared to the state-of-the-art generic MPC against a dishonest majority (Wang et al., CCS 2017; Cramer et al., Crypto 2018), our construction outperforms them w.r.t. both total running time and online running time.
Sam A. Markelon, Mia Filić, Thomas Shrimpton
Nico Döttling, Tamer Mour
Despite substantial progress in constructing correlation intractable hash functions, all constructions known to date are based on highly-structured hardness assumptions and, further, are of complexity scaling with the circuit complexity of the target relation class.
In this work, we initiate the study of the barriers for building correlation intractability. Our main result is a lower bound on the complexity of any black-box construction of CIH from collision resistant hash (CRH), or one-way permutations (OWP), for any sufficiently expressive relation class. In particular, any such construction for a class of relations with circuit complexity $t$ must make at least $\Omega(t)$ invocations of the underlying building block.
We see this as a first step in developing a methodology towards broader lower bounds.
Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, Floris Westermann
Afterwards, we consider achieving consensus using deterministic protocols, for which the agreement condition must be appropriately relaxed depending on the convexity space. For the relevant case of graph convexity spaces, we find that a previous asynchronous approximate agreement protocol for chordal graphs is incorrect, and hereby give a new protocol for the problem designed for the best-of-both-worlds model and achieving tight point-wise resilience bounds. Finally, we show that asynchronous graph approximate agreement remains unsolvable by deterministic protocols even when corruptions are restricted to at most two crashing nodes and the distance agreement threshold is linear in the size of the graph.
Fuchun Lin, Chaoping Xing, Yizhou Yao, Chen Yuan
David Fifield
My primary purpose is to provide an introduction of circumvention threat models to specialists in cryptography, and to make the point that while cryptography is a necessary tool in circumvention, it is not the sole or even most important consideration. Secondarily, I want to furnish a few instructive examples of cryptographic design and implementation errors in uncontrived, deployed protocols. While the flaws I discuss affected systems of significant social importance with millions of collective users, they are not well-known outside a small circle of specialists in circumvention.
Amit Singh Bhati, Erik Pohle, Aysajan Abidin, Elena Andreeva, Bart Preneel
As an important building block in this scenario, we propose a new, provably secure family of lightweight modes for authenticated encryption with associated data (AEAD), called Eevee. The Eevee family has fully parallel decryption, making it suitable for MPC protocols for which the round complexity depends on the complexity of the function they compute. Further, our modes use the lightweight forkcipher primitive that offers fixed-length output expansion and a compact yet parallelizable internal structure.
All Eevee members improve substantially over the few available state-of-the-art (SotA) MPC-friendly modes and other standard solutions. We benchmark the Eevee family on a microcontroller and in MPC. Our proposed mode Jolteon (when instantiated with ForkSkinny) provides 1.85x to 3.64x speedup in IoT-encryption time and 3x to 4.5x speedup in both MPC-decryption time and data for very short queries of 8 bytes and, 1.55x to 3.04x and 1.23x to 2.43x speedup, respectively, in MPC-decryption time and data for queries up to 500 bytes when compared against SotA MPC-friendly modes instantiated with SKINNY. We also provide two advanced modes, Umbreon and Espeon, that show a favorable performance-security trade-off with stronger security guarantees such as nonce-misuse security. Additionally, all Eevee members have full $n$-bit security (where $n$ is the block size of the underlying primitive), use a single primitive and require smaller state and HW area when compared with the SotA modes under their original security settings.