International Association
for Cryptologic Research

Asynchronous Remote Key Generation (ARKG, introduced in ACM CCS 2020) allows for a party to create public keys for which corresponding private keys may be later computed by another intended party only. ARKG can be composed with standard public-key cryptosystems and has been used to construct a new class of privacy-preserving proxy signatures. The original construction of ARKG, however, generates discrete logarithm key pairs of the form $(x, g^x)$.

In this paper we define a generic approach for building ARKG schemes which can be applied to a wide range of pairing-based cryptosystems. This construction is based on a new building block which we introduce and call Asymmetric Key Generation (AKG) along with its extension $\phi$-AKG where $\phi$ is a suitable mapping for capturing different key structures and types of pairings. We show that appropriate choice of $\phi$ allows us to create a secure ARKG scheme compatible with any key pair that is secure under the Uber assumption (EUROCRYPT 2004).

To demonstrate the extensive range of our general approach, we construct ARKG schemes for a number of popular pairing-based primitives: Boneh-Lynn-Shacham (JoC 2004), Camenisch-Lysyanskaya (CRYPTO 2004), Pointcheval-Sanders (CT-RSA 2016), Waters (EUROCRYPT 2005) signatures and structure-preserving signatures on equivalence classes (ASIACRYPT 2014). For each scheme we give an implementation and provide benchmarks that show the feasibility of our techniques.

We introduce and formalize tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in the sense that they allow only three wire values ($0$,$1$, and undefined – $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in the sense that their statically placed gates fire (execute) eagerly as their inputs become defined, implying an order of execution that depends on the input. This dynamic behavior is sufficient to efficiently evaluate RAM programs.

We construct a TSC that emulates $T$ steps of any RAM program and that has only $O(T \cdot \log^3 T \cdot \log \log T )$ gates. Contrast this with the reduction to Boolean circuits, where the best known approach scans all of memory on each access, incurring quadratic cost. Thus, while simple, TSCs have expressive power that closely approximates the RAM model.

We connect TSCs with Garbled Computation (GC). TSCs capture the power of garbling far better than Boolean Circuits, offering a significantly more expressive model of computation while leaving the per-gate cost of evaluation essentially unchanged.

Our most exciting explicit result is authenticated Garbled RAM (GRAM), an approach to constant-round maliciously-secure 2PC of RAM programs. Let $\lambda$ denote the computational security parameter. We first extend authenticated garbling to TSCs; then, by simply plugging in our TSC-based RAM, we immediately obtain authenticated GRAM running at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming all prior work, including even GRAMs in the semi-honest setting. (Prior GRAMs measure per-access cost for a memory storing large $w = \Omega(\log^2 T)$-bit words; by this metric, our cost is $O(w\cdot \log T \cdot \log\log T \cdot \lambda)$.)

As another highlight of the power of TSCs, we give a simple semi-honest garbling of TSCs based only on one-way functions. This yields standard- assumption-based GRAM at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming the best prior GRAM in this setting by more than factor $\lambda$.

Wireless-channel key exchange (WiKE) protocols that leverage Physical Layer Security (PLS) techniques could become an alternative solution for secure communication establishment, such as vehicular ad-hoc networks, wireless IoT networks, or cross-layer protocols.

In this paper, we provide a novel abstraction of WiKE protocols and present the first game-based security model for WiKE. Our result enables the analysis of security guarantees offered by these cross-layer protocols and allows the study of WiKE's compositional aspects. Further, we address the potential problem of the slow-rate secret-key generation in WiKE due to inadequate environmental conditions that might render WiKE protocols impractical or undesirably slow. We explore a solution to such a problem by bootstrapping a low-entropy key coming as the output of WiKE using a Password Authenticated Key Exchange (PAKE). On top of the new security definition for WiKE and those which are well-established for PAKE, we build a compositional WiKE-then-PAKE model and define the minimum security requirements for the safe sequential composition of the two primitives in a black-box manner. Finally, we show the pitfalls of previous ad-hoc attempts to combine WiKE and PAKE.

We give an algebraic attack to forge the signature of a scheme called MPPK/DS, which can be achieved by solving a linear system in 5 variables with coefficients on $\mathbb{Z}/2^x q \mathbb{Z}$ for some odd prime $q$ and $x ≥ 1$.

The School of Cyber Science and Engineering (formerly known as the School of Information Security Engineering) of Shanghai Jiao Tong University was founded in October 2000. It was the first school-level training base for high-level information security professionals in China and was jointly established by the Ministry of Education of China, the Ministry of Science and Technology of China, and the Shanghai Municipal People’s Government. The undergraduate and postgraduate students of the school mainly come from the top 100 key high schools and 985/double first-class universities in China. The school is ranked among the best cyberspace security nationwide every year. The school has a solid foundation and strength in the field of academic research and technological innovation on cyberspace security. The school is committed to building a world-class academic research center, cultivating the talents of the country and society. The school is in great demand of a number of world renowned professors, outstanding young researchers, full-time research fellows and post-doctors. The school now has a few positions available at the rank of tenure-track Assistant/Associate Professors, tenured Full Professors as well as Research Assistants/Associates and Post-Doctors in theory and practice of cyberspace security.
Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching.
The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “Outstanding Youth Talents Program”, Shanghai “Talents Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.

Closing date for applications:

Contact: Chaoping Xing, emial: xingcp@sjtu.edu.cn;
Ni Liang, email: liangni@sjtu.edu

Xiamen University Malaysia is now seeking highly motivated, committed and qualified individuals for academic teaching positions in computer science and cyber security. Applicants must possess a PhD degree in a related discipline. The ideal candidate is expected to be able to support general computing subjects, as well as cyber security specialization subjects.

Applicants with specific teaching and/or research interests in FOUR OR MORE of the following areas are encouraged to apply:

• Calculus
• Linear Algebra
• Discrete Mathematics
• Probability and Statistics
• Design & Analysis of Algorithms
• Computer Composition
• Operating Systems
• Object-Oriented Programming-C++
• Object-Oriented Programming-Java
• ARM Assembly Language
• Computer Networks and Communication
• Compiler Principles
• Cyber Security
• Modern Cryptography
• Digital Forensics and Investigation
• Network Traffic Monitoring and Analysis
• Advanced Network Attack and Defence Technology
• Malware Analysis
• Cryptanalysis
• Big Data Analytics
• Biometrics
• Blockchain Technology

HOW TO APPLY
Applicants are invited to submit a digital application packet to: iftekhar.salam@xmu.edu.my

The subject line of your email must include: your name, relevant academic discipline, and the specific position for which you are applying for. All application packets must include the following attachments:

1. Your current CV with publication (*Asterisk to indicate corresponding author, include Indexing & Quartile);
2. Cover letter;
3. List of courses from the above that you are able to support;
4. Evidence of academic qualifications;
5. 3-5 Full-Text publications (if applicable);
6. Teaching evaluation (if applicable);

The positions will remain open until filled. Applications with missing information will be considered incomplete and will not be processed.

Closing date for applications:

Contact: iftekhar.salam@xmu.edu.my

The Surrey Centre for Cyber Security (SCCS) within the School of Computer Science and Electronic Engineering at the University of Surrey is seeking to recruit a full-time Research Fellow in Data Resilience, Security and Privacy. The post is available with 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. The successful candidate will be expected 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 post holder will benefit from the research environment provided by the Surrey Centre for Cyber Security, an Academic Centre of Excellence in Cyber Security Research recognised by the National Cyber Security Centre. The Centre’s broader research agenda is in the areas of trusted computing, data privacy, privacy preserving security, applied cryptography, and a range of cyber security topics. The post will also offer an excellent opportunity for a researcher to develop their own research agenda within the area of data resilience, security and privacy, and to work collaboratively in a team of colleagues working on related projects around privacy and security. It will also provide an excellent opportunity to influence research directions during the course of the appointment. The successful candidate will work under the direction of Professor Steve Schneider together with the support of other colleagues at Surrey and DDRC. Researchers with an interest in data security and in its role within AI applications are encouraged to apply.

Closing date for applications:

Contact: Steve Schneider: s.schneider@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13080&forced=2

Applications are invited for a Postdoctoral Research Fellow, to work on the EPSRC-funded project “PKC-Sec: Security Analysis of Classical and Post-Quantum Public Key Cryptography Assumptions”. The successful post holder is expected to start as soon as possible after accepting the position and will be based in the Department of Computer Science and its highly regarded Surrey Centre for Cyber Security (SCCS), working with Dr. Robert Granger.

The aim of the project is to research and develop algorithms for solving computational problems that are foundational to the security of public key cryptography, both now and in the future. In particular, it will study: the discrete logarithm problem in finite fields of fixed characteristic, for which an efficient classical algorithm is potentially on the horizon; the security of the Legendre pseudo-random function, which is extremely well suited for multi-party computation and is used in the proof of custody construction within Ethereum, but is not so well-studied; and finally the security of supersingular isogeny-based post-quantum cryptography, which although a relatively young field offers many very promising applications. Due to their nature, any cryptographic assumptions based on mathematical constructions are potentially weaker than currently believed, and the project will deepen our understanding and assess the hardness of these natural and fundamental problems.

The postholder will be responsible for conducting research into the three aforementioned areas, working alongside Dr. Granger and in collaboration with the official project partners: the Ethereum Foundation; PQShield; and K.U. Leuven, namely, Prof. Frederik Vercauteren and members of this group within COSIC. The successful applicant is expected to have a PhD (gained or near completion), or equivalent professional experience in computer science or a related subject, in technical areas relevant to the envisioned research.

For informal inquiries about the position, please contact Dr. Robert Granger (r.granger@surrey.ac.uk). This is a fixed term contract for up to 2 years. The application deadline is 16th April 2023.

Closing date for applications:

Contact: Dr. Robert Granger

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13154&forced=2

We construct a sublinear-time single-server pre-processing Private Information Retrieval (PIR) scheme with optimal client storage and server computation (up to poly-logarithmic factors), only relying on the assumption of the existence of One Way Functions (OWF). Our scheme achieves amortized $\tilde{O}(\sqrt{n})$ online server computation and client computation and $O(\sqrt{n})$ online communication per query, and requires $\widetilde{O}_\lambda(\sqrt{n})$ client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme only utilizes lightweight cryptography such as PRFs, which is easily instantiated in practice. To our knowledge, this is the first practical implementation of a single-server sublinear-time PIR scheme. Compared to existing linear time single-server solutions, our schemes are faster by $10-300\times$ and are comparable to the fastest two-server schemes. In particular, for a 100GB database of 1.6 billion entries, our experiments show that our scheme has less than 40ms online computation time on a single core.

Verifiable secret sharing (VSS) allows a dealer to send shares of a secret value to parties such that each party receiving a share can verify (often interactively) if the received share was correctly generated. Non-interactive VSS (NI-VSS) allows the dealer to perform secret sharing such that every party (including an outsider) can verify their shares along with others’ without any interaction with the dealer as well as among themselves. Existing NI-VSS schemes employing either exponentiated ElGamal or lattice-based encryption schemes involve zero-knowledge range proofs, resulting in higher computational and communication complexities.

This preliminary report presents cgVSS, a NI-VSS protocol that uses class groups for encryption. In cgVSS, the dealer encrypts the secret shares in the exponent through a class group encryption such that the parties can directly decrypt their shares. The existence of a subgroup where a discrete logarithm is tractable in a class group allows the receiver to efficiently decrypt the share though it is available in the exponent. This yields a novel-yet-simple VSS protocol where the dealer publishes the encryptions of the shares and the zero-knowledge proof of the correctness of the dealing. The linear homomorphic nature of the employed encryption scheme allows for an efficient zero-knowledge proof of correct sharing. Given the rise in demand for VSS protocols in the blockchain space, especially for publicly verifiable distributed key generation (DKG), our NI-VSS construction can be particularly interesting. We implement our cgVSS protocol using the BICYCL library and compare its performance with the state-of-the-art NI-VSS by Groth. Our protocol reduces the message complexity and the bit length of the broadcast message by at least 5.6x for a 150 party system, with a 1.8x speed-up in the dealer’s computation time and with similar receiver computation times.

HID Global is a major vendor of physical access control systems. In 2012, it introduced Seos, its newest and most secure contactless RFID credential technology, successfully remediating known flaws in predecessors iCLASS and Prox. Seos has been widely deployed to secure sensitive assets and facilities. To date, no published research has demonstrated a security flaw in Seos. We present a relay attack developed with inexpensive COTS hardware, including the Proxmark 3 RDV4. Our attack is capable of operating over extremely long ranges as it uses the Internet as a communications backbone. We have tested multiple real-world attack scenarios and are able to unlock a door in our lab with a card approximately 1960 km away. Our attack is covert and does not require long-term access to the card. Further, our attack is generic and is potentially applicable to other protocols that, like Seos, use ISO/IEC 14443A to communicate. We discuss several mitigations capable of thwarting our attack that could be introduced in future credential systems or as an update to Seos-compatible readers' firmware; these rely on rejecting cards that take too long to reply.

Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in $\mathbb{R}^D$ as input. The honest parties are required to obtain very close outputs in $\mathbb{R}^D$ that lie inside the convex hull of their inputs.

Existing Multidimensional Approximate Agreement protocols achieve resilience against $t_s < n / (D + 1)$ corruptions under a synchronous network where messages are delivered within some time $\Delta$, but become completely insecure as soon as a single message is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to $t_a < n / (D + 2)$ corruptions.

We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate $t_s$ corruptions when the network is synchronous, and also tolerate $t_a \leq t_s$ corruptions when the network is asynchronous. We provide a protocol that works as long as $(D + 1) \cdot t_s + t_a < n$, and matches several existing lower bounds.

PKC 2023 will take place in Atlanta, USA on May 7-10, 2023. The registration site is now open:

https://pkc.iacr.org/2023/registration.php

Register by April 7th to avoid late fees.

Event date: 15 August to 16 August 2023
Submission deadline: 24 April 2023
Notification: 1 June 2023

The generalized inverses of systematic non-square binary matrices have applications in mathematics, channel coding and decoding, navigation signals, machine learning, data storage and cryptography such as the McEliece and Niederreiter public-key cryptosystems. A systematic non-square $(n-k) \times k$ matrix $H$, $n > k$, has $2^{k\times(n-k)}$ different generalized inverse matrices. This paper presents an algorithm for generating these matrices and compares it with two well-known methods, i.e. Gauss-Jordan elimination and Moore-Penrose methods. A random generalized inverse matrix construction method is given which has a lower execution time than the Gauss-Jordan elimination and Moore-Penrose approaches.

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, a orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice $\mathbb Z^n$ is of particular interest ($\mathbb Z$LIP). Heuristic analysis suggests that the BKZ algorithm with blocksize $\beta = n/2 + o(n)$ solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022).

In this work, I propose a provable version of this statement, namely, that $\mathbb Z$LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem (SVP) oracle in dimension at most $n/2 + 1$.

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In this work we revisit the Micciancio-Peikert preimage sampling algorithm with different contributions. We first propose a finer analysis of this procedure which results in interesting efficiency gains of around 20% on the preimage sizes without affecting security. It can thus be used as a drop-in replacement in every construction resorting to it. We then reconsider the Lyubashevsky-Wichs sampler for Micciancio-Peikert trapdoors which leverages rejection sampling but suffered from strong parameter requirements that hampered performance. We propose an improved analysis which allows to obtain much more compact parameters. This leads to gains of up to 30% compared to the original Micciancio-Peikert sampling technique and opens promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. As an application of the latter, we give the first lattice-based aggregate signature supporting public aggregation and that achieves relevant compression compared to the concatenation of individual signatures. Our scheme is proven secure in the aggregate chosen-key model coined by Boneh et al. in 2003, based on the well-studied assumptions Module Learning With Errors and Module Short Integer Solution.

We prove adaptive security of a simple three-round threshold Schnorr signature scheme, which we call Sparkle. The standard notion of security for threshold signatures considers a static adversary – one who must declare which parties are corrupt at the beginning of the protocol. The stronger adaptive adversary can at any time corrupt parties and learn their state. This notion is natural and practical, yet not proven to be met by most schemes in the literature.

In this paper, we demonstrate that Sparkle achieves several levels of security based on different corruption models and assumptions. To begin with, Sparkle is statically secure under minimal assumptions: the discrete logarithm assumption (DL) and the random oracle model (ROM). If an adaptive adversary corrupts fewer than t/2 out of a threshold of t + 1 signers, then Sparkle is adaptively secure under a weaker variant of the one-more discrete logarithm assumption (AOMDL) in the ROM. Finally, we prove that Sparkle achieves full adaptive security, with a corruption threshold of t, under AOMDL in the algebraic group model (AGM) with random oracles. Importantly, we show adaptive security without requiring secure erasures. Ours is the first proof achieving full adaptive security without exponential tightness loss for any threshold Schnorr signature scheme; moreover, the reduction is tight.

Bounded-collusion identity-based encryption (BC-IBE) is a variant of identity-based encryption, where an adversary obtains user secrete keys corresponding to at most $d$ identities. From results of existing work, it is proven that BC-IBE can be constructed from public key encryption (PKE) with several properties. In particular, we focus on post-quantum PKE schemes submitted to the NIST PQC competition, as the underlying PKE of BC-IBE schemes. This is because post-quantum cryptography is one of active research areas, due to recent advancement of developing quantum computers. Hence, it is reasonable to consider converting such PKE schemes into encryption schemes with additional functionalities. By using existing generic constructions of BC-IBE, those post-quantum PKE schemes are transformed into BC-IBE with non-compact public parameter. In this paper, we propose generic constructions of BC-IBE whose public parameter-size is more compact, and it is possible to apply many post-quantum PKE schemes secure against chosen plaintext attacks, into our generic constructions. To this end, we construct BC-IBE schemes from a group testing perspective, while existing ones are constructed by employing error-correcting codes or cover-free families. As a result, we can obtain BC-IBE schemes with more compact public parameter, which are constructed from the NIST PQC PKE schemes.

A thread of physical attacks that try to obtain secret information from cryptographic modules has been of academic and practical interest. One of the concerns is determining its efficiency, e.g., the number of attack trials to recover the secret key. However, the accurate estimation of the attack efficiency is generally expensive because of the complexity of the physical attack on a cryptographic algorithm. Based on this background, in this study, we propose a new abstraction model for evaluating the attack efficiency of the probing and DFA attacks. The proposed model includes an abstracted attack target and attacker to determine the amount of leaked information obtained in a single attack trial. We can adapt the model flexibly to various attack scenarios and can get the attack efficiency quickly and precisely. In the probing attack on AES, the difference in the attack efficiency is only approximately 0.3% between the model and experimental values, whereas that of a previous model is approximately 16%. We also apply the probing attack on DES, and the results show that DES has a high resistance to the probing attack. Moreover, the proposed model works accurately also for the DFA attack on AES.