International Association
for Cryptologic Research

Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. SNARKs with desirable properties such as transparent setup are constructed in the random oracle model. However, using such SNARKs to construct PCD requires heuristically instantiating the oracle and using it in a non-black-box way. Chen, Chiesa and Spooner (EC'22) constructed SNARKs in the low-degree random oracle model, circumventing this issue, but instantiating their model in the real world appears difficult.

In this paper, we introduce a new model: the arithmetized random oracle model (AROM). We provide a plausible standard-model (software-only) instantiation of the AROM, and we construct PCD in the AROM, given only a standard-model collision-resistant hash function. Furthermore, our PCD construction is for arbitrary-depth compliance predicates. We obtain our PCD construction by showing how to construct SNARKs in the AROM for computations that query the oracle, given an accumulation scheme for oracle queries in the AROM. We then construct such an accumulation scheme for the AROM.

We give an efficient "lazy sampling" algorithm (an emulator) for the ARO up to some error. Our emulator enables us to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM. The algorithm is non-trivial, and relies on results in algebraic query complexity and the combinatorial nullstellensatz.

VC schemes provide a mechanism for verifying the output of a remotely executed program. These are used to support computing paradigms wherein a computationally restricted client, the Verifier, wishes to delegate work to a more powerful but untrusted server, the Prover. The Verifier wishes to detect any incorrect results, be they accidental or malicious. The current state-of-the-art is only close-to-practical, usually because of a computationally demanding setup which must be amortised across repeat executions. We present a VC scheme for verifying the output of arithmetic circuits with a small one-time setup, KGen, independent of the size of the circuit being verified, and a insignificantly small constant program specific setup, ProbGen. To our knowledge our VC scheme is the first built from the hardness of integer factoring, a standard cryptographic assumption. Our scheme has the added novelty that the proofs are simply the raw output of the target computation, and the Prover is in effect blind to the fact they are taking part in a VC scheme at all. Compared to related work our scheme comes at the cost of a more expensive, but still efficient, verification step. Verification is always practical, and the Prover workload is unchanged from unverified outsourced computation. Although our scheme has worse asymptotic performance than the state-of-the-art it is particularly well suited for verifying one-shot programs and the output of large integer polynomial evaluation.

Consider two participants who wish to each reveal some secret information to each other, but both will only reveal their secret if there is a guarantee that the other will do so too. Conventionally, whoever sends their secret first makes themselves vulnerable to the possibility that the other party will cheat and won’t send their secret in reply. Fair Exchange (FE) protocols are a class of cryptographic construction which allow an exchange like this to occur without either party making themselves vulnerable. It is widely believed that a trusted third party arbitrator is required to intervene in the case of a dispute. We present a FE protocol that allows two parties to exchange secrets, safe in the knowledge that either both secrets will be exchanged, or neither will; without the involvement of a third party. This construction requires that the parties run online interactive processes, with reasonable timeliness requirements on the messages. In this work we provide a scheme for swapping arbitrarily sized secrets with security that reduces to the strength of an underlying symmetric authenticated encryption scheme.

Conflict-free Replicated Data Types (CRDTs) are a very popular class of distributed data structures that strike a compromise between strong and eventual consistency. Ensuring the protection of data stored within a CRDT, however, cannot be done trivially using standard encryption techniques, as secure CRDT protocols would require replica-side computation. This paper proposes an approach to lift general-purpose implementations of CRDTs to secure variants using secure multiparty computation (MPC). Each replica within the system is realized by a group of MPC parties that compute its functionality. Our results include: i) an extension of current formal models used for reasoning over the security of CRDT solutions to the MPC setting; ii) a MPC language and type system to enable the construction of secure versions of CRDTs and; iii) a proof of security that relates the security of CRDT constructions designed under said semantics to the underlying MPC library. We provide an open-source system implementation with an extensive evaluation, which compares different designs with their baseline throughput and latency.

Despite offering numerous advantages, public decentralized cryptocurrencies such as Bitcoin suffer from scalability issues such as high transaction latency and low throughput. The vast array of so-called Layer-2 solutions tackling the scalability problem focus on throughput, and consider latency as a secondary objective. However, in the context of retail payments, instant finality of transactions is arguably a more pressing concern, besides the overarching concern for privacy.

In this paper, we provide an overlay network that allows privacy-friendly low latency payments in a retail market. Our approach follows that of a recent work called Snappy, which achieved low latency but exposed identities of customers and their transaction histories. Our construction ensures this data is kept private, while providing merchants with protection against double-spending attacks. Although our system is still based upon customers registering with a collateral, crucially this collateral is reusable over time.

The technical novelty of our work comes from randomness-reusable threshold encryption (RRTE), a cryptographic primitive we designed specifically for the following features: our construction provably guarantees payments to merchants, preserves the secret identity of honest customers and prevents their transactions from being linked. We also present an implementation of our construction, showing its capacity for fast global payments in a retail setting with a delay of less than 1 second.

The original NTRU cryptosystem from 1998 can be considered the starting point of the great success story of lattice-based cryptography. Modern NTRU versions like NTRU-HPS and NTRU-HRSS are round-3 finalists in NIST's selection process, and also Crystals-Kyber and especially Falcon are heavily influenced by NTRU. Coppersmith and Shamir proposed to attack NTRU via lattice basis reduction, and variations of the Coppersmith-Shamir lattice have been successfully applied to solve official NTRU challenges by Security Innovations, Inc. up to dimension $n=173$. In our work, we provide the tools to attack modern NTRU versions, both by the design of a proper lattice basis, as well as by tuning the modern BKZ with lattice sieving algorithm from the G6K library to NTRU needs. Let $n$ be prime, $\Phi_n := (X^n-1)/(X-1)$, and let $\mathbb{Z}_q[X]/(\Phi_n)$ be the cyclotomic ring. As opposed to the common belief, we show that switching from the Coppersmith-Shamir lattice to a basis for the cyclotomic ring provides benefits. To this end, we slightly enhance the LWE with Hints framework by Dachman-Soled, Ducas, Gong, Rossi with the concept of projections against almost-parallel hints. Using our new lattice bases, we set the first cryptanalysis landmarks for NTRU-HPS with $n \in [101,171]$ and for NTRU-HRSS with $n \in [101,211]$. As a numerical example, we break our largest HPS-171 instance using the cyclotomic ring basis within $83$ core days, whereas the Coppersmith-Shamir basis requires $172$ core days. We also break one more official NTRU challenges by Security Innovation, Inc., originally worth 1000\$, in dimension $n=181$ in $20$ core years.

MQ-Sign is a variant of the UOV singature scheme proposed by Shim et al. It has been suggested as a candidate for the standardization of post-quantum cryptography in Republic of Korea (known as KpqC). However, recently Aulbach et al. proposed a practical key recovery attack against MQ-Sign-RS and MQ-Sign-SS with a simple secret key $\mathcal{S}$. In this paper, we propose another attack that is valid for the case of a general secret key $\mathcal{S}$.

The neural-differential distinguisher proposed by Gohr boosted the development of neural aided differential attack. As another significant cryptanalysis technique, linear attack has not been developing as rapidly in combination with deep learning technology as differential attack. In 2020, Hou et al. proposed the first neural-linear attack with one bit key recovery on 3, 4 and 5-round DES and restricted multiple bits recovery on 4 rounds, where the effective bits in one plain-ciphertext pair are spliced as one data sample. In this paper, we compare the neural-linear cryptanalysis with neural-differential cryptanalysis and propose a new data preprocessing algorithm depending on their similarities and differences. We call the new data structure distribution data. Basing on it, we mount our key recovery on round-reduced DES—first, we raise the accuracy of the neural-linear distinguisher by about 50%. Second, our distinguisher improves the effectiveness of one bit key recovery against 3, 4 and 5-round DES than the former one, and attack 6-round DES with success rate of 60.6% using 2048 plain-ciphertext pairs. Third, we propose a real multiple bit key recovery algorithm, leading neural-linear attack from theory to practice.

In this work we are interested in evaluating the possibility of extracting information from radio-enabled embedded-systems from a long distance. That is, our focus is capturing information from sources in the micrometer to tens of centimeters scale, such as intra- or inter- device busses, board-level routing traces etc. Moreover, we focus on distances in the range of millimeters to tens of centimeters from the (on-chip or on-board) embedded-system Tx Antenna to the signal source. Side-channels denotes presence of information in illegitimate channels. Side-channel analysis (SCA) attacks typically require statistical analysis and many leakage traces, focusing on micrometer level signals (sources) which emanate direct Near-Field information up to centimeters-level distances. In the same context (Near-Field and micrometer-level) simple power analysis (SPA) like attacks typically extract either direct raw information from one or few leakages or utilize statistical analysis on various samples from the same trace, similarly to horizontal attacks. Lately, radio-enabled systems were shown to emanate to a large distance (Far-Field), information from micrometer level sources, such as CPU processing, through the RF Tx Antenna: so far, SCA-like statistical analysis were shown. On the other hand, various reports exist on direct information eavesdropping/ sniffing or data exfiltration, emanated from centimeter to tens of centimeters scale sources, e.g., SATA, USB, Power-lines, Serial interface, Air-Gap systems, Screens and even optical fibers. All these elements are typically being used as a source and a direct Tx Antenna (huge, several to tens of centimeters) of the sensitive information. These antennas typically transmit information to short distances and the decay is very steep (proportional to $r^{-2}$-$r^{-3}$ depending on various factors and models). To the best of our knowledge, we report here for the first time an alarming security challenge: any signal in the embedded system, from serial ports, DMA-controlled memory-access, JTAG and SPI interfaces, on-board signals with galvanic connection to the Tx Antenna-chip and \emph{on-board signals without galvanic connection to the Tx Antenna-chip itself, all leak direct information up to tens of centimeters from source to the Tx Antenna}. This alarming situation induce signal-integrity implications within the embedded system, and significant implications relating to device-isolation and user-isolation, it may also affect standards and specifications for e.g., electromagnetic compatibility (EMC), on-board signal shielding, electromagnetic and RF interference (EMI, RFI), cross-talk, and generally design-for-manufacturing (DFM) guidelines for both intra-IC and PCB board. We demonstrate such direct readout of signals with commercial and low-cost equipment indicating how problematic the situation is. The existence of such leakage is demonstrated both over an ultra-low-cost platform such as the nRF52832(nRF) embedded-system and on a more advanced ESP32-c3-devkitc-02 board which is far more widespread in ISM radio applications and meets certification like FCC and CE (as compared to the nRF device). We have constructed an experiment to demonstrate leakage scenarios from (1) on- and (2) off-chip, on-board or (3) signals without galvanic connection to the RF front-end chip, showing the severity of the leakage, repetitively and systematic nature of the phenomena over various devices. We further demonstrate how sophisticated adversaries can build a code-injection Gadget which can carry sensitive-data and modulate it to be best extracted by the RF-channel. The main observation we push forward is that unless concrete interference and isolation standards appear with security metrics in mind, which are significantly different than ones needed for communication, it would be hard to prevent such leakages.

Distributed Oblivious Random Access Memory (DORAM) is a secure multiparty protocol that allows a group of participants holding a secret-shared array to read and write to secret-shared locations within the array. The efficiency of a DORAM protocol is measured by the amount of communication and computation required per read/write query into the array. DORAM protocols are a necessary ingredient for executing Secure Multiparty Computation (MPC) in the RAM model.

Although DORAM has been widely studied, all existing DORAM protocols have focused on the setting where the DORAM servers are semi-honest. Generic techniques for upgrading a semi-honest DORAM protocol to the malicious model typically increase the asymptotic communication complexity of the DORAM scheme.

In this work, we present a 3-party DORAM protocol which requires $O((\kappa + D)\log N)$ communication and computation per query, for a database of size $N$ with $D$-bit values, where $\kappa$ is the security parameter. Our hidden constants in a big-O nation are small. We show that our protocol is UC-secure in the presence of a malicious, static adversary. This matches the communication and computation complexity of the best semi-honest DORAM protocol, and is the first malicious DORAM protocol with this complexity.

Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. This paper explains how this buffer overflow vulnerability in XKCP was found. More generally, we explore the application of formal methods to the five finalist submission packages to the NIST SHA-3 competition, allowing us to (re-)discover vulnerabilities in the implementations of Keccak and BLAKE, and also discover a previously undisclosed vulnerability in the implementation of Grøstl. We also show how the same approach rediscovers a vulnerability affecting 11 out of the 12 implemented cryptographic hash functions in Apple's CoreCrypto library. Our approach consists of removing certain lines of code and then using KLEE as a tool to prove functional equivalence. We discuss the advantages and limitations of our approach and hope that our attempt to consolidate some earlier approaches can lead to new insights.

Due to the significant development of the intelligence industry worldwide, various initiatives have increasingly recognized the value of the Internet of Things. IoT systems, however, are often hindered by fundamental challenges, such as the need for a central server to manage them. Decentralizing these systems can be achieved through the use of blockchains. Recently, there has been an increase in the popularity of blockchain in various fields, such as banking, Internet of Things, and intelligence industry, and human societies have taken notice of it. One of the main problems is with the scalability of such systems as the network size grows.

This paper examines how blockchain can assist IoT systems to overcome this challenge. We introduce a lightweight-scalable blockchain as a solution for the sharding nodes. This solution assigns nodes to shards according to their history of activity. As part of this study, an IGDBFT algorithm is introduced within the proposed scheme for intra-shard consensus. A solution to storing blocks and cross-shard transactions has been developed using a global chain containing parent blocks in the cloud layer. Finally, we analyze the security and efficiency of our scheme and compare our sharding-based protocol with previous protocols.

Central Bank Digital Currency (CBDC) is in the phase of discussion in most of countries. In this paper, we consider the security issues of centralized retail CBDC. Our focus is on the design and analysis of the underlying cryptographic protocol. The main security requirements against the protocol are transaction anonymity and protection against tax evasion. The protocol provides security guarantees in case of the strongest model of an execution environment which is the general concurrent environment. We apply the Universal Composition (UC) methodology of Canetti [3],[4]. At the time of this writing, we are not aware of any published CBDC protocol with an aim to provide secure compositional guarantees.

There are lots of Random Key Generators, In this paper, we gave a new construction of Randomized Bit Generator by using Algebraic number theory, which is quite easy to compute and also we keep the security of this generator in our mind. we discussed its applications as a secret key generator being a randomized bit generator in encryption schemes and hash functions. We tried to make it Quantumly secure by randomizing it and extending its parameters to see it as a Quantum Random key generator.

Organisation: The CRISES research group at Rovira i Virgili University is seeking to recruit a full-time postdoctoral researcher in computer security. The group focuses on theoretical advances for computer security and privacy, often in collaboration with industry and the government. The successful candidate will work in an exciting international campus located at the sunny and Mediterranean city of Tarragona, Spain. For further information please check: https://crises-deim.urv.cat/

Your role: The successful candidate is expected to contribute to the HERMES project, which focuses on supply chain security and data provenance. The post, however, offers the candidate the opportunity to develop their own research agenda within the area of security and privacy of software systems. The successful candidate will work under the direction of Dr. Rolando Trujillo together with other members of the CRISES research group. Candidates with experience in cryptographic protocols, threat modelling or formal verification are encouraged to apply.

Offer: The University offers a two-year employment that may be extended up to three years. The University offers highly competitive salaries and is an equal opportunity employer.

Applications: Applications will be considered on receipt until 15 Jun 2023 (closing date).

Closing date for applications:

Contact: Dr. Rolando Trujillo (rolando.trujillo@urv.cat)

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.cn

This paper introduces HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. A distinguishing aspect of HyperNova is that the prover’s cost at each step is dominated by a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme.

To construct HyperNova, we generalize folding schemes (CRYPTO 22), to allow instances from two (potentially) different NP relations, that share the same structure, to be folded; we refer to this generalization as multi-folding schemes. Furthermore, we devise a public-coin, multi-folding scheme for instances in CCS and linearized CCS (a variant of CCS that we introduce). This construction can be viewed as an “early stopping” version of Spartan (CRYPTO 20), applied to a carefully-crafted polynomial that includes claims about prior linearized CCS instances. The prover’s work in the multi-folding scheme is a linear number of finite field operations and the verifier’s work is a logarithmic number of finite field operations and a single group scalar multiplication. We then construct incrementally verifiable computation (IVC) from non-interactive multi-folding schemes with the lowest prover costs and the lowest recursion overheads in the literature. We also provide an alternate realization of HyperNova with a black box use of Nova, which nearly eliminates the need for deferred arithmetic when instantiated with a cycle of elliptic curves.

As an additional contribution, we describe nlookup, a lookup argument, that is particularly suited for recursive arguments based on folding schemes. Specifically, at a particular step in an incremental computation, for m lookups into a table of size $n$ $(m << n)$, the prover’s work is dominated by $O(n)$ finite field operations and it requires only $O(m \cdot \log{n})$ degree-2 constraints and $O(\log{n})$ hash evaluations in the incremental computation. nlookup is currently not suitable for efficiently encoding bitwise operations, but it provides a powerful tool for efficiently encoding (large) finite state machines and proving their transitions with recursive SNARKs.

Private messaging systems that use a bulletin board, like privacy-preserving blockchains, have been a popular topic during the last couple of years. In these systems, typically a private message is posted on the board for a recipient and the privacy requirement is that no one can determine the sender and the recipient of the message. Until recently, the efficiency of these recipients was not considered, and the party had to perform a naive scan of the board to retrieve their messages. More recently, works like Fuzzy Message Detection (FMD), Private Signaling (PS), and Oblivious Message Retrieval (OMR) have studied the problem of protecting recipient privacy by outsourcing the message retrieval process to an untrusted server. However, FMD only provides limited privacy guarantees, and PS and OMR greatly lack scalability.

In this work, we present a new construction for private signaling which is both asymptotically superior and concretely orders of magnitude faster than all prior works while providing full privacy. Our constructions make use of a trusted execution environment (TEE) and an Oblivious RAM to improve the computation complexity of the server. We also improve the privacy guarantees by keeping the recipient hidden even during the retrieval of signals from the server. Our proof-of-concept open-source implementation shows that for a server serving a hundred thousand recipients and ten million messages, it only takes $< 6$ milliseconds to process a sent message, and $< 200$ milliseconds to process a retrieval (of 100 signals) request from a recipient.

In this work, we initiate a study of $K$-NIKE protocols in the fine-grained setting, in which there is a polynomial gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of $K$-NIKE for $K \geq 3$. Our contribution is threefold. - We show that random oracles can be used to obtain fine-grained $K$-NIKE protocols for every constant $K$. In particular, we show how to generalize Merkle's two-party protocol to $K$ parties in such a way that the honest parties ask $n$ queries each, while the adversary needs $n^{K/(K-1)}$ queries to the random oracle to find the key. - We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup's generic group model with a quadratic gap between the number of queries by the honest parties vs. that of the adversary. - Finally, we show a limitation of using purely algebraic methods for obtaining $3$-NIKE. In particular, we show that any $n$-query $3$-NIKE protocol in Maurer's generic group model can be broken by a $O(n^2)$-query attacker. Maurer's GGM is more limited compared with Shoup's both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break $3$-NIKE protocols in Maurer's model with any polynomial number of queries.

Commitments are fundamental in cryptography. In the classical world, commitments are equivalent to the existence of one-way functions. It is also known that the most desired form of commitments in terms of their round complexity, i.e., non-interactive commitments, cannot be built from one-way functions in a black-box way [Mahmoody-Pass, Crypto'12]. However, if one allows the parties to use quantum computation and communication, it is known that non-interactive commitments (to classical bits) are in fact possible [Koshiba-Odaira, Arxiv'11 and Bitansky-Brakerski, TCC'21].

We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation and classical communication based on a black-box use of one-way functions. We prove that doing so is impossible unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto'22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC'21], as they only required a classical decommitment message. Because non-interactive commitments can be based on injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science'21] in which they only allowed the security reduction to be quantum.

At a technical level, we prove that sampling oracles at random from ``sufficiently large'' sets (of oracles) will make them one-way against polynomial quantum-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al.[Asiacrypt'19] and Chung et al. [FOCS'20].