[continued from previous message]

In the process, we identify and provide generic solutions for two fundamental issues arising when deriving a large number of private keys from a single seed, and when building FSS for Hash-and-Sign-based signatures.



## 2023/1755

* Title: HashRand: Efficient Asynchronous Random Beacon without Threshold Cryptographic Setup
* Authors: Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Michael Reiter
* [Permalink](https://eprint.iacr.org/2023/1755)
* [Download](https://eprint.iacr.org/2023/1755.pdf)

### Abstract

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes,
with the majority of them assumed to be honest. These protocols have found applications in blockchain technology, leading to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon
systems rely on threshold cryptographic setups or exhibit high computational costs, while others assume partial or bounded synchronous networks. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous
random beacon protocol that uses a secure Hash function to generate beacons and pairwise secure channels. HashRand has a per-node communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is
attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against
quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=160$ nodes, HashRand produces 1 beacon every second, which is at least 4x higher than Spurt. We also
demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 122k txns per second over a WAN at $n=40$ nodes.



## 2023/1756

* Title: How to Use Quantum Indistinguishability Obfuscation
* Authors: Andrea Coladangelo, Sam Gunn
* [Permalink](https://eprint.iacr.org/2023/1756)
* [Download](https://eprint.iacr.org/2023/1756.pdf)

### Abstract

Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs.

As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs.
We show that applying qsiO to a program immediately achieves best-possible copy protection.

Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof
is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the
existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection.

Finally, we construct qsiO relative to an efficient quantum oracle.



## 2023/1757

* Title: Adaptively Secure Consensus with Linear Complexity and Constant Round under Honest Majority in the Bare PKI Model, and Separation Bounds from the Idealized Message-Authentication Model
* Authors: Matthieu Rambaud
* [Permalink](https://eprint.iacr.org/2023/1757)
* [Download](https://eprint.iacr.org/2023/1757.pdf)

### Abstract

We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI
is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since [Lamport et al, 82]
that BA under honest majority (let alone secure computation) would not be possible without messages-authentication. But as further highlighted by [Borcherding, 96], messages-authentication cannot not simply be implemented with digital signatures, without
a bulletin-board of public keys. So the bulletin-board PKI setup and the messages-authentication model seem very close: this raizes the question whether there is a separation between them. In the bulletin-board PKI setup, the most communication-efficient
synchronous BA is the one of [Boyle-Cohen-Goel, Podc'21 \& J. Cryptol.'24], which has $O(n.\text{polylog}(n))$ bit complexity, $f<n(1/3-\epsilon)$ resilience and tolerates an adversary which cannot adaptively corrupt after the setup. Our main upper-bound
is a BA (and also a VBA) in this same model with strictly better parameters: {quasi-optimal} resilience $f<n(1/2-\epsilon)$, with an expected bit complexity of communications which is {linear} in $n$, and tolerance to an {adaptive} rushing adversary (but
which unavoidably cannot remove messages sent). As [BCG'21], they have constant expected latency. All previous BAs or VBAs achieving the same metrics as our upper bound, are either in the static adversary model: Sleepy [Pass-Shi, Asiacrypt'17], Snow
White [Daian-Pass-Shi, FC'19], or assume more than a bare PKI setup: (i) The model of Thunderella [Pass-Shi, EC'17], Algorand [Gilad et al, SOSP'17], Praos [David et al, EC'18], [Goyal et al, FC'21] and [Momose et al, CCS'22 and CCS'23] assumes a public
random seed which is unpredictable until strictly after all players published on the bulletin board; (ii) [Abraham et al, Podc'19] assume a trusted entity which honestly samples the keys of all players; (iii) All known implementations of the setups (i)
and (ii), as well as the setup of [Blum et al, TCC'20], require interactions, furthermore in the form of BAs. (iv) [Garay-Kiayas-Shen '23] assume that honest players work more than the adversary, or, [Eckey-Faust-Loss et al '17 '22] at least as fast.
Of independent interest, our tool is a very simple non-interactive mechanism which {sets-up a self-sortition function from non-interactive publications on the bulletin board}, and still, guarantees an honest majority in every committee up to probability
exponentially small in both $\epsilon$ and in the multicast complexity.
We provide the following further results:

{- Optimality.} We show that resilience up to a tight honest majority $f<n/2$ is impossible for any multicast-based adaptively secure BA with subquadratic communication, whatever the setup.

{- Separation.} We show impossibility of subquadratic multicast-based BA in the messages-authentication model. Our model for this lower bound is even stronger, since it onboards other assumptions at least as strong as all popular implications of a
bulletin-board PKI setup: {secure channels}, {a (possibly structured) random string}, {NIZK}.

{- Partial synchrony.} Given that the multicast lower-bound holds a fortiori, and that the upper-bound adapts seamlessly (for $f<n(1/3-\epsilon)$), the separation also holds.
We show a second separation, which holds for general BAs, non-necessarily multicast-based: any partially-synchronous BA in the messages-authentication model, if it has linear message complexity, then it has latency at least {logarithmic in $f$}.

{- Extension to VBA.} We extend to VBA the logarithmic latency lower bound. This is the first communication lower bound for randomized VBA to our knowledge. It shows that the separation under partial synchrony also holds for VBA. Along the way, we close
the characterization of [Civit et al, Podc'23] of validity conditions in authenticated consensus, by apparently new results on VBA: both BA and VBA are infeasible under partial synchrony beyond $f<n/3$, whatever the setup; whereas synchronous VBA is
feasible up to $f=n-1$ (contrary to BA).



## 2023/1758

* Title: Pulsar: Secure Steganography through Diffusion Models
* Authors: Tushar M. Jois, Gabrielle Beck, Gabriel Kaptchuk
* [Permalink](https://eprint.iacr.org/2023/1758)
* [Download](https://eprint.iacr.org/2023/1758.pdf)

### Abstract

Widespread efforts to subvert acccess to strong cryptography has renewed interest in steganography, the practice of embedding sensitive messages in mundane cover messages. Recent efforts at provably secure steganography have only focused on text-based
generative models and cannot support other types of models, such as diffusion models, which are used for high-quality image synthesis. In this work, we initiate the study of securely embedding steganographic messages into the output of image diffusion
models. We identify that the use of variance noise during image generation provides a suitable steganographic channel. We develop our construction, Pulsar, by building optimizations to make this channel practical for communication. Our implementation of
Pulsar is capable of embedding $\approx 275$-$542$ bytes (on average) into a single image without altering the distribution of the generated image, all in the span of $\approx 3$ seconds of online time on a laptop. In addition, we discuss how the results
of Pulsar can inform future research into diffusion models. Pulsar shows that diffusion models are a promising medium for steganography and censorship resistance.



## 2023/1759

* Title: Non-Interactive Zero-Knowledge Functional Proofs
* Authors: Gongxian Zeng, Junzuo Lai, Zhengan Huang, Linru Zhang, Xiangning Wang, Kwok-Yan Lam, Huaxiong Wang, Jian Weng
* [Permalink](https://eprint.iacr.org/2023/1759)
* [Download](https://eprint.iacr.org/2023/1759.pdf)

### Abstract

In this paper, we consider to generalize NIZK by empowering a prover to share a witness in a fine-grained manner with verifiers. Roughly, the prover is able to authorize a verifier to obtain extra information of witness, i.e., besides verifying the truth
of the statement, the verifier can additionally obtain certain function of the witness from the accepting proof using a secret functional key provided by the prover.

To fulfill these requirements, we introduce a new primitive called \emph{non-interactive zero-knowledge functional proofs (fNIZKs)}, and formalize its security notions. We provide a generic construction of fNIZK for any $\textsf{NP}$ relation $\mathcal{
R}$, which enables the prover to share any function of the witness with a verifier. For a widely-used relation about set membership proof (implying range proof), we construct a concrete and efficient fNIZK, through new building blocks (set membership
encryption and dual inner-product encryption), which might be of independent interest.



## 2023/1760

* Title: Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials
* Authors: Luk Bettale, Delaram Kahrobaei, Ludovic Perret, Javier Verbel
* [Permalink](https://eprint.iacr.org/2023/1760)
* [Download](https://eprint.iacr.org/2023/1760.pdf)

### Abstract

This paper describes Biscuit, a new multivariate-based signature scheme derived using the MPCitH approach. The security of Biscuit is related to the problem of solving a set of quadratic structured systems of algebraic equations. These equations are
highly compact and can be evaluated using very few multiplications. The core of Biscuit is a rather simple MPC protocol which consists of the parallel execution of a few secure multiplications using standard optimized multiplicative triples. This paper
also includes several improvements with respect to Biscuit submission to the last NIST PQC standardization process for additional
signature schemes. Notably, we introduce a new hypercube variant of Biscuit, refine the security analysis with recent third-party attacks, and present a new avx2 implementation of Biscuit.



## 2023/1761

* Title: Guardianship in Group Key Exchange for Limited Environments
* Authors: Elsie Mestl Fondevik, Britta Hale, Xisen Tian
* [Permalink](https://eprint.iacr.org/2023/1761)
* [Download](https://eprint.iacr.org/2023/1761.pdf)

### Abstract

Post-compromise security (PCS) has been a core goal of end-to-end encrypted messaging applications for many years, both in one-to-one continuous key agreement (CKA) and for groups (CGKA). At its essence, PCS relies on a compromised party to perform a key
update in order to `self-heal'. However, due to bandwidth constraints, receive-only mode, and various other environmental demands of the growing number of use cases for such CGKA protocols, a group member may not be able to issue such updates. In this
work, we address the issue of devices functioning in limited mode through the introduction of guardianship, where a designated guardian can perform key updates on the behalf of its paired edge device. We introduce a Guardianship PCS (GPCS) security, and
provide an associated security experiment. We investigate various architectural designs in the pursuit of GPCS, provide constructions and security analyses, and describe trade-offs.



## 2023/1762

* Title: ZKSMT: A VM for Proving SMT Theorems in Zero Knowledge
* Authors: Daniel Luick, John Kolesar, Timos Antonopoulos, William R. Harris, James Parker, Ruzica Piskac, Eran Tromer, Xiao Wang, Ning Luo
* [Permalink](https://eprint.iacr.org/2023/1762)
* [Download](https://eprint.iacr.org/2023/1762.pdf)

### Abstract

Verification of program safety is often reducible to proving the unsatisfiability (i.e., validity) of a formula in Satisfiability Modulo Theories (SMT): Boolean logic combined with theories that formalize arbitrary first-order fragments. Zero-knowledge (
ZK) proofs allow SMT formulas to be validated without revealing the underlying formulas or their proofs to other parties, which is a crucial building block for proving the safety of proprietary programs. Recently, Luo et al. (CCS 2022) studied the
simpler problem of proving the unsatisfiability of pure Boolean formulas, but it does not support safety proofs generated by SMT solvers. This work presents ZKSMT, a novel framework for proving the validity of SMT formulas in ZK. We design a virtual
machine (VM) tailored to efficiently represent the verification process of SMT validity proofs in ZK. Our VM can support the vast majority of popular theories when proving program safety while being complete and sound. To demonstrate this, we instantiate
the commonly used theories of equality and linear integer arithmetic in our VM with theory-specific optimizations for proving them in ZK. ZKSMT achieves high practicality even when running on realistic SMT formulas generated by Boogie, a common tool for
software verification. It achieves a three-order-of-magnitude improvement compared to a baseline that executes the proof verification code in a general ZK system.



## 2023/1763

* Title: Secure Transformer Inference
* Authors: Mu Yuan, Lan Zhang, Xiang-Yang Li
* [Permalink](https://eprint.iacr.org/2023/1763)
* [Download](https://eprint.iacr.org/2023/1763.pdf)

### Abstract

We present a three-party protocol that can protect both Transformer parameters and user data during the inference phase. For each feedforward inference process, our protocol only introduces permutation computation of input and output data on the user
side. Our protocol, Secure Transformer Inference Protocol (STIP), can be applied to real-world services like ChatGPT.



## 2023/1764

* Title: Distributed Differential Privacy via Shuffling vs Aggregation: a Curious Study
* Authors: Yu Wei, Jingyu Jia, Yuduo Wu, Changhui Hu, Changyu Dong, Zheli Liu, Xiaofeng Chen, Yun Peng, Shaowei Wang
* [Permalink](https://eprint.iacr.org/2023/1764)
* [Download](https://eprint.iacr.org/2023/1764.pdf)

### Abstract

How to achieve distributed differential privacy (DP) without a trusted central party is of great interest in both theory and practice. Recently, the shuffle model has attracted much attention. Unlike the local DP model in which the users send randomized
data directly to the data collector/analyzer, in the shuffle model an intermediate untrusted shuffler is introduced to randomly permute the data, which have already been randomized by the users, before they reach the analyzer. The most appealing aspect
is that while shuffling does not explicitly add more noise to the data, it can make privacy better. The privacy amplification effect in consequence means the users need to add less noise to the data than in the local DP model, but can achieve the same
level of differential privacy. Thus, protocols in the shuffle model can provide better accuracy than those in the local DP model. What looks interesting to us is that the architecture of the shuffle model is similar to private aggregation, which has been
studied for more than a decade. In private aggregation, locally randomized user data are aggregated by an intermediate untrusted aggregator. Thus, our question is whether aggregation also exhibits some sort of privacy amplification effect? And if so, how
good is this ``aggregation model'' in comparison with the shuffle model. We conducted the first comparative study between the two, covering privacy amplification, functionalities, protocol accuracy, and practicality. The results as yet suggest that the
new shuffle model does not have obvious advantages over the old aggregation model. On the contrary, protocols in the aggregation model outperform those in the shuffle model, sometimes significantly, in many aspects.



## 2023/1765

* Title: The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False
* Authors: Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2023/1765)
* [Download](https://eprint.iacr.org/2023/1765.pdf)

### Abstract

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ̸ = P conjecture (which they predate) and state
that for “meta-complexity” problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search.

In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(·), there exists of a circuit of size $2^{4n/5+o(n)}$ that solves the t(·)-
bounded Kolmogorov complexity problem on every instance.

Our algorithm is black-box in the description of the Universal Turing Machine employed in the definition of Kolmogorov Complexity, and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity
problem of Liu and Pass (FOCS’20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC’91). We additionally demonstrate that no such black-box algorithm can have sub-exponential circuit size.

Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 2^{4n/5+o(n)}; as far as we know, this yields the first
formal proof that a non-trivial circuit can invert any efficient function.



## 2023/1766

* Title: Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time
* Authors: Aurel Page, Damien Robert
* [Permalink](https://eprint.iacr.org/2023/1766)
* [Download](https://eprint.iacr.org/2023/1766.pdf)

### Abstract

In this short note, we present a simplified (but slower) version Clapoti of Clapotis, whose full description will appear later. Let 𝐸/𝔽_𝑞 be an elliptic curve with an effective primitive orientation by a quadratic imaginary order 𝑅 ⊂ End(�
�). Let 𝔞 be an invertible ideal in 𝑅. Clapoti is a randomized polynomial time algorithm in 𝑂 ((log Δ_𝑅 + log 𝑞)^𝑂(1) ) operations to compute the class group action 𝐸 ↦ 𝐸_𝔞 ≃ 𝐸/𝐸[𝔞].



## 2023/1767

* Title: The Impact of Hash Primitives and Communication Overhead for Hardware-Accelerated SPHINCS+
* Authors: Patrick Karl, Jonas Schupp, Georg Sigl
* [Permalink](https://eprint.iacr.org/2023/1767)
* [Download](https://eprint.iacr.org/2023/1767.pdf)

### Abstract

SPHINCS+ is a signature scheme included in the first NIST post-quantum standard, that bases its security on the underlying hash primitive. As most of the runtime of SPHINCS+ is caused by the evaluation of several hash- and pseudo-random functions,
instantiated via the hash primitive, offloading this computation to dedicated hardware accelerators is a natural step. In this work, we evaluate different architectures for hardware acceleration of such a hash primitive with respect to its use-case and
evaluate them in the context of SPHINCS+. We attach hardware accelerators for different hash primitives (SHAKE256 and Asconxof for both full and round-reduced versions) to CPU interfaces having different transfer speeds. We show, that for most use-cases,
data transfer determines the overall performance if accelerators are equipped with FIFOs.



## 2023/1768

* Title: Homomorphic Polynomial Public Key Cryptography for Quantum-secure Digital Signature
* Authors: Randy Kuang, Maria Perepechaenko, Mahmoud Sayed, Dafu Lou
* [Permalink](https://eprint.iacr.org/2023/1768)
* [Download](https://eprint.iacr.org/2023/1768.pdf)

### Abstract

In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication
for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over large hidden
rings using homomorphic encryption through modular multiplications. Initially designed for key encapsulation mechanism (KEM), HPPK ensures security through homomorphic encryption of public polynomials over concealed rings. This paper extends its
application to a digital signature scheme. The framework of HPPK KEM can not be directly applied to the digital signatures dues to the different nature of verification procedure compared to decryption procedure. Thus, in order to use the core ideas of
the HPPK KEM scheme in the framework of digital signatures, the authors introduce an extension of the Barrett reduction algorithm. This extension transforms modular multiplications over hidden rings into divisions in the verification equation, conducted
over a prime field. The extended algorithm non-linearly embeds the signature into public polynomial coefficients, employing the floor function of big integer divisions. This innovative approach overcomes vulnerabilities associated with linear
relationships of earlier MPPK DS schemes. The security analysis reveals exponential complexity for both private key recovery and forged signature attacks, taking into account that the bit length of the rings is twice that of the prime field size. The
effectiveness of the proposed Homomorphic Polynomial Public Key Digital Signature (HPPK DS) scheme is illustrated through a practical toy example, showcasing its intricate functionality and enhanced security features.



## 2023/1769

* Title: A Comprehensive Survey on Non-Invasive Fault Injection Attacks
* Authors: Amit Mazumder Shuvo, Tao Zhang, Farimah Farahmandi, Mark Tehranipoor * [Permalink](https://eprint.iacr.org/2023/1769)
* [Download](https://eprint.iacr.org/2023/1769.pdf)

### Abstract

Non-invasive fault injection attacks have emerged as significant threats to a spectrum of microelectronic systems ranging from commodity devices to high-end customized processors. Unlike their invasive counterparts, these attacks are more affordable and
can exploit system vulnerabilities without altering the hardware physically. Furthermore, certain non-invasive fault injection strategies allow for remote vulnerability exploitation without the requirement of physical proximity. However, existing studies
lack extensive investigation into these attacks across diverse target platforms, threat models, emerging attack strategies, assessment frameworks, and mitigation approaches. In this paper, we provide a comprehensive overview of contemporary research on
non-invasive fault injection attacks. Our objective is to consolidate and scrutinize the various techniques, methodologies, target systems susceptible to the attacks, and existing mitigation mechanisms advanced by the research community. Besides, we
categorize attack strategies based on several aspects, present a detailed comparison among the categories, and highlight research challenges with future direction. By underlining and discussing the landscape of cutting-edge, non-invasive fault injection,
we hope more researchers, designers, and security professionals examine the attacks further and take such threats into consideration while developing effective countermeasures.



## 2023/1770

* Title: On the Feasibility of E2E Verifiable Online Voting – A Case Study From Durga Puja Trial
* Authors: Horia Druliac, Matthew Bardsley, Chris Riches, Christian Dunn, Luke Harrison, Bimal Roy, Feng Hao
* [Permalink](https://eprint.iacr.org/2023/1770)
* [Download](https://eprint.iacr.org/2023/1770.pdf)

### Abstract

India is the largest democracy by population and has one of the largest deployments of e-voting in the world for national elections. However, the e-voting machines used in India are not end-to-end (E2E) verifiable. The inability to verify the tallying
integrity of an election by the public leaves the outcome open to disputes. E2E verifiable e-voting systems are commonly regarded as the most promising solution to address this problem, but they had not been implemented or trialed in India. It was
unclear whether such systems would be usable and practical to the Indian people. Previous works such as Helios require a set of tallying authorities (TAs) to perform the decryption and tallying operations, but finding and managing TAs can prove difficult.
This paper presents a TA-free E2E verifiable online voting system based on the DRE-ip protocol. In collaboration with the local authority of New Town, Kolkata, India, we conducted an online voting trial as part of the 2022 Durga Puja festival
celebration, during which residents of New Town were invited to use mobile phones to vote for their favourite pujas (festival decorations) in an E2E verifiable manner. 543 participants attended the Durga Puja trial and 95 of them provided feedback by
filling in an anonymous survey after voting. Based on the voter feedback, participants generally found the system easy to use. This was the first time that an E2E online voting system had been built and tested in India, suggesting its feasibility for non-
statutory voting scenarios.



## 2023/1771

* Title: A note on ``HAKECC: highly efficient authentication and key agreement scheme based on ECDH for RFID in IOT environment''
* Authors: Zhengjun Cao
* [Permalink](https://eprint.iacr.org/2023/1771)
* [Download](https://eprint.iacr.org/2023/1771.pdf)

### Abstract

We show that the Nikooghadam-Shahriari-Saeidi authentication and key agreement scheme [J. Inf. Secur. Appl., 76, 103523 (2023)]
cannot resist impersonation attack, not as claimed. An adversary can impersonate the RFID reader to cheat the RFID tag. The drawback results from its simple secret key invoking mechanism. We also find it seems difficult to revise the scheme due to the
inherent flaw.



## 2023/1772

* Title: Robust Combiners and Universal Constructions for Quantum Cryptography * Authors: Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2023/1772)
* [Download](https://eprint.iacr.org/2023/1772.pdf)

### Abstract

A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal
construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal construction for
a primitive can be constructed from a robust combiner for the primitive in many cases.

Although robust combiners and universal constructions for classical cryptography are widely studied, robust combiners and universal constructions for quantum cryptography have not been explored so far. In this work, we define robust combiners and
universal constructions for several quantum cryptographic primitives including one-way state generators, public-key quantum money, quantum bit commitments, and unclonable encryption, and provide constructions of them.

On a different note, it was an open problem how to expand the plaintext length of unclonable encryption. In one of our universal constructions for unclonable encryption, we can expand the plaintext length, which resolves the open problem.



## 2023/1773

* Title: Scalable and Adaptively Secure Any-Trust Distributed Key Generation and All-hands Checkpointing
* Authors: Hanwen Feng, Tiancheng Mai, Qiang Tang
* [Permalink](https://eprint.iacr.org/2023/1773)
* [Download](https://eprint.iacr.org/2023/1773.pdf)

### Abstract

The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large scale deployments are still yet to come, due to various
challenges including broadcast channel scalability and worst-case complaint phase.
In this paper, we propose a practical DKG for DL-based cryptosystems, with only (quasi-)linear computation/communication cost per participant, with the help of a public ledger, and beacon; Notably, our DKG only incurs constant-size blockchain storage
cost for broadcast, even in the face of worst-case complaints. Moreover, our protocol satisfies adaptive security.
The key to our improvements lies in delegating the most costly operations to an Any-Trust group. This group is randomly sampled and consists of a small number of individuals. The population only trusts that at least one member in the group is honest,
without knowing which one.
Additionally, we introduce an extended broadcast channel based on a blockchain and data dispersal network (such as IPFS), enabling reliable broadcasting of arbitrary-size messages at the cost of constant-size blockchain storage, which may be of
independent interest.


[continued in next message]

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