[continued from previous message]

* Authors: Song Bian, Zian Zhao, Ruiyu Shen, Zhou Zhang, Ran Mao, Dawei Li, Yizhong Liu, Masaki Waga, Kohei Suenaga, Zhenyu Guan, Jiafeng Hua, Yier Jin, Jianwei Liu
* [Permalink](https://eprint.iacr.org/2024/1991)
* [Download](https://eprint.iacr.org/2024/1991.pdf)

### Abstract

This work proposes a multi-level compiler framework to transform programs with loop structures to efficient algorithms over fully homomorphic encryption (FHE). We observe that, when loops operate over ciphertexts, it becomes extremely challenging to
effectively interpret the control structures within the loop and construct operator cost models for the main body of the loop. Consequently, most existing compiler frameworks have inadequate support for programs involving non-trivial loops, undermining
the expressiveness of programming over FHE. To achieve both efficient and general program execution over FHE, we propose CHLOE, a new compiler framework with multi-level control-flow analysis for the effective optimization of compound repetition control
structures. We observe that loops over FHE can be classified into two categories depending on whether the loop condition is encrypted, namely, the transparent loops and the oblivious loops. For transparent loops, we can directly inspect the control
structures and build operator cost models to apply FHE-specific loop segmentation and vectorization in a fine-grained manner. Meanwhile, for oblivious loops, we derive closed-form expressions and static analysis techniques to reduce the number of
potential loop paths and conditional branches. In the experiment, we show that \NAME can compile programs with complex loop structures into efficient executable codes over FHE, where the performance improvement ranges from $1.5\times$ to $54\times$ (up
to $10^{5}\times$ for programs containing oblivious loops) when compared to programs produced by the-state-of-the-art FHE compilers.



## 2024/1992

* Title: Improved Quantum Linear Attacks and Application to CAST
* Authors: Kaveh Bashiri, Xavier Bonnetain, Akinori Hosoyamada, Nathalie Lang, André Schrottenloher
* [Permalink](https://eprint.iacr.org/2024/1992)
* [Download](https://eprint.iacr.org/2024/1992.pdf)

### Abstract

This paper studies quantum linear key-recovery attacks on block ciphers.
The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC
2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum \emph{correlation state}
, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily.

In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying
our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon's algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon
attacks.



## 2024/1993

* Title: BOIL: Proof-Carrying Data from Accumulation of Correlated Holographic IOPs
* Authors: Tohru Kohrita, Maksim Nikolaev, Javier Silva
* [Permalink](https://eprint.iacr.org/2024/1993)
* [Download](https://eprint.iacr.org/2024/1993.pdf)

### Abstract

In this paper, we present a batching technique for oracles corresponding to codewords of a Reed–Solomon code. This protocol is inspired by the round function of the STIR protocol (CRYPTO 2024). Using this oracle batching protocol, we propose a
construction of a practically efficient accumulation scheme, which we call BOIL. Our accumulation scheme can be initiated with an arbitrary correlated holographic IOP, leading to a new class of PCD constructions. The results of this paper were originally
given as a presentation at zkSummit12.



## 2024/1994

* Title: Token-Based Key Exchange - Non-Interactive Key Exchange meets Attribute-Based Encryption
* Authors: Elsie Mestl Fondevik, Kristian Gjøsteen
* [Permalink](https://eprint.iacr.org/2024/1994)
* [Download](https://eprint.iacr.org/2024/1994.pdf)

### Abstract

In this paper we define the novel concept token-based key exchange (TBKE), which can be considered a cross between non-interactive key exchange (NIKE) and attribute-based encryption (ABE). TBKE is a scheme that allows users within an organization to
generate shared keys for a subgroup of users through the use of personal tokens and secret key. The shared key generation is performed locally and no interaction between users or with a server is needed.

The personal tokens are derived from a set of universal tokens and a master secret key which are generated and stored on a trusted central server. Users are only required to interact with the server during setup or if new tokens are provided. To reduce
key escrow issues the server can be erased after all users have received their secret keys. Alternatively, if the server is kept available TBKE can additionally provide token revocation, addition and update.

We propose a very simple TBKE protocol using bilinear pairings.
The protocol is secure against user coalitions based upon a novel hidden matrix problem. The problems requires an adversary to compute where the adversary must compute a matrix product in the exponent, where some components are given in the clear and
others are hidden as unknown exponents. We argue that the hidden matrix problem is as hard as dLog in the bilinear group model.



## 2024/1995

* Title: BitVM: Quasi-Turing Complete Computation on Bitcoin
* Authors: Lukas Aumayr, Zeta Avarikioti, Robin Linus, Matteo Maffei, Andrea Pelosi, Christos Stefo, Alexei Zamyatin
* [Permalink](https://eprint.iacr.org/2024/1995)
* [Download](https://eprint.iacr.org/2024/1995.pdf)

### Abstract

A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby
being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments.

In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script, without introducing any language modification or additional security assumptions, such as trusted
hardware, trusted parties, or committees with secure majority. In particular, we present $\mathsf{BitVM}$, a two-party protocol realizing a generic virtual machine by a combination of cryptographic and incentive mechanisms. We conduct a formal analysis
of $\mathsf{BitVM}$, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach: in the optimistic case (i.e., in the absence of disputes between parties), our protocol requires
just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. This work not only solves a long-standing theoretical problem, but it also promises a strong
practical impact, enabling the development of complex applications in Bitcoin.



## 2024/1996

* Title: A Framework for Generating S-Box Circuits with Boyer-Peralta Algorithm-Based Heuristics, and Its Applications to AES, SNOW3G, and Saturnin
* Authors: Yongjin Jeon, Seungjun Baek, Giyoon Kim, Jongsung Kim
* [Permalink](https://eprint.iacr.org/2024/1996)
* [Download](https://eprint.iacr.org/2024/1996.pdf)

### Abstract

In many lightweight cryptography applications, low area and latency are required for efficient implementation. The gate count in the cipher and the circuit depth must be low to minimize these two metrics. Many optimization strategies have been developed
for the linear layer, led by the Boyer-Peralta (BP) algorithm. The Advanced Encryption Standard (AES) has been a focus of extensive research in this area. However, while the linear layer uses only XOR gates, the S-box, which is an essential nonlinear
component in symmetric cryptography, uses various gate types, making optimization challenging, particularly as the bit size increases.

In this paper, we propose a new framework for a heuristic search to optimize the circuit depth or XOR gate count of S-box circuits. Existing S-box circuit optimization studies have divided the nonlinear and linear layers of the S-box, optimizing each
separately, but limitations still exist in optimizing large S-box circuits. To extend the optimization target from individual internal components to the entire S-box circuit, we extract the XOR information of each node in the target circuit and
reconstruct the nodes based on nonlinear gates. Next, we extend the BP algorithm-based heuristics to address nonlinear gates and incorporate this into the framework. It is noteworthy that the effects of our framework occur while maintaining the AND gate
count and AND depth without any increase.

To demonstrate the effectiveness of the proposed framework, we apply it to the AES, SNOW3G, and Saturnin S-box circuits. Our results include depth improvements by about 40% and 11% compared to the existing AES S-box [BP10] and Saturnin super S-box [CDL+
20] circuits, respectively. We implement a new circuit for the SNOW3G S-box, which has not previously been developed, and apply our framework to reduce its depth. We expect the proposed framework to contribute to the design and implementation of various
symmetric-key cryptography solutions.



## 2024/1997

* Title: On format preserving encryption with nonce
* Authors: Alexander Maximov, Jukka Ylitalo
* [Permalink](https://eprint.iacr.org/2024/1997)
* [Download](https://eprint.iacr.org/2024/1997.pdf)

### Abstract

In this short paper we consider a format preserving encryption when a nonce is available. The encryption itself mimics a stream cipher where the keystream is of a (non-binary) radix $R$. We give a few practical and efficient ways to generate such a
keystream from a binary keystream generator.



## 2024/1998

* Title: Impossible Differential Automation: Model Generation and New Techniques
* Authors: Emanuele Bellini, Paul Huynh, David Gerault, Andrea Visconti, Alessandro De Piccoli, Simone Pelizzola
* [Permalink](https://eprint.iacr.org/2024/1998)
* [Download](https://eprint.iacr.org/2024/1998.pdf)

### Abstract

In this paper, we aim to enhance and automate advanced techniques for impossible differential attacks. To demonstrate these advancements, we present improved attacks on the LBlock and HIGHT block ciphers. More precisely, we
(a) introduce a methodology to automatically invert symmetric ciphers when represented as directed acyclic graphs, a fundamental step in the search for impossible differential trails and in key recovery techniques;
(b) automate the search for impossible differential distinguishers, reproducing recent techniques and results;
(c) present a new hybrid model combining cell-wise properties and bit-wise granularity;
(d) integrate these techniques in the automated tool CLAASP;
(e) demonstrate the effectiveness of the tool by
reproducing a state-of-the-art 16-round impossible differential for LBlock previously obtained using a different technique and
exhibiting a new 18-round improbable trail;
(f) improve the state-of-the-art single-key recovery of HIGHT for 27 rounds, by automating the use of hash tables to current state-of-the-art results.



## 2024/1999

* Title: Multivariate Encryptions with LL’ perturbations - Is it possible to repair HFE in encryption? -
* Authors: Jacques Patarin, Pierre Varjabedian
* [Permalink](https://eprint.iacr.org/2024/1999)
* [Download](https://eprint.iacr.org/2024/1999.pdf)

### Abstract

We will present here new multivariate encryption algorithms. This is interesting since few multivariate encryption scheme currently exist, while their exist many more multivariate signature schemes. Our algorithms will combine several ideas, in
particular the idea of the LL’ perturbation originally introduced, but only for signature, in [GP06]. In this paper, the LL’ perturbation will be used for encryption and will greatly differ from [GP06]. As we will see, our algorithms resists to all
known attacks (in particular Gröbner attacks and MinRank attacks) and have reasonable computation time.



## 2024/2000

* Title: Evasive LWE Assumptions: Definitions, Classes, and Counterexamples
* Authors: Chris Brzuska, Akin Ünal, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2024/2000)
* [Download](https://eprint.iacr.org/2024/2000.pdf)

### Abstract

The evasive LWE assumption, proposed by Wee [Eurocrypt'22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to
obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work,
we initiate a more systematic study on evasive LWE assumptions:
(i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto'22 Tsabary, Asiacrypt'22 VWW, Crypto'23 ARYY] respectively, showing that these assumptions are unlikely to hold.
(ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples.
(iii) We show that under our assumption formulations, the security proofs of [Asiacrypt'22 VWW] and [Crypto'23 ARYY] can be recovered, and we reason why the security proof of [Crypto'22 Tsabary] is also plausibly repairable using an appropriate evasive
LWE assumption.



## 2024/2001

* Title: Xiezhi: Toward Succinct Proofs of Solvency
* Authors: Youwei Deng, Jeremy Clark
* [Permalink](https://eprint.iacr.org/2024/2001)
* [Download](https://eprint.iacr.org/2024/2001.pdf)

### Abstract

A proof of solvency (or proof of reserves) is a zero-knowledge proof conducted by centralized cryptocurrency exchange to offer evidence that the exchange owns enough cryptocurrency to settle each of its users' balances. The proof seeks to reveal nothing
about the finances of the exchange or its users, only the fact that it is solvent. The literature has already started to explore how to make proof size and verifier time independent of the number of (i) users on the exchange, and (ii) addresses used by
the exchange. We argue there are a few areas of improvement. First, we propose and implement a full end-to-end argument that is fast for the exchange to prove (minutes), small in size (KBs), and fast to verify (seconds). Second, we deal with the natural
conflict between Bitcoin and Ethereum's cryptographic setting (secp256k1) and more ideal settings for succinctness (e.g., pairing-based cryptography) with a novel mapping approach. Finally, we discuss how to adapt the protocol to the concrete parameters
of bls12-381 (which is relevant because the bit-decomposition of all user balances will exceed the largest root of unity of the curve for even moderately-sized exchanges).



## 2024/2002

* Title: Improving Differential-Neural Distinguisher For Simeck Family
* Authors: Xue Yuan, Qichun Wang
* [Permalink](https://eprint.iacr.org/2024/2002)
* [Download](https://eprint.iacr.org/2024/2002.pdf)

### Abstract

In CRYPTO 2019, Gohr introduced the method of differential neural cryptanalysis, utilizing neural networks as the underlying distinguishers to achieve distinguishers for (5-8)-round of the Speck32/64 cipher and subsequently recovering keys for 11 and 12
rounds. Inspired by this work, we propose an enhanced neural cryptanalysis framework that combines the Efficient Channel Attention (ECA) module with residual networks. By introducing the channel attention mechanism to emphasize key features and
leveraging residual networks to facilitate efficient feature extraction and gradient flow, we achieve improved performance. Additionally, we employ a new data format that combines the ciphertext and the penultimate round ciphertext as input samples,
providing the distinguisher with more useful features. Compared with the known results, our work enhance the accuracy of the neural distinguishers for Simeck32/64 (10-12)-round and achieve a new 13-round distinguisher. We also improve the accuracy of the
Simeck48/96 (10-11)-round distinguishers and develop new (12-16)-round neural distinguishers. Moreover, we enhance the accuracy of the Simeck64/128 (14-18)-round distinguishers and obtain a new 19-round neural distinguisher. As a result, we achieve the
highest accuracy and the longest rounds distinguishers for Simeck32/64, Simeck48/96, and Simeck64/128.



## 2024/2003

* Title: Exploring the Optimal Differential Characteristics of SM4 (Full Version): Improving Automatic Search by Including Human Insights
* Authors: Bingqing Li, Ling Sun
* [Permalink](https://eprint.iacr.org/2024/2003)
* [Download](https://eprint.iacr.org/2024/2003.pdf)

### Abstract

This study aims to determine the complete and precise differential properties of SM4, which have remained unknown for over twenty years after the cipher was initially released. A Boolean Satisfiability Problem (SAT) based automatic search approach is
employed to achieve the objective. To improve the limited efficiency of the search focused on differential probabilities, we want to investigate the feasibility of integrating human expertise into an automatic approach to enhance the search speed. This
study presents the construction of four new SAT models that describe the human-identified specific properties of short differential characteristics. All of these models are integrated into the fundamental model, and the SAT solver is implemented to
assess the acceleration capabilities of the new models. The experimental results indicate that including three new models effectively decreases the overall execution time of the SAT solver. Using the novel models, we obtain the first precise minimal
values for the number of active S-boxes of SM4 under single-key (complete rounds) and related-key (1-round to 19-round) settings. The first precise upper bound for differential probabilities of SM4 (1-round to 20-round) is also determined. In addition,
we present the first publicly revealed optimal 19-round differential characteristic of SM4.



## 2024/2004

* Title: Regev's attack on hyperelliptic cryptosystems
* Authors: Razvan Barbulescu, Gaetan Bisson
* [Permalink](https://eprint.iacr.org/2024/2004)
* [Download](https://eprint.iacr.org/2024/2004.pdf)

### Abstract

Hyperelliptic curve cryptography (HECC) is a candidate to standardization which is a competitive alternative to elliptic curve cryptography (ECC). We extend Regev's algorithm to this setting. For genus-two curves relevant to cryptography, this yields a
quantum attack up to nine times faster than the state-of-the-art. This implies that HECC is slightly weaker than ECC. In a more theoretical direction, we show that Regev's algorithm obtains its full speedup with respect to Shor's when the genus is high,
a setting which is already known to be inadequate for cryptography.



## 2024/2005

* Title: Post-Quantum Secure Channel Protocols for eSIMs
* Authors: Luk Bettale, Emmanuelle Dottax, Laurent Grémy
* [Permalink](https://eprint.iacr.org/2024/2005)
* [Download](https://eprint.iacr.org/2024/2005.pdf)

### Abstract

The transition to Post-Quantum (PQ) cryptography is increasingly mandated by national agencies and organizations, often involving a phase where classical and PQ primitives are combined into hybrid solutions. In this context, existing protocols must be
adapted to ensure quantum resistance while maintaining their security goals. These adaptations can significantly impact performance, particularly on embedded devices.
In this article, we focus on standardized protocols which support application management on eSIMs across different modes. This is a complex use-case, involving constrained devices with stringent security requirements. We present PQ adaptations, including
both hybrid and fully PQ versions, for all modes. Using ProVerif, we provide automated proofs that verify the security of these PQ variants. Additionally, we analyze the performance impact of implementing PQ protocols on devices, measuring runtime and
bandwidth consumption. Our findings highlight the resource overhead associated with achieving post-quantum security for eSIM management.



## 2024/2006

* Title: Data Decryption and Analysis of Note-Taking Applications
* Authors: Seyoung Yoon, Myungseo Park, Kyungbae Jang, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/2006)
* [Download](https://eprint.iacr.org/2024/2006.pdf)

### Abstract

As smartphone usage continues to grow, the demand for note-taking applications, including memo and diary apps, is rapidly increasing. These applications often contain sensitive information such as user schedules, thoughts, and activities, making them key
targets for analysis in digital forensics. Each year, new note-taking applications are released, most of which include lock features to protect user data. However, these security features can create challenges for authorized investigators attempting to
access and analyze application data. This paper aims to support investigators by conducting a static analysis of Android-based note-taking applications. It identifies how and where data is stored and explains methods for extracting and decrypting
encrypted data. Based on the analysis, the paper concludes by proposing future research directions in the field of digital forensics.



## 2024/2007

* Title: A Combinatorial Attack on Ternary Sparse Learning with Errors (sLWE)
* Authors: Abul Kalam, Santanu Sarkar, Willi Meier
* [Permalink](https://eprint.iacr.org/2024/2007)
* [Download](https://eprint.iacr.org/2024/2007.pdf)

### Abstract

Sparse Learning With Errors (sLWE) is a novel problem introduced at Crypto 2024 by Jain et al., designed to enhance security in lattice-based cryptography against quantum attacks while maintaining computational efficiency. This paper presents the first
third-party analysis of the ternary variant of sLWE, where both the secret and error vectors are constrained to ternary values. We introduce a combinatorial attack that employs a subsystem extraction technique followed by a Meet-in-the-Middle approach,
effectively recovering the ternary secret vector. Our comprehensive analysis explores the attack's performance across various sparsity and modulus settings, revealing critical security limitations inherent in ternary sLWE.

Our analysis does not claim to present any attack on the proposal of Jain et al.; rather, it supports their assertion that sparse LWE is vulnerable for small secrets, particularly for ternary secrets and ternary errors. Notably, our findings indicate
that the recommended parameters, which the developers claim provide security equivalent to LWE with a dimension of 1024, may not hold true for the ternary variant of sLWE.
Our research highlights that, particularly with a modulus of $2^{64}$, the secret key can be recovered in a practical timeframe, supporting the developers' claim of vulnerability in this case. Additionally, for configurations with moduli of $2^{32}$ and $
2^{16}$, we observe a significant reduction in the security margin. This suggests that the actual security level may be significantly weaker than intended. Overall, our work contributes crucial insights into the cryptographic robustness of ternary sLWE,
emphasizing the need for further strengthening to protect against potential attacks and setting the stage for future research in this area.



## 2024/2008

* Title: PrivCirNet: Efficient Private Inference via Block Circulant Transformation
* Authors: Tianshi Xu, Lemeng Wu, Runsheng Wang, Meng Li
* [Permalink](https://eprint.iacr.org/2024/2008)
* [Download](https://eprint.iacr.org/2024/2008.pdf)

### Abstract

Homomorphic encryption (HE)-based deep neural network (DNN) inference protects data and model privacy but suffers from significant computation overhead. We observe transforming the DNN weights into circulant matrices converts general matrix-vector
multiplications into HE-friendly 1-dimensional convolutions, drastically reducing the HE computation cost. Hence, in this paper, we propose PrivCirNet, a protocol/network co-optimization framework based on block circulant transformation. At the protocol
level, PrivCirNet customizes the HE encoding algorithm that is fully compatible with the block circulant transformation and reduces the computation latency in proportion to the block size. At the network level, we propose a latency-aware formulation to
search for the layer-wise block size assignment based on second-order information. PrivCirNet also leverages layer fusion to further reduce the inference cost. We compare PrivCirNet with the state-of-the-art HE-based framework Bolt (IEEE S&P 2024) and HE-
friendly pruning method SpENCNN (ICML 2023). For ResNet-18 and Vision Transformer (ViT) on Tiny ImageNet, PrivCirNet reduces latency by $5.0\times$ and $1.3\times$ with iso-accuracy over Bolt, respectively, and improves accuracy by $4.1\%$ and $12\%$
over SpENCNN, respectively. For MobileNetV2 on ImageNet, PrivCirNet achieves $1.7\times$ lower latency and $4.2\%$ better accuracy over Bolt and SpENCNN, respectively.
Our code and checkpoints are available at https://github.com/Tianshi-Xu/PrivCirNet.



## 2024/2009

* Title: The Mis/Dis-information Problem is Hard to Solve
* Authors: Gregory Hagen, Reihaneh Safavi-Naini, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/2009)
* [Download](https://eprint.iacr.org/2024/2009.pdf)

### Abstract

Securing information communication dates back thousands of years ago. The meaning of information security, however, has evolved over time and today covers a very wide variety of goals, including identifying the source of information, the reliability of
information, and ultimately whether the information is trustworthy.
In this paper, we will look at the evolution of the information security problem and the approaches that have been developed for providing
information protection. We argue that the more recent problem of misinformation and disinformation has shifted the content integrity problem from the protection of message syntax to the protection of message semantics. This shift, in the age of advanced
AI systems, a technology that can be used to mimic human-generated content as well as to create bots that mimic human behaviour on the Internet, poses fundamental technological challenges that evade existing technologies. It leaves social elements,
including public education and a suitable legal framework, as increasingly the main pillars of effective protection, at least in the short run. It also poses an intriguing challenge to the scientific community: to design effective solutions that employ
cryptography and AI, together with incentivization to engage the global community, to ensure the safety of the information ecosystem.



## 2024/2010

* Title: Anonymous credentials from ECDSA
* Authors: Matteo Frigo, abhi shelat
* [Permalink](https://eprint.iacr.org/2024/2010)
* [Download](https://eprint.iacr.org/2024/2010.pdf)

### Abstract

Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves. For example, a user who has received a digital passport credential can
prove their “age is $>18$” without revealing any other attributes such as their name or date of birth.

Despite inherent value for privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic assumptions that
require system-wide changes to existing issuer infrastructure. In addition, issuers often require digital identity credentials to be *device-bound* by incorporating the device’s secure element into the presentation flow. As a result, schemes like
BBS+ require updates to the hardware secure elements and OS on every user's device.

In this paper, we propose a new anonymous credential scheme for the popular and legacy-deployed Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme. By adding efficient zk arguments for statements about SHA256 and document parsing
for ISO-standardized identity formats, our anonymous credential scheme is that first one that can be deployed *without* changing any issuer processes, *without* requiring changes to mobile devices, and *without* requiring non-standard cryptographic
assumptions.

Producing ZK proofs about ECDSA signatures has been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms. We overcome this bottleneck by
designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA.

Our proofs for ECDSA can be generated in 60ms. When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, we can generate a zero-knowledge proof for the MDOC presentation flow in 1.2 seconds on mobile devices
depending on the credential size. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.



## 2024/2011

* Title: Honest-Majority Threshold ECDSA with Batch Generation of Key-Independent Presignatures
* Authors: Jonathan Katz, Antoine Urban
* [Permalink](https://eprint.iacr.org/2024/2011)
* [Download](https://eprint.iacr.org/2024/2011.pdf)

### Abstract

Several protocols have been proposed recently for threshold ECDSA signatures, mostly in the dishonest-majority setting. Yet in so-called key-management networks, where a fixed set of servers share a large number of keys on behalf of multiple users, it
may be reasonable to assume that a majority of the servers remain uncompromised, and in that case there may be several advantages to using an honest-majority protocol.

With this in mind, we describe an efficient protocol for honest-majority threshold ECDSA supporting batch generation of key-independent presignatures that allow for "non-interactive'" online signing; these properties are not available in existing
dishonest-majority protocols. Our protocol offers low latency and high throughput, and runs at an amortized rate of roughly 1.3 ms/presignature.



## 2024/2012

* Title: GraSS: Graph-based Similarity Search on Encrypted Query
* Authors: Duhyeong Kim, Yujin Nam, Wen Wang, Huijing Gong, Ishwar Bhati, Rosario Cammarota, Tajana S. Rosing, Mariano Tepper, Theodore L. Willke
* [Permalink](https://eprint.iacr.org/2024/2012)
* [Download](https://eprint.iacr.org/2024/2012.pdf)

### Abstract


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)