International Association
for Cryptologic Research

The celebrated result of Yao (FOCS'82) shows that concatenating $n\cdot p(n)$ copies of a weak one-way function (OWF) $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, yields a strong OWF $g$, showing that weak and strong OWFs are black-box equivalent. Yao's transformation is not security-preserving, i.e., the input to $g$ needs to be much larger than the input to $f$. Understanding whether a larger input is inherent is a long-standing open question.

In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of a strong OWF $g$ from a weak OWF $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, the input size of $g$ must grow as $\Omega(p(n))$. Here, direct product refers to the following structure: the construction $g$ executes some arbitrary pre-processing function (independent of $f$) on its input $s$, obtaining a vector $(x_1, \cdots, x_l)$, and outputs $f(x_1), \cdots, f(x_l)$. When setting the pre-processing to be the identity, one recovers thus Yao's construction.

Our result generalizes to functions $g$ with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong OWF hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense that post-processing of the outputs of $f$ is very lossy).

On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak OWFs by evaluating the OWF along a random walk on an expander graph – the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak OWF.

Bulletproofs are general-purpose Zero Knowledge Proof protocols that allow a Prover to demonstrate to a Verifier knowledge of a solution to a set of equations, represented as a Rank 1 Constraint System.

We present a protocol extending the standard Bulletproof protocol, which introduces a second layer of interactivity to the protocol, by allowing the Verifier to choose the set of equations after the Prover has already committed to portions of the solution.

We show that such Verifier-chosen (or stochastically-chosen) equation sets can be used to design smaller equation sets with less variables that have the same proving-power as their larger, deterministic counterparts but are, in practice, orders of magnitude faster both in proof generation and in proof verification, and even reduce the size of the resulting proofs. We demonstrate this with an example from a real-world application.

Our method maintains all the classical benefits of the Bulletproof approach: efficient proof generation, efficient proof checking, extremely short proofs, and the ability to use Fiat-Shamir challenges in order to turn an interactive proof into a non-interactive proof.

Proof-of-work (PoW) blockchain protocols based on directed acyclic graphs (DAGs) have demonstrated superior transaction confirmation performance compared to their chain-based predecessors. However, it is uncertain whether their security deteriorates in high-throughput settings similar to their predecessors, because their acceptance of simultaneous blocks and complex block dependencies presents challenges for rigorous security analysis.

We address these challenges by analyzing DAG-based protocols via a congestible blockchain model (CBM), a general model that allows case-by-case upper bounds on the block propagation delay, rather than a uniform upper bound as in most previous analyses. CBM allows us to capture two key phenomena of high-throughput settings: (1) simultaneous blocks increase each other's propagation delay, and (2) a block can be processed only after receiving all the blocks it refers to. We further devise a reasonable adversarial block propagation strategy in CBM, called the late-predecessor attack, which exploits block dependencies to delay the processing of honest blocks. We then evaluate the security and performance of Prism and OHIE, two DAG-based protocols that aim to break the security-performance tradeoff, in the presence of an attacker capable of launching the late predecessor attack. Our results show that these protocols suffer from reduced security and extended latency in high-throughput settings similar to their chain-based predecessors.

In this work, we initiate a new conceptual line of attack on the fundamental question of how to generate hard problems. Motivated by the need for one-way functions in cryptography, we propose an information-theoretic framework to study the question of generating new provably hard one-way functions by composing functions that are easy to invert and evaluate, where each such easy function is modeled as a random oracles paired with another oracle that implements an inverse function.

The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient method for finding a good set of PNBs. A refined framework of key-recovery attack is then formalized for round-reduced ChaCha. The new techniques allow us to break 7.5 rounds of ChaCha without the last XOR and rotation, as well as to bring faster attacks on 6 rounds and 7 rounds of ChaCha.

Whether one-way functions (OWF) exist is arguably the most important problem in Cryptography, and beyond. While lots of candidate constructions of one-way functions are known, and recently also problems whose average-case hardness characterize the existence of OWFs have been demonstrated, the question of whether there exists some \emph{worst-case hard problem} that characterizes the existence of one-way functions has remained open since their introduction in 1976.

In this work, we present the first ``OWF-complete'' promise problem---a promise problem whose worst-case hardness w.r.t. $\BPP$ (resp. $\Ppoly$) is \emph{equivalent} to the existence of OWFs secure against $\PPT$ (resp. $\nuPPT$) algorithms. The problem is a variant of the Minimum Time-bounded Kolmogorov Complexity problem ($\mktp[s]$ with a threshold $s$), where we condition on instances having small ``computational depth''.

We furthermore show that depending on the choice of the threshold $s$, this problem characterizes either ``standard'' (polynomially-hard) OWFs, or quasi polynomially- or subexponentially-hard OWFs. Additionally, when the threshold is sufficiently small (e.g., $2^{O(\sqrt{n})}$ or $\poly\log n$) then \emph{sublinear} hardness of this problem suffices to characterize quasi-polynomial/sub-exponential OWFs.

While our constructions are black-box, our analysis is \emph{non- black box}; we additionally demonstrate that fully black-box constructions of OWF from the worst-case hardness of this problem are impossible. We finally show that, under Rudich's conjecture, and standard derandomization assumptions, our problem is not inside $\coAM$; as such, it yields the first candidate problem believed to be outside of $\AM \cap \coAM$, or even ${\bf SZK}$, whose worst case hardness implies the existence of OWFs.

Efficiently and securely removing encrypted redundant data with cross-user in the cloud is challenging. Convergent Encryption (CE) is difficult to resist dictionary attacks for its deterministic tag. Server-aided mechanism is against such attacks while it may exist collusion. Focus on multimedia data, this paper proposes an efficient and secure fuzzy deduplication system without any additional servers. We also propose a notion of preverification of label consistency to compensate for the irreparable post-verification loss. Compared with other fuzzy deduplication schemes, our work has apparent advantages in deduplication efficiency and security based on a natural data set.

NIST has recently selected CRYSTALS-Kyber as a new public key encryption and key establishment algorithm to be standardized. This makes it important to evaluate the resistance of CRYSTALS-Kyber implementations to side-channel attacks. Software implementations of CRYSTALS-Kyber have already been thoroughly analysed. The discovered vulnerabilities helped improve the subsequently released versions and promoted stronger countermeasures against side-channel attacks. In this paper, we present the first attack on a protected hardware implementation of CRYSTALS-Kyber. We demonstrate a practical message (shared key) recovery attack on the first-order masked FPGA implementation of Kyber-512 by Kamucheka et al. (2022) using power analysis based on the Hamming distance leakage model. The presented attack exploits a vulnerability located in the masked message decoding procedure which is called during the decryption step of the decapsulation. The message recovery is performed using a profiled deep learning-based method which extracts the message directly, without extracting each share explicitly. By repeating the same decapsulation process multiple times, it is possible to increase the success rate of full shared key recovery to 99%.

Idealized constructions in cryptography prove the security of a primitive based on the security of another primitive. The challenge of building a pseudorandom function (PRF) from a random permutation (RP) has only been recently tackled by Chen, Lambooij and Mennink [CRYPTO 2019] who proposed Sum of Even-Mansour (SoEM) with a provable beyond-birthday-bound security. In this work, we revisit the challenge of building a PRF from an RP. On the one hand, we describe Keyed Sum of Permutations (KSoP) that achieves the same provable security as SoEM while being strictly simpler since it avoids a key addition but still requires two independent keys and permutations. On the other hand, we show that it is impossible to further simplify the scheme by deriving the two keys with a simple linear key schedule as it allows a non-trivial birthday-bound key recovery attack. The birthday-bound attack is mostly information-theoretic, but it can be optimized to run faster than a brute-force attack.

We present a novel stateless zero-knowledge rollup (ZK-rollup) protocol with client-side validation called Intmax2. Our architecture distinctly diverges from existing ZK-rollup approaches since essentially all of the data availability and computational costs are shifted to the client-side as opposed to imposing heavy computational requirements on the rollup aggregators. Moreover, the data storage and computation in our approach is parallelizable for each user. Therefore, there are no specific nodes to validate the contents of transactions. In effect, only block producers, who periodically submit a Merkle tree root containing all the transactions, are necessary.

Recently, many cryptographic primitives such as homomorphic encryption (HE), multi-party computation (MPC) and zero-knowledge (ZK) protocols have been proposed in the literature which operate on prime field $\mathbb{F}_p$ for some large prime $p$. Primitives that are designed using such operations are called arithmetization-oriented primitives. As the concept of arithmetization-oriented primitives is new, a rigorous cryptanalysis of such primitives is yet to be done. In this paper, we investigate arithmetization-oriented APN functions. More precisely, we investigate APN permutations in the CCZ-classes of known families of APN power functions over prime field $\mathbb{F}_p$. Moreover, we present a new class of APN binomials over $\mathbb{F}_q$ obtained by modifying the planar function $x^2$ over $\mathbb{F}_q$. We also present a class of binomials having differential uniformity at most $5$ defined via the quadratic character over finite fields of odd characteristic. We give sufficient conditions for which this family of binomials is permutation. Computationally it is confirmed that the latter family contains new APN functions for some small parameters. We conjecture it to contain an infinite subfamily of APN functions.

REAMC Report-007(2023) ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption Roy S Wikramaratna (email: rwikramaratna@gmail.com) Abstract

The Additive Congruential Random Number (ACORN) generator is straightforward to implement; it has been demonstrated in previous papers to give rise to sequences with long period which can be proven from theoretical considerations to approximate to being uniform in up to k dimensions (for any given k).

The ACORN-QRE algorithm is a straightforward modification of ACORN which effectively avoids the linearity of the original algorithm, while preserving the uniformity of the modified sequence. It provides a new method for generating one-time pads that are resistant to attack either by current computers or by future computing developments, including quantum computers. The pads can use any alphabet (including both binary and alphanumeric) and can be used with a Vernam-type cypher to securely encrypt both files and communications.

This report explains how the ACORN-QRE algorithm works and provides evidence for the claim that the resulting one-time pads are inherently not susceptible to cryptanalysis and that they will remain secure against foreseeable developments in computing, including the potential development of quantum computers.

The ACORN-QRE algorithm is patented in the UK under Patent No. GB2591467; patent applied for in the US under Application No. 17/795632. The patents are owned by REAMC Limited, 4 Nuthatch Close, Poole, Dorset BH17 7XR, United Kingdom

Towards building more scalable blockchains, an approach known as data availability sampling (DAS) has emerged over the past few years. Even large blockchains like Ethereum are planning to eventually deploy DAS to improve their scalability. In a nutshell, DAS allows the participants of a network to ensure the full availability of some data without any one participant downloading it entirely. Despite the significant practical interest that DAS has received, there are currently no formal definitions for this primitive, no security notions, and no security proofs for any candidate constructions. For a cryptographic primitive that may end up being widely deployed in large real-world systems, this is a rather unsatisfactory state of affairs.

In this work, we initiate a cryptographic study of data availability sampling. To this end, we define data availability sampling precisely as a clean cryptographic primitive. Then, we show how data availability sampling relates to erasure codes. We do so by defining a new type of commitment schemes which naturally generalizes vector commitments and polynomial commitments. Using our framework, we analyze existing constructions and prove them secure. In addition, we give new constructions which are based on weaker assumptions, computationally more efficient, and do not rely on a trusted setup, at the cost of slightly larger communication complexity. Finally, we evaluate the trade-offs of the different constructions.

Efficient power management is critical for embedded devices, both for extending their lifetime and ensuring safety. However, this can be a challenging task due to the unpredictability of the batteries commonly used in such devices. To address this issue, dedicated Integrated Circuits known as "fuel gauges" are often employed outside of the System-On-Chip. These devices provide various metrics about the available energy source and are highly accurate. However, their precision can also be exploited by malicious actors to compromise platform confidentiality if the Operating System fails to intervene. Depending on the fuel gauge and OS configuration, several attack scenarios are possible. In this article, we focus on Android and demonstrate how it is possible to bypass application isolation to recover PINs entered in other processes.

YOSO-style MPC protocols (Gentry et al., Crypto'21), are a promising framework where the overall computation is partitioned into small, short-lived pieces, delegated to subsets of one-time stateless parties. Such protocols enable gaining from the security benefits provided by using a large community of participants where "mass corruption" of a large fraction of participants is considered unlikely, while keeping the computational and communication costs manageable. However, fully realizing and analyzing YOSO-style protocols has proven to be challenging: While different components have been defined and realized in various works, there is a dearth of protocols that have reasonable efficiency and enjoy full end to end security against adaptive adversaries.

The YOSO model separates the protocol design, specifying the short-lived responsibilities, from the mechanisms assigning these responsibilities to machines participating in the computation. These protocol designs must then be translated to run directly on the machines, while preserving security guarantees. We provide a versatile and modular framework for analyzing the security of YOSO-style protocols, and show how to use it to compile any protocol design that is secure against static corruptions of $t$ out of $c$ parties, into protocols that withstand adaptive corruption of $T$ out of $N$ machines (where $T/N$ is closely related to $t/c$, specifically when $t/c<0.5$, we tolerate $T/N \leq 0.29$) at overall communication cost that is comparable to that of the traditional protocol even when $c << N$.

Furthermore, we demonstrate how to minimize the use of costly non-committing encryption, thereby keeping the computational and communication overhead manageable even in practical terms, while still providing end to end security analysis. Combined with existing approaches for transforming stateful protocols into stateless ones while preserving static security (e.g. Gentry et al. 21, Kolby et al. 22), we obtain end to end security.

The BBS+ signature scheme is one of the most prominent solutions for realizing anonymous credentials. In particular, due to properties like selective disclosure and efficient protocols for creating and showing possession of credentials. In recent years, research in cryptography has increasingly focused on the distribution of cryptographic tasks to mitigate attack surfaces and remove single points of failure.

In this work, we present a threshold BBS+ protocol in the preprocessing model. Our protocol supports an arbitrary $t$-out-of-$n$ threshold and achieves non-interactive signing in the online phase. It relies on a new pseudorandom correlation-based offline protocol producing preprocessing material with sublinear communication complexity in the number of signatures. Both our offline and online protocols are actively secure under the Universal Composability framework. Finally, we estimate the concrete efficiency of our protocol, including an implementation of the online phase. The online protocol without network latency takes less than $15 ms$ for $t \leq 30$ and credentials sizes up to $10$. Further, our results indicate that the influence of $t$ on the online signing is insignificant, $< 6 \%$ for $t \leq 30$, and the overhead of the thresholdization occurs almost exclusively in the offline phase.

The Security and Privacy Research Unit at TU Wien (https://secpriv.wien) is offering a fully funded PhD position within the WWTF project “SCALE2: SeCure, privAte, and interoperabLe layEr 2” (https://www.wwtf.at/funding/programmes/ict/ICT22-045/) under the supervision of Dr. Georgia Avarikioti and Univ.-Prof. Dr. Matteo Maffei.
Your profile:

• Master degree in computer science or equivalent (degree completion by employment start)
• Background in security/blockchain is a plus
• Excellent English, communication, and teamwork skills

Your tasks:

• Conducting world-class research in the design and analysis of scaling protocols for blockchains
• Engaging in research collaborations
• Contributing to teaching blockchain technologies on Masters-level

We offer:

• The Security and Privacy group is internationally renowned, regularly publishes in top security venues, and consists of an international, diverse team with expertise in cryptography, security, privacy, and game theory
• An international English-speaking environment (German not required)
• Personal/professional development, flexible hours
• Central workplace location (U1/U2/U4 Karlsplatz)
• Creative environment in a top-ranked city in livability
• A competitive salary

TU Wien strongly advocates for women, especially in leadership roles, and encourages applications from females and individuals with special needs. If qualifications are equal, female applicants will be prioritized unless specific reasons favor a male candidate.
The application material should include:

• Motivation letter
• Bachelor/Master’s transcripts
• Publication list (if available)
• Curriculum vitae
• Contact information for two referees

Closing date for applications:

Contact: Interested candidates should send the application material to Matteo Maffei (matteo.maffei@tuwien.ac.at) and Georgia Avarikioti (georgia.avarikioti@tuwien.ac.at). Applications received by August 15th will receive full consideration, but applications will be accepted until the position is filled.

Mysten Labs believes that decentralized and open protocols are the bedrock of the internet of value. This is why at Mysten Labs, we are creating foundational infrastructure to accelerate the adoption of decentralized protocols based on blockchain technologies.

Mysten is looking for a Software Engineer who is interested in cryptographic protocols and their application to blockchain. This person would work with us to design, check and implement mission-critical algorithms on range of topics including; cryptographic primitives such as pairing-based cryptography, distributed cryptographic protocols such as signature aggregation and distributed key generation, and zero-knowledge building blocks such as vector commitments and accumulators. They would then put this cryptography into practice in order to realize the scalability required by the next generation of blockchain networks.

What You'll Have:

5+ years of experience in hands-on software engineering for cryptographic operations, such as signature schemes, accumulators, key management, data encryption and compression.

Understanding of fundamental cryptographic algorithms and underlying math for any of the following: hash functions, finite field arithmetic, polynomials (FFT) and elliptic curves.

Experience implementing high-performance and parallelizable protocols in languages such as Go, Rust Java, or C/C++.

Experience with tools, practices, and programming patterns for ensuring software correctness.

Experience implementing zk-SNARK circuits or proof systems (i.e., Groth16, Halo, Plonk, STARKs, Marlin) is considered a plus.

Understanding, research publications or hands-on experience in any of the following is considered a bonus: zero knowledge proofs, threshold signatures, multi-party computations, efficient accumulators, distributed randomness generation, auditing cryptographic software/smart contracts, lightweight and embedded cryptography.

Closing date for applications:

Contact: Please navigate to our job posting if you wish to apply: https://jobs.ashbyhq.com/mystenlabs/a3d0da5b-b3cb-45db-9aa8-dc89ba0cee5e

More information: https://jobs.ashbyhq.com/mystenlabs/a3d0da5b-b3cb-45db-9aa8-dc89ba0cee5e

The University of Birmingham's School of Computer Science continues to thrive during a period of sustained growth. We are inviting applications for full professorial positions [1]. If you are a leader with a passion for computer science (and in particular Cyber Security), this is an extraordinary opportunity to shape the future of our academic community.

Areas of interest include (but are not limited to) systems security, artificial intelligence, network/web security, as well as formal methods and cryptography.

As part of the University of Birmingham, you will have access to state-of-the-art facilities, world-class research centres (in particular the Centre for Cyber Security and Privacy [2]), and a growing network of academic and industry collaborations. Our commitment to diversity and inclusion ensures an inclusive and welcoming environment for all.

The deadline for applications is 30 July 2023. Please note that we reserve the right to close this vacancy early once a sufficient number of applications have been received.

[1] https://www.jobs.ac.uk/job/DBD093/chair-in-computer-science-school-of-computing-science-4-positions-102099

[2] https://www.birmingham.ac.uk/research/centre-for-cyber-security-and-privacy/index.aspx

Closing date for applications:

Contact: For further information, please contact Aad van Moorsel, a.vanmoorsel@bham.ac.uk. For informal enquiries regarding the Centre for Cyber Security and Privacy, please contact David Oswald (d.f.oswald@bham.ac.uk) and Mark Ryan (m.d.ryan@bham.ac.uk).

More information: https://www.jobs.ac.uk/job/DBD093/chair-in-computer-science-school-of-computing-science-4-positions-102099

The responsibilities of this exciting, varied role will include:

• Software security assessment of SoC/IC security architectures and security scope specifications

• Plan, track and execute process, specification as well as software implementation reviews

• Assessment of software security robustness and effectiveness of security mechanisms

• Work with engineering teams and security engineers to innovate solutions to security-related problems

• Manage the NXP’s software secure development lifecycle (SSDLC) applied on product developments to minimize security risks

• Work on continuous improvements to keep up with state-of-the-art security technologies

• Refine software security best practices to assure and efficient and effective application

• Provide consultation on specific areas of security expertise and on the application of the SSDLC

To ensure your successful performance in this role, the following is desired

• Finished a BSEE or MSEE preferred in Security Engineering or Software Engineering

• Have good understanding of embedded software design, programming, documentation, and testing

• Have experience in the design and development of secure software, focus on embedded systems or complete solutions

• Have experience in the security concept/design, thread analysis, risk/threat modelling and mitigation strategies

• Have professional knowledge of software languages (C, Java, Java Card, Python, Rust)

• Knowledge of security compliance and certification processes would be an advantage

• Be familiar with "state of the art" software tools, CI/CD, secure software engineering processes, IoT solutions and service (depending on area of expertise)

• Have excellent communication skills, are willing to listen and adapt

• Are a collaborator with strong soft skills, ideally experienced in multicultural and global working environment

Closing date for applications:

Contact:

Veronika von Hepperger

Senior Talent Acquisition Specialist

(veronika.vonhepperger@nxp.com)