[continued from previous message]

We analyze the security of MAPCP and demonstrate its atomicity, meaning that, (i) the buyer gets the digital product after the payment is published in the blockchain (buyer security); and (ii) the seller receives the payment if the buyer gets access to
the digital product (seller security). Moreover, we present a construction of MAPCP in a use case where a customer pays a notary in exchange for a document signature.



## 2024/1931

* Title: On White-Box Learning and Public-Key Encryption
* Authors: Yanyi Liu, Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/1931)
* [Download](https://eprint.iacr.org/2024/1931.pdf)

### Abstract

We consider a generalization of the Learning With Error problem, referred to as the white-box learning problem: You are given the code of a sampler that with high probability produces samples of the form $y,f(y)+\epsilon$ where is small, and $f$ is
computable in polynomial-size, and the computational task consist of outputting a polynomial-size circuit $C$ that with probability, say, $1/3$ over a new sample $y$? according to the same distributions, approximates $f(y)$ (i.e., $|C(y)-f(y)$ is small).
This problem can be thought of as a generalizing of the Learning with Error Problem (LWE) from linear functions $f$ to polynomial-size computable functions.

We demonstrate that worst-case hardness of the white-box learning problem, conditioned on the instances satisfying a notion of computational shallowness (a concept from the study of Kolmogorov complexity) not only suffices to get public-key encryption,
but is also necessary; as such, this yields the first problem whose worst-case hardness characterizes the existence of public-key encryption. Additionally, our results highlights to what extent LWE “overshoots” the task of public-key encryption.

We complement these results by noting that worst-case hardness of the same problem, but restricting the learner to only get black-box access to the sampler, characterizes one-way functions.



## 2024/1932

* Title: On Witness Encryption and Laconic Zero-Knowledge Arguments
* Authors: Yanyi Liu, Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/1932)
* [Download](https://eprint.iacr.org/2024/1932.pdf)

### Abstract

Witness encryption (WE) (Garg et al, STOC’13) is a powerful cryptographic primitive that is closely related to the notion of indistinguishability obfuscation (Barak et, JACM’12, Garg et al, FOCS’13). For a given NP-language $L$, WE for $L$ enables
encrypting a message $m$ using an instance $x$ as the public-key, while ensuring that efficient decryption is possible by anyone possessing a witness for $x \in L$, and if $x\notin L$, then the encryption is hiding. We show that this seemingly
sophisticated primitive is equivalent to a communication-efficient version of one of the most classic cryptographic primitives—namely that of a zero-knowledge argument (Goldwasser et al, SIAM’89, Brassard et al, JCSS’88): for any NP-language $L$,
the following are equivalent:
- There exists a witness encryption for L;
- There exists a laconic (i.e., the prover communication is bounded by $O(\log n)$) special-honest verifier zero-knowledge (SHVZK) argument for $L$.
Our approach is inspired by an elegant (one-sided) connection between (laconic) zero-knowledge arguments and public-key encryption established by Berman et al (CRYPTO’17) and Cramer-Shoup (EuroCrypt’02).



## 2024/1933

* Title: On Concrete Security Treatment of Signatures Based on Multiple Discrete Logarithms
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/1933)
* [Download](https://eprint.iacr.org/2024/1933.pdf)

### Abstract

In this paper, we present a generalization of Schnorr's digital signature that allows a user to simultaneously sign multiple messages. Compared to Schnorr's scheme that concatenates messages and then signs them, the new protocol takes advantage of
multiple threads to process messages in parallel. We prove the security of our novel protocol and discuss different variants of it. Last but not least, we extend Ferradi et al.'s co-signature protocol by exploiting the inherent parallelism of our
proposed signature scheme.



## 2024/1934

* Title: Quantum One-Time Programs, Revisited
* Authors: Aparna Gupte, Jiahui Liu, Justin Raizes, Bhaskar Roberts, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/1934)
* [Download](https://eprint.iacr.org/2024/1934.pdf)

### Abstract

One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of
quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for
any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is
a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security.

In this work, we present new, meaningful, yet achievable definitions of one-time program security for *probabilistic* classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle
model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be
highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.



## 2024/1935

* Title: RevoLUT : Rust Efficient Versatile Oblivious Look-Up-Tables
* Authors: Sofiane Azogagh, Zelma Aubin Birba, Marc-Olivier Killijian, Félix Larose-Gervais
* [Permalink](https://eprint.iacr.org/2024/1935)
* [Download](https://eprint.iacr.org/2024/1935.pdf)

### Abstract

In this paper we present RevoLUT, a library implemented in Rust that reimagines the use of Look-Up-Tables (LUT) beyond their conventional role in function encoding, as commonly used in TFHE's programmable boostrapping. Instead, RevoLUT leverages LUTs as
first class objects, enabling efficient oblivious operations such as array access, elements sorting and permutation directly within the table. This approach supports oblivious algortithm, providing a secure, privacy-preserving solution for handling
sensitive data in various applications.



## 2024/1936

* Title: Multiparty Shuffle: Linear Online Phase is Almost for Free
* Authors: Jiacheng Gao, Yuan Zhang, Sheng Zhong
* [Permalink](https://eprint.iacr.org/2024/1936)
* [Download](https://eprint.iacr.org/2024/1936.pdf)

### Abstract

Shuffle is a frequently used operation in secure multiparty computations, with various applications, including joint data analysis and anonymous communication systems. Most existing MPC shuffle protocols are constructed from MPC permutation protocols,
which allows a party to securely apply its private permutation to an array of $m$ numbers shared among all $n$ parties. Following a ``permute-in-turn'' paradigm, these protocols result in $\Omega(n^2m)$ complexity in the semi-honest setting. Recent works
have significantly improved efficiency and security by adopting a two-phase solution. Specifically, Eskandarian and Boneh demonstrate how to construct MPC shuffle protocols with linear complexity in both semi-honest and malicious adversary settings.
However, a more recent study by Song et al. reveals that Eskandarian and Boneh's protocol fails to achieve malicious security. Consequently, designing an MPC shuffle protocol with linear complexity and malicious security remains an open question.

In this paper, we address this question by presenting the first general construction of MPC shuffle protocol that is maliciously secure and has linear online communication and computation complexity, utilizing black-box access to secure arithmetic
MPC primitives and MPC permutation protocol. When instantiating our construction with the SPDZ framework and the best existing malicious secure MPC shuffle, our construction only slightly increases the offline overhead compared to the semi-honest secure
version, and thus achieve a linear online phase almost for free. As our constructions requires only black-box access to basic secure MPC primitives and permutation protocols, they are compatible with and can be integrated to most modern MPC frameworks.
We provide formal security proofs for both semi-honest and malicious settings, demonstrating that our maliciously secure construction can achieve universally composable security. Experimental results indicate that our construction significantly enhances
online performance while maintaining a moderate increase in offline overhead. Given that shuffle is a frequently used primitive in secure multiparty computation, we anticipate that our construction will accelerate many real-world MPC applications.



## 2024/1937

* Title: Asynchronous Byzantine Consensus with Trusted Monotonic Counters
* Authors: Yackolley Amoussou-Guenou, Maurice Herlihy, Maria Potop Butucaru
* [Permalink](https://eprint.iacr.org/2024/1937)
* [Download](https://eprint.iacr.org/2024/1937.pdf)

### Abstract

The paper promotes a new design paradigm for Byzantine tolerant distributed algorithms using trusted abstractions (oracles) specified in a functional manner. The contribution of the paper is conceptual. The objective here is to design distributed
fundamental algorithms such as reliable broadcast and asynchronous byzantine consensus using trusted execution environments and to help designers to compare various solutions on a common ground.
In this framework we revisit the Bracha's seminal work on Asynchronous Byzantine Consensus. Our solution uses trusted monotonic counters abstraction and tolerates $t$ Byzantine processes in a system with $n$ processes, $n \geq 2t+1$. The keystone of our
construction is a novel and elegant Byzantine Reliable Broadcast algorithm resilient to $t<n$ Byzantine processes that uses an unique trusted monotonic counter (at the initiator).



## 2024/1938

* Title: A Formal Treatment of Key Transparency Systems with Scalability Improvements
* Authors: Nicholas Brandt, Mia Filić, Sam A. Markelon
* [Permalink](https://eprint.iacr.org/2024/1938)
* [Download](https://eprint.iacr.org/2024/1938.pdf)

### Abstract

Key Transparency (KT) systems have emerged as a critical technology for securely distributing and verifying the correctness of public keys used in end-to-end encrypted messaging services. Despite substantial academic interest, increased industry adoption,
and IETF standardization efforts, KT systems lack a holistic and formalized security model, limiting their resilience to practical threats and constraining future development. In this paper, we introduce the first cryptographically sound formalization
of KT as an ideal functionality, clarifying the assumptions, security properties, and potential vulnerabilities of deployed KT systems. We identify a significant security concern — a possible impersonation attack by a malicious service provider — and
propose a backward-compatible solution. Additionally, we address a core scalability bottleneck by designing and implementing a novel, privacy-preserving verifiable Bloom filter (VBF) that significantly improves KT efficiency without compromising security.
Experimental results demonstrate the effectiveness of our approach, marking a step forward in both the theoretical and practical deployment of scalable KT solutions.



## 2024/1939

* Title: Machine Learning-Based Detection of Glitch Attacks in Clock Signal Data
* Authors: Asier Gambra, Durba Chatterjee, Unai Rioja, Igor Armendariz, Lejla Batina
* [Permalink](https://eprint.iacr.org/2024/1939)
* [Download](https://eprint.iacr.org/2024/1939.pdf)

### Abstract

Voltage fault injection attacks are a particularly powerful threat to secure embedded devices because they exploit brief, hard-to-detect power fluctuations causing errors or bypassing security mechanisms. To counter these attacks, various detectors are
employed, but as defenses strengthen, increasingly elusive glitches continue to emerge. Artificial intelligence, with its inherent ability to learn and adapt to complex patterns, presents a promising solution. This research presents an AI-driven voltage
fault injection detector that analyzes clock signals directly. We provide a detailed fault characterization of the STM32F410 microcontroller, emphasizing the impact of faults on the clock signal. Our findings reveal how power supply glitches directly
impact the clock, correlating closely with the amount of power injected. This led to developing a lightweight Multi-Layer Perceptron model that analyzes clock traces to distinguish between safe executions, glitches that keep the device running but may
introduce faults, and glitches that cause the target to reset. While previous fault injection AI applications have primarily focused on parameter optimization and simulation assistance, in this work we use the adaptability of machine learning to create a
fault detection model that is specifically adjusted to the hardware that implements it. The developed glitch detector has a high accuracy showing this a promising direction to combat FI attacks on a variety of platform.



## 2024/1940

* Title: A Comprehensive Review of Post-Quantum Cryptography: Challenges and Advances
* Authors: Seyed MohammadReza Hosseini, Hossein Pilaram
* [Permalink](https://eprint.iacr.org/2024/1940)
* [Download](https://eprint.iacr.org/2024/1940.pdf)

### Abstract

One of the most crucial measures to maintain data security is the use of cryptography schemes and digital signatures built upon cryptographic algorithms. The resistance of cryptographic algorithms against conventional attacks is guaranteed by the
computational difficulties and the immense amount of computation required to them. In the last decade, with the advances in quantum computing technology and the realization of quantum computers, which have higher computational power compared to
conventional computers and can execute special kinds of algorithms (i.e., quantum algorithms), the security of many existing cryptographic algorithms has been questioned. The reason is that by using quantum computers and executing specific quantum
algorithms through them, the computational difficulties of conventional cryptographic algorithms can be reduced, which makes it possible to overcome and break them in a relatively short period of time. Therefore, researchers began efforts to find new
quantum-resistant cryptographic algorithms that would be impossible to break, even using quantum computers, in a short time. Such algorithms are called post-quantum cryptographic algorithms. In this article, we provide a comprehensive review of the
challenges and vulnerabilities of different kinds of conventional cryptographic algorithms against quantum computers. Afterward, we review the latest cryptographic algorithms and standards that have been proposed to confront the threats posed by quantum
computers. We present the classification of post-quantum cryptographic algorithms and digital signatures based on their technical specifications, provide examples of each category, and outline the strengths and weaknesses of each category.



## 2024/1941

* Title: Universally Composable Server-Supported Signatures for Smartphones
* Authors: Nikita Snetkov, Jelizaveta Vakarjuk, Peeter Laud
* [Permalink](https://eprint.iacr.org/2024/1941)
* [Download](https://eprint.iacr.org/2024/1941.pdf)

### Abstract

Smart-ID is an application for signing and authentication provided as a service to residents of Belgium, Estonia, Latvia and Lithuania. Its security relies on multi-prime server-supported RSA, password-authenticated key shares and clone detection
mechanism. Unfortunately, the security properties of the underlying protocol have been specified only in ``game-based'' manner. There is no corresponding ideal functionality that the actual protocol is shown to securely realize in the universal
composability (UC) framework. In this paper, we remedy that shortcoming, presenting the functionality (optionally parameterized with a non-threshold signature scheme) and prove that the existing Smart-ID protocol securely realizes it. Additionally, we
present a server-supported protocol for generating ECDSA signatures and show that it also securely realizes the proposed ideal functionality in the Global Random Oracle Model (UC+GROM).



## 2024/1942

* Title: DGMT: A Fully Dynamic Group Signature From Symmetric-key Primitives
* Authors: Mojtaba Fadavi, Sabyasachi Karati, Aylar Erfanian, Reihaneh Safavi-Naini
* [Permalink](https://eprint.iacr.org/2024/1942)
* [Download](https://eprint.iacr.org/2024/1942.pdf)

### Abstract

A group signatures allows a user to sign a message anonymously on behalf of a group and provides accountability by using an opening authority who can ``open'' a signature and reveal the signer's identity. Group signatures have been widely used in
privacy-preserving applications including anonymous attestation and anonymous authentication. Fully dynamic group signatures allow new members to join the group and existing members to be revoked if needed. Symmetric-key based group signature schemes
are post-quantum group signatures whose security rely on the security of symmetric-key primitives such as cryptographic hash functions and pseudorandom functions.

In this paper, we design a symmetric-key based fully dynamic group signature scheme, called DGMT, that redesigns DGM (Buser et al. ESORICS 2019) and removes its two important shortcomings that limit its application in practice: (i) interaction with the
group manager for signature verification, and (ii) the need for storing and managing an unacceptably large amount of data by the group manager. We prove security of DGMT (unforgeability, anonymity, and traceability) and give a full implementation of
the system. Compared to all known post-quantum group signature schemes with the same security level, DGMT has the shortest signature size. We also analyze DGM signature revocation approach and show that despite its conceptual novelty, it has
significant hidden costs that makes it much more costly than using traditional revocation list approach.



## 2024/1943

* Title: $\textsf{LiLAC}$: Linear Prover, Logarithmic Verifier and Field-agnostic Multilinear Polynomial Commitment Scheme
* Authors: Kyeongtae Lee, Seongho Park, Byeongjun Jang, Jihye Kim, Hyunok Oh
* [Permalink](https://eprint.iacr.org/2024/1943)
* [Download](https://eprint.iacr.org/2024/1943.pdf)

### Abstract

In this paper, we propose $\textsf{LiLAC}$, a novel field-agnostic, transparent multilinear polynomial commitment scheme (MLPCS) designed to address key challenges in polynomial commitment systems. For a polynomial with $N$ coefficients, $\textsf{LiLAC}$
achieves $\mathcal{O}(N)$ prover time, $\mathcal{O}(\log N)$ verifier time, and $\mathcal{O}(\log N)$ proof size, overcoming the limitations of $\mathcal{O}(\log^2 N)$ verification time and proof size without any increase in other costs. This is achieved
through an optimized polynomial commitment strategy and the recursive application of the tensor IOPP, making $\textsf{LiLAC}$ both theoretically optimal and practical for large-scale applications. Furthermore, $\textsf{LiLAC}$ offers post-quantum
security, providing robust protection against future quantum computing threats.

We propose two constructions of $\textsf{LiLAC}$: a field-agnostic $\textsf{LiLAC}$ and a field-specific $\textsf{LiLAC}$. Each construction demonstrates superior performance compared to the state-of-the-art techniques in their respective categories of
MLPCS.
First, the field-agnostic $\textsf{LiLAC}$ is compared against Brakedown (CRYPTO 2023), which is based on a tensor IOP and satisfies field-agnosticity. In experiments conducted over a 128-bit field with a coefficient size of $2^{30}$, the field-agnostic $
\textsf{LiLAC}$ achieves a proof size that is $3.7\times$ smaller and a verification speed that is $2.2\times$ faster, while maintaining a similar proof generation time compared to Brakedown.
Furthermore, the field-specific $\textsf{LiLAC}$ is evaluated against WHIR (ePrint 2024/1586), which is based on an FRI. With a 128-bit field and a coefficient size of $2^{30}$, the field-specific $\textsf{LiLAC}$ achieves a proof generation speed that
is $2.8\times$ faster, a proof size that is $27\%$ smaller, and a verification speed that is $14\%$ faster compared to WHIR.



## 2024/1944

* Title: SoK: The apprentice guide to automated fault injection simulation for security evaluation
* Authors: Asmita Adhikary, Giacomo Tommaso Petrucci, Philippe Tanguy, Vianney Lapôtre, Ileana Buhan
* [Permalink](https://eprint.iacr.org/2024/1944)
* [Download](https://eprint.iacr.org/2024/1944.pdf)

### Abstract

Identifying and mitigating vulnerable locations to fault injections requires significant expertise and expensive equipment. Fault injections can damage hardware, cause software crashes, and pose safety and security hazards. Simulating fault injections
offers a safer alternative, and fault simulators have steadily developed, though they vary significantly in functionality, target applications, fault injection methods, supported fault models, and guarantees. We present a taxonomy categorizing fault
simulators based on their target applications and development cycle stages, from source code to final product. Our taxonomy provides insights and comparisons to highlight open problems.



## 2024/1945

* Title: Multi-Client Attribute-Based and Predicate Encryption from Standard Assumptions
* Authors: David Pointcheval, Robert Schädlich
* [Permalink](https://eprint.iacr.org/2024/1945)
* [Download](https://eprint.iacr.org/2024/1945.pdf)

### Abstract

Multi-input Attribute-Based Encryption (ABE) is a generalization of key-policy ABE where attributes can be independently encrypted across several ciphertexts, and a joint decryption of these ciphertexts is possible if and only if the combination of
attributes satisfies the policy of the decryption key. We extend this model by introducing a new primitive that we call Multi-Client ABE (MC-ABE), which provides the usual enhancements of multi-client functional encryption over multi-input functional
encryption. Specifically, we separate the secret keys that are used by the different encryptors and consider the case that some of them may be corrupted by the adversary. Furthermore, we tie each ciphertext to a label and enable a joint decryption of
ciphertexts only if all ciphertexts share the same label. We provide constructions of MC-ABE for various policy classes based on SXDH. Notably, we can deal with policies that are not a conjunction of local policies, which has been a limitation of
previous constructions from standard assumptions.

Subsequently, we introduce the notion of Multi-Client Predicate Encryption (MC-PE) which, in contrast to MC-ABE, does not only guarantee message-hiding but also attribute-hiding. We present a new compiler that turns any constant-arity MC-ABE into an MC-
PE for the same arity and policy class. Security is proven under the LWE assumption.



## 2024/1946

* Title: Distributed Differentially Private Data Analytics via Secure Sketching * Authors: Jakob Burkhardt, Hannah Keller, Claudio Orlandi, Chris Schwiegelshohn
* [Permalink](https://eprint.iacr.org/2024/1946)
* [Download](https://eprint.iacr.org/2024/1946.pdf)

### Abstract

We explore the use of distributed differentially private computations across multiple servers, balancing the tradeoff between the error introduced by the differentially private mechanism and the computational efficiency of the resulting distributed
algorithm.

We introduce the linear-transformation model, where clients have access to a trusted platform capable of applying a public matrix to their inputs. Such computations can be securely distributed across multiple servers using simple and efficient secure
multiparty computation techniques.

The linear-transformation model serves as an intermediate model between the highly expressive central model and the minimal local model. In the central model, clients have access to a trusted platform capable of applying any function to their inputs.
However, this expressiveness comes at a cost, as it is often expensive to distribute such computations, leading to the central model typically being implemented by a single trusted server. In contrast, the local model assumes no trusted platform, which
forces clients to add significant noise to their data. The linear-transformation model avoids the single point of failure for privacy present in the central model, while also mitigating the high noise required in the local model.

We demonstrate that linear transformations are very useful for differential privacy, allowing for the computation of linear sketches of input data. These sketches largely preserve utility for tasks such as private low-rank approximation and private ridge
regression, while introducing only minimal error, critically independent of the number of clients. Previously, such accuracy had only been achieved in the more expressive central model.



## 2024/1947

* Title: One-More Unforgeability for Multi- and Threshold Signatures
* Authors: Sela Navot, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2024/1947)
* [Download](https://eprint.iacr.org/2024/1947.pdf)

### Abstract

This paper initiates the study of one-more unforgeability for multi-signatures and threshold signatures as a stronger security goal, ensuring that ℓ executions of a signing protocol cannot result in more than ℓ signatures. This notion is widely used
in the context of blind signatures, but we argue that it is a convenient way to model strong unforgeability for other types of distributed signing protocols. We provide formal security definitions for one-more unforgeability (OMUF) and show that the HBMS
multi-signature scheme does not satisfy this definition, whereas MuSig and MuSig2 do. We also show that mBCJ multi-signautres do not satisfy OMUF, as well as expose a subtle issue with their existential unforgeability (which does not contradict their
original security proof). For threshold signatures, we show that FROST satisfies OMUF, but ROAST does not.

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