International Association
for Cryptologic Research

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. In the largest case, $N=511$ was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024-bit and 2048-bit integers. In our estimation, Shor's quantum circuit for factoring 1024-bit integers requires $2.78 \times 10^{11}$ gates, and with depth $2.24 \times 10^{11}$, while $2.23 \times 10^{12}$ gates, and with depth $1.80 \times 10^{12}$ for 2048-bit integers.

We study satisfiability modulo the theory of finite fields and give a decision procedure for this theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this theory, we construct SMT queries that verify the correctness of various zero knowledge proof compilers on various input programs. Our experiments show that our implementation is vastly superior to previous approaches (which encode field arithmetic using integers or bit-vectors).

Because of the rapid growth of Internet of Things (IoT), embedded systems have become an interesting target for experienced attackers. ESP32~\cite{tech-ref-man} is a low-cost and low-power system on chip (SoC) series created by Espressif Systems. The firmware extraction of such embedded systems is a real threat to the manufacturer as it breaks its intellectual property and raises the risk of creating equivalent systems with less effort and resources. In 2019, LimitedResults~\cite{LimitedResultsPown} published power glitch attacks which resulted in dumping secure boot and flash encryption keys stored in the eFuses of ESP32. Therefore, Espressif patched this vulnerability and then advised its customers to use ESP32-V3, which is an updated SoC revision. This new version is hardened against fault injection attacks in hardware and software as announced by Espressif~\cite{ESPpatch}. In this paper, we present for the first time a deep hardware security evaluation for ESP32-V3. The main goal of this evaluation is to extract the firmware encryption key stored in the eFuses. This evaluation includes Fault Injection (FI) and Side-Channel (SC) attacks. First, we use Electromagnetic FI (EMFI) in order to show that ESP32-V3 doesn't resist EMFI. However, by experimental results, we show that this version contains a revised bootloader compared to ESP32-V1, which hardens dumping the eFuse keys by FI. Second, we perform a full SC analysis on the AES accelerator of ESP32-V3. We show that an attacker with a physical access to the device can extract all the keys of the hardware AES-256 after collecting 60K power measurements during the execution of the AES block. Third, we present another SC analysis for the firmware decryption mechanism, by targeting the decryption operation during the power up. Using this knowledge, we demonstrate that the full 256-bit AES firmware encryption key, which is stored in the eFuses, can be recovered by SC analysis using 300K power measurements. Finally, we apply practically the firmware encryption attack on Jade hardware wallet \cite{jade}.

Recent years have witnessed a push to bring multi-party computation (MPC) to practice and make it accessible to the end user/programmer. Despite novel ideas, on frontend language design (e.g., Wysteria, Viaduct), backend protocol design and implementation (e.g., ABY, MOTION), or both (e.g., SPDZ), classical compiler optimizations remain largely under-utilized (if not completely unused) in MPC programming. A likely reason is that such optimizations are often applied on a middle-end intermediate representation such as SSA.

We put forth a methodology for an MPC programming compilation toolchain, which by mimicking the compilation methodology of standard imperative languages enables middle-end optimizations on MPC, yielding significant improvements. To this direction we devise an MPC circuit compiler that allows MPC programming in what is essentially Python, and inherits the structure (and therefore optimization opportunities) of the classical compilation pipeline. Our key conceptual contribution is advancing an intermediate language, which we call MPC-IR, that can be viewed as the analogue, in an MPC program’s compilation, of (enriched) SSA form. MPC-IR is a particularly appealing intermediate language as it allows backend-independent optimizations, a close analogy to machine independent optimizations in classical compilers. Demonstrating the power of our approach, we focus on a specific backend-independent optimization, SIMD-vectorization: We devise a novel classical-compiler-inspired automatic SIMD-vectorization on MPC-IR, which we show leads to significant speedup in circuit generation time and running time, as well as significant reduction in communication size and number of gates over the corresponding iterative schedule.

We implement and benchmark our compiler from a Python-like program to an optimized circuit that can be fed into an MPC backend (for our benchmarks we make use of the MOTION backend for MPC). We view our exhaustive benchmarks as both a way to validate our optimization and end-to-end compiler, and as a contribution, by itself, to a more complete benchmarks suite for MPC programming—such benchmarks suites are common in classical compilers.

We initiate a formal study of individual cryptography Informally speaking, an algorithm Alg is individual if in every implementation of Alg there always exists an individual user that has full knowledge of the cryptographic secrets S used by Alg. In particular, it should be infeasible to design implementations of this algorithm that would hide the secret S by distributing it between a group of parties using an MPC protocol, or via outsourcing it to a trusted execution environment.

This paper describes a formalization of the specification and the algorithm of the public key encryption scheme CRYSTALS-KYBER as well as the verification of its $\delta$-correctness and indistinguishability under chosen plaintext attack (IND-CPA) security proof. The algorithms and proofs were formalized with only minimal assumptions in a modular way to verify the proofs for all possible parameter sets. During the formalization in this flexible setting, problems in the correctness proof were uncovered. Furthermore, the security of CRYSTALS-KYBER under IND-CPA was verified using a game-based approach. As the security property does not hold for the original version of CRYSTALS-KYBER, we only show the IND-CPA security for the latest versions. The security proof was verified under the hardness assumption of the module Learning-with-Errors Problem. The formalization was realized in the theorem prover Isabelle and is foundational.

As the number of blockchain projects grows, efficient cross-chain interoperability becomes more necessary. A common cross-chain protocol is the two-way peg, which is typically used to transfer assets between blockchains and their sidechains. The criticality of cross-chain protocols require that they are designed with strong security models, which can reduce usability in the form of long transfer times. In this paper, we present Flyover, a repayment protocol to speed up the transfer of bitcoins over federated pegs by allowing untrusted liquidity providers to advance funds for the users. Transfer times are reduced because liquidity providers do not have the same security requirements as the underlying cross-chain protocol. We illustrate the Flyover protocol on the cross-chain interoperability protocol that connects Bitcoin to the RSK sidechain and show how Flyover can reduce transfer times without reducing security. In addition to this, Flyover extends the cross-chain protocol by allowing liquidity providers to make smart contract calls on RSK on behalf of the user.

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.

We propose a single-tiered hybrid Proof-of-Work consensus protocol to encourage decentralization in bitcoin. Our new mechanism comprises coupled puzzles of which properties differ from each other; the one is the extant outsourceable bitcoin puzzle while the other is non-outsourceable. Our new protocol enables miners to solve either puzzle as they want; therefore, blocks can be generated by either puzzle. Our hybrid consensus can be successfully implemented in bitcoin, because it is backward-compatible with existing bitcoin mining equipment(more precisely, existing bitcoin mining ASICs)

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM queries is necessary assuming $O(1)$ client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

Flow is a high-throughput blockchain with a dedicated step for executing the transactions in a block and a subsequent verification step performed by Verification Nodes. To enforce integrity of the blockchain, the protocol requires a component that prevents Verification Nodes from approving execution results without checking. In our preceding work, we have sketched out an approach called Specialized Proof of Confidential Knowledge (SPoCK). Using SPoCK, nodes can provide evidence to a third party that they both executed the same transaction sequence without revealing the resulting execution trace. The previous Flow white paper presented a basic implementation of such scheme. In this note, we introduce a new SPoCK implementation that is more concise and more efficient than the previous proposal. We first provide a formal generic description of a SPoCK scheme as well as its security definition. Then we propose a new construction of SPoCK based on the BLS signature scheme. We support the new scheme with its proof of security under the appropriate computation assumptions.

Encryption alone is not enough for secure end-to-end encrypted messaging: a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components: (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store.

To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed ''compaction'', as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks.

The private heavy-hitters problem is a data-collection task where many clients possess private bit strings, and data-collection servers aim to identify the most popular strings without learning anything about the clients' inputs. The recent work of Poplar constructed a protocol for private heavy hitters but their solution was susceptible to additive attacks by a malicious server, compromising both the correctness and the security of the protocol.

In this paper, we introduce PLASMA, a private analytics framework that addresses these challenges by using three data-collection servers and a novel primitive, called verifiable incremental distributed point function (VIDPF). PLASMA allows each client to non-interactively send a message to the servers as its input and then go offline. Our new VIDPF primitive employs lightweight techniques based on efficient hashing and allows the servers to non-interactively validate client inputs and preemptively reject malformed ones.

PLASMA drastically reduces the communication overhead incurred by the servers using our novel batched consistency checks. Specifically, our server-to-server communication depends only on the number of malicious clients, as opposed to the total number of clients, yielding a $182\times$ and $235\times$ improvement over Poplar and other state-of-the-art sorting-based protocols respectively. Compared to recent works, PLASMA enables both client input validation and succinct communication, while ensuring full security. At runtime, PLASMA computes the 1000 most popular strings among a set of 1 million client-held 32-bit strings in 67 seconds and 256-bit strings in less than 20 minutes respectively.

The increasing popularity of blockchain technology has affected the way we view many fields related to computer science, with E-commerce being no exception. The distributed nature and transparency of blockchain-based systems is one of its main perks, but it also raises some issues when it comes to privacy. Zero-knowledge proofs are very powerful building blocks when it comes to building privacy-preserving protocols, so, naturally, they have attracted a lot of attention in the last years. Following the recent collapse of the very popular crypto exchange FTX, we believe it is important to analyse how such events can be prevented in the future. This paper aims to highlight solutions that use zero-knowledge to prove solvency.

Blockchain is a newly emerging technology, however, it has proven effective in many applications because it provides multiple advantages, mainly as it represents a trust system in which data is encrypted in a way that cannot be tampered with or forged. Because it contains many details such as smart contracts, consensus, authentication, etc. the blockchain is a fertile ground for researchers where they can continually improve previous versions of these concepts. This paper introduces a new multi-signature scheme based on RSA. This scheme is designed to reduce the blockchain's size and prevent known attacks and is also applicable in many other settings that require multi-signatures. Our scheme is in the plain public key model, which means nodes do not need to prove knowledge or possession of their private key. In which, whatever the number of signers, the final signature size is equal to $O(k)$ where $k$ is a security parameter and no interaction between signers is needed. To verify that a number of parties have signed a shared message $m$, a verifier needs the signature, list of signers, and the message $m$. The presented practical short accountable-subgroup multi-signature (ASM) scheme allows a valid signature to disclose which subset generated the signature. It is worth noting that our multi-signatures with public key aggregation is an interactive two-round protocol and a multi-signature model applied to the entire block and not to individual transactions.

Visa Research is a growing group within Visa. We are located in the Palo Alto. The team itself is highly collaborative, working together not only on projects and research but also known to go hiking and have lunch together. 

Currently, we focus on building research teams in key areas: Data Analytics, Cryptography, and Future of Payment(Blockchain), and Artificial Intelligence. We are looking for outstanding researcher interns as part of the growing team! 

Visa Research’s goal of security is to enable policy-enforced, full lifecycle protection for data at rest, in transit and during computation for all payment-related scenarios. We accomplish this through fundamental and applied research in the areas of security and cryptography.

The internship will focus on developing new and impactful research in the chosen area. You will work closely with our team members to define and solve a state of the art research problem. In most cases, the final deliverable will be a research publication at a top-tier conference. Candidates should be able to demonstrate research proficiency (eg existing publications) and be able to perform research in both a group and self-guided setting.

Specific areas of interest include :

• Post Quantum Cryptography
• Quantum Cryptography
• Secure Multiparty Computation
• Zero Knowledge Proofs
• Blockchain & Consensus Protocols

Closing date for applications:

Contact: perindal@visa.com

More information: https://jobs.smartrecruiters.com/Visa/743999878021251-intern-visa-research-phd-

The Information Security Research Group at University College London offers a full-time PhD position in applied cryptography under the supervision of Dr. Philipp Jovanovic. This 4-year position is fully funded and has a starting date of September/October 2023 or shortly thereafter.

The position provides an excellent opportunity for students to develop cryptographic tools to improve the privacy, scalability, and security of next-generation decentralized systems. Candidates with research interests in one or more of the following areas are particularly encouraged to apply: blockchains and cryptocurrencies, threshold cryptography, multiparty computation, zero-knowledge proofs, consensus, distributed systems, cryptoeconomics. Successful applicants will work in an exciting international environment, conduct cutting-edge research in the above-mentioned fields, and publish and present their results at top venues for research in blockchains, cryptography, and IT security.

Closing date for applications:

Contact: Philipp Jovanovic p.jovanovic@ucl.ac.uk

More information: https://www.notion.so/philipp-jovanovic/Fully-funded-PhD-Position-in-Applied-Cryptography-The-WebN-Scholarship-in-Information-Security-536378d8a85c4306b9a6c2b0cdf1eb1b

Applications are invited for a post of Research Associate (RA) to work on the R&D project titled "Construction of permutation polynomials, and computation of generalized differential and boomerang uniformities of some classes of functions over finite fields," sanctioned by the Science and Engineering Research Board (SERB), Govt. of India, for a period of three years. The RA will be initially appointed for a period of one year and may be extended for a maximum of three years depending on performance, which will be evaluated at the completion of each year. The post is purely temporary and co-terminus with the project.

Closing date for applications:

Contact: Sartaj Ul Hasan (sartaj.hasan[at]iitjammu.ac.in)

More information: https://www.iitjammu.ac.in/post/advt-IITJMU-RC-RP00141-2023-A-18-research-associate

The research focus of the Implementation Security group at the Faculty of Computer Science is on the security of implementations. A large part of our research is dedicated to hardware security, protection against physical attacks (side-channel analysis and fault-injection attacks), security analysis of real-world systems particularly internet of things, and efficient hardware and software implementation of cryptographic primitives including fully homomorphic encryption schemes. This includes various implementation platforms like ASICs, FPGAs, and micro-processors. The Implementation Security group is looking for excellent B.Sc. and M.Sc. graduates with outstanding grades and degrees in computer science, computer engineering, electrical engineering, and mathematics. In addition, we are looking for outstanding postdoctoral candidates from these fields.

Initially, we offer three-year fully funded positions for B.Sc. and M.Sc. graduates. The expectation is to work towards a doctorate. Postdoctoral positions are initially offered to two years. Both PhD and Postdoctoral positions are subject to extensions. The salary will be according to the remuneration group E 13 TV-L (full time).

Our offerings:

• Excellent research environment with award-winning scientists, Open team culture,
• Programs designed to support parents,
• Support measures for women in IT security,
• Excellent support for doctoral and postdoctoral researchers,
• Opportunities for academic and professional development,
• Budget for courses, conferences, equipment and international exchange

Please send your complete application documents in one single pdf file to: amir.moradi@rub.de. The required documents are: CV, transcript of records of BSc., transcript of records of MSc. (if applicable).

Closing date for applications:

Contact:

Prof. Amir Moradi

https://informatik.rub.de/impsec/personen/moradi/

More information: https://informatik.rub.de/impsec/

ARC (Australian Research Council) PhD scholarship is available at the University of Southern Queensland, Australia ---Research Area: Computer Network Security ---Scholarship Amount: AU$32,000 per year for 3 years Requirements:   Good research track record and skills.   English: IELTS >= 6.5 TOFEL: Paper-based, >= 570 Electronic or computer based, >= 230 Internet based, >= 90 ,Or meet the enrolment in an Australian University ---For more PhD enrolment information, please check out the link of https://www.unisq.edu.au/handbook/current/sciences/DPHD.html Contact: Professor Yan Li - Yan.Li@usq.edu.au

Closing date for applications:

Contact: Professor Yan Li with email: Yan.Li@usq.edu.au

More information: https://www.unisq.edu.au/handbook/current/sciences/DPHD.html