• [digest] 2024 Week 1 (1/2)

    From IACR ePrint Archive@21:1/5 to All on Mon Jan 8 03:23:04 2024
    ## In this issue

    1. [2023/1392] Robust Publicly Verifiable Covert Security: Limited ...
    2. [2023/1724] Accountability for Misbehavior in Threshold ...
    3. [2023/1973] Combinatorially Homomorphic Encryption
    4. [2024/1] On short digital signatures with Eulerian ...
    5. [2024/2] Fast polynomial multiplication using matrix ...
    6. [2024/3] Simple Soundness Proofs
    7. [2024/4] Practical Two-party Computational Differential ...
    8. [2024/5] The Multiple Millionaires’ Problem
    9. [2024/6] Towards general-purpose program obfuscation via ...
    10. [2024/7] Password Protected Universal Thresholdizer
    11. [2024/8] SoK: Methods for Sampling Random Permutations in ...
    12. [2024/9] Distributed Protocols for Oblivious Transfer and ...
    13. [2024/10] On the tropical two-sided discrete logarithm and a ...
    14. [2024/11] MetaDORAM: Breaking the Log-Overhead Information ...
    15. [2024/12] Two-Round ID-PAKE with strong PFS and single ...
    16. [2024/13] A note on ``intelligent drone-assisted robust ...
    17. [2024/14] A Lattice-based Accountable Subgroup Multi- ...
    18. [2024/15] Unconditionally secure MPC for Boolean circuits ...
    19. [2024/16] Reducing the computational complexity of fuzzy ...
    20. [2024/17] PT-symmetric mapping of three states and its ...

    ## 2023/1392

    * Title: Robust Publicly Verifiable Covert Security: Limited Information Leakage and Guaranteed Correctness with Low Overhead
    * Authors: Yi Liu, Junzuo Lai, Qi Wang, Xianrui Qin, Anjia Yang, Jian Weng
    * [Permalink](https://eprint.iacr.org/2023/1392)
    * [Download](https://eprint.iacr.org/2023/1392.pdf)

    ### Abstract

    Protocols with \emph{publicly verifiable covert (PVC) security} offer high efficiency and an appealing feature: a covert party may deviate from the protocol, but with a probability (\eg $90\%$, referred to as the \emph{deterrence factor}), the honest
    party can identify this deviation and expose it using a publicly verifiable certificate. These protocols are particularly suitable for practical applications involving reputation-conscious parties.

    However, in the cases where misbehavior goes undetected (\eg with a probability of $10\%$), \emph{no security guarantee is provided for the honest party}, potentially resulting in a complete loss of input privacy and output correctness.

    In this paper, we tackle this critical problem by presenting a highly effective solution. We introduce and formally define an enhanced notion called \emph{robust PVC security}, such that even if the misbehavior remains undetected, the malicious party can
    only gain an additional $1$-bit of information about the honest party's input while maintaining the correctness of the output. We propose a novel approach leveraging \emph{dual execution} and \emph{time-lock puzzles} to design a robust PVC-secure two-
    party protocol with \emph{low overhead} (depending on the deterrence factor). For instance, with a deterrence factor of $90\%$, our robust PVC-secure protocol incurs \emph{only additional ${\sim}10\%$ overhead} compared to the state-of-the-art PVC-secure
    protocol.

    Given the stronger security guarantees with low overhead, our protocol is highly suitable for practical applications of secure two-party computation.



    ## 2023/1724

    * Title: Accountability for Misbehavior in Threshold Decryption via Threshold Traitor Tracing
    * Authors: Dan Boneh, Aditi Partap, Lior Rotem
    * [Permalink](https://eprint.iacr.org/2023/1724)
    * [Download](https://eprint.iacr.org/2023/1724.pdf)

    ### Abstract

    A $t$-out-of-$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a well-formed ciphertext. Existing threshold decryption systems are not secure when these parties are rational actors: an adversary can
    offer to pay the parties for their key shares. The problem is that a quorum of $t$ parties, working together, can sell the adversary a decryption key that reveals nothing about the identity of the traitor parties. This provides a risk-free profit for the
    parties since there is no accountability for their misbehavior --- the information they sell to the adversary reveals nothing about their identity. This behavior can result in a complete break in many applications of threshold decryption, such as
    encrypted mempools, private voting, and sealed-bid auctions.

    In this work we show how to add accountability to threshold decryption systems to deter this type of risk-free misbehavior. Suppose a quorum of $t$ or more parties construct a decoder algorithm $D(\cdot)$ that takes as input a ciphertext and outputs the
    corresponding plaintext or $\bot$. They sell $D$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace $D$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to $
    D$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder $D$ in the first place.

    Our starting point is standard (non-threshold) traitor tracing, where $n$ parties each holds a secret key. Every party can decrypt a well-formed ciphertext on its own. However, if a subset of parties ${\cal J} \subseteq [n]$ collude to create a pirate
    decoder $D(\cdot)$ that can decrypt well-formed ciphertexts, then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder $D$. Traitor tracing received much attention over the years and multiple schemes
    have been developed.

    In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset ${\cal J} \subseteq [n]$ of $t$ or more parties can collude to create a pirate decoder $D(\cdot)$. This problem has recently become quite important
    due to the real-world deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several non-threshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption
    settings requires new cryptographic techniques. We present a number of constructions for traitor tracing for threshold decryption, and note that much work remains to explore the large design space.



    ## 2023/1973

    * Title: Combinatorially Homomorphic Encryption
    * Authors: Yuval Ishai, Eyal Kushnir, Ron D. Rothblum
    * [Permalink](https://eprint.iacr.org/2023/1973)
    * [Download](https://eprint.iacr.org/2023/1973.pdf)

    ### Abstract

    Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography. Nevertheless, while there is a general loose understanding of what
    it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes.
    In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and
    nontrivial homomorphism.

    Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity. Thus, we say that a scheme is combinatorially homomorphic if there
    exists a communication complexity problem $f(x,y)$ (where $x$ is Alice's input and $y$ is Bob's input) which requires communication $c$, but can be solved with communication less than $c$ when Alice is given in addition also an encryption $E_k(y)$ of Bob'
    s input (using Bob's key $k$).

    We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include
    constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.



    ## 2024/1

    * Title: On short digital signatures with Eulerian transformations
    * Authors: Vasyl Ustimenko
    * [Permalink](https://eprint.iacr.org/2024/001)
    * [Download](https://eprint.iacr.org/2024/001.pdf)

    ### Abstract

    Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to
    sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision element into
    composition into given generators. The protocol uses the semigroup of Eulerian transformations of variety (K*)^n where K* is a nontrivial multiplicative group of the finite commutative ring K. Its execution complexity is O(n^3). Additionally we use
    this protocol to define asymmetric cryptosystem with the space of plaintexts and ciphertexts (K*)^n which allows users to encrypt and decrypt O(n^t) documents of size n in time O(n^{3+[t]}) where [x] stands for the flow function from x. Finally we
    suggest protocol based cryptosystem working with plaintext space (K*)^n and the space of ciphertext K^n which allows decryption of O(n^t), t>1 documents of size n in time O(n^{t+3}), t>1. The multivariate encryption map has linear degree O(n) and density
    O(n^4). We discuss the idea of public key with Eulerian transformations which allows to sign O(n^t), t≥0 documents in time O(n^{t+2}). The idea of delivery and usage of several Eulerian and quadratic transformations is also discussed.



    ## 2024/2

    * Title: Fast polynomial multiplication using matrix multiplication accelerators with applications to NTRU on Apple M1/M3 SoCs
    * Authors: Décio Luiz Gazzoni Filho, Guilherme Brandão, Julio López
    * [Permalink](https://eprint.iacr.org/2024/002)
    * [Download](https://eprint.iacr.org/2024/002.pdf)

    ### Abstract

    Efficient polynomial multiplication routines are critical to the performance of lattice-based post-quantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines.
    Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflops-level of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions,
    coprocessors and special-purpose cores to accelerate such operations. In particular, Apple ships an undocumented matrix-multiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to
    implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systems-on-chip (SoCs).



    ## 2024/3

    * Title: Simple Soundness Proofs
    * Authors: Alex Kampa
    * [Permalink](https://eprint.iacr.org/2024/003)
    * [Download](https://eprint.iacr.org/2024/003.pdf)

    ### Abstract

    We present a general method to simplify soundness proofs under certain conditions. Given an adversary $\mathcal{A}$ able to break a scheme $S$ with non-negligible probability $t$, we define the concept of $\textit{trace}$ of a $\textit{winning
    configuration}$, which is already implicitly used in soundness proofs. If a scheme can be constructed that (1) takes a random configuration $e$, being the inputs and execution environment of $\mathcal{A}$, (2) "guesses" a trace, (3) modifies $e$ based on
    its guess so that the modified configuration $e'$ is statistically indistinguishable from the original one, (4) is then able to execute $\mathcal{A}$ correctly under the condition that $e'$ is a winning configuration and that $B$'s guess of the trace was
    correct, and finally (5) that during its execution $\mathcal{A}$ is unable extract any information about $B$'s guess, then the probability of $B$ winning can be expressed as a simple function of $t$ and the bit-length of the trace, namely $\frac{t}{2^m}$.
    Soundness then results if $2^m$ is polynomial in the security parameter.

    To illustrate the concept, a concrete application of this method to a simple binary voting scheme is then described in detail.



    ## 2024/4

    * Title: Practical Two-party Computational Differential Privacy with Active Security.
    * Authors: Fredrik Meisingseth, Christian Rechberger, Fabian Schmid
    * [Permalink](https://eprint.iacr.org/2024/004)
    * [Download](https://eprint.iacr.org/2024/004.pdf)

    ### Abstract

    Distributed models for differential privacy (DP), such as the local and shuffle models, allow for differential privacy without having to trust a single central dataholder. They do however typically require adding more noise than the central model. One
    commonly iterated remark is that achieving DP with similar accuracy as in the central model is directly achievable by \textit{emulating the trusted party}, using general multiparty computation (MPC), which computes a canonical DP mechanism such as the
    Laplace or Gaussian mechanism. There have been a few works proposing concrete protocols for doing this but as of yet, all of them either require honest majorities, only allow passive corruptions, only allow computing aggregate functions, lack formal
    claims of what type of DP is achieved or are not computable in polynomial time by a finite computer. In this work, we propose the first efficiently computable protocol for emulating a dataholder running the geometric mechanism, and which retains its
    security and DP properties in the presence of dishonest majorities and active corruptions. To this end, we first analyse why current definitions of computational DP are unsuitable for this setting and introduce a new version of computational DP, SIM$^*$-
    CDP. We then demonstrate the merit of this new definition by proving that our protocol satisfies it. Further, we use the protocol to compute two-party inner products with computational DP and with similar levels of accuracy as in the central model, being
    the first to do so. Finally, we provide an open-sourced implementation of our protocol and benchmark its practical performance.



    ## 2024/5

    * Title: The Multiple Millionaires’ Problem
    * Authors: Tamir Tassa, Avishay Yanai
    * [Permalink](https://eprint.iacr.org/2024/005)
    * [Download](https://eprint.iacr.org/2024/005.pdf)

    ### Abstract

    We study a fundamental problem in Multi-Party Computation, which we call the Multiple Millionaires’ Problem (MMP). Given a set of private integer inputs, the problem is to identify the subset of inputs that equal the maximum (or minimum) of that set,
    without revealing any further information on the inputs beyond what is implied by the desired output.
    Such a problem is a natural extension of the Millionaires’ Problem, which is the very first Multi-Party Computation problem that was presented in Andrew Yao’s seminal work [31]. A closely related problem is MaxP, in which the value of the maximum is
    sought. We propose several approaches towards the solution of those fundamental problems as well as concrete solutions, and compare their performance. As applications of privacy-preserving computation are more and more commonly implemented in industrial
    systems, MMP and MaxP become important building blocks in privacy-preserving statistics, machine learning, auctions and other domains. One of the prominent advantages of our novel protocols is their simplicity. As they solve fundamental problems that are
    essential building blocks in various application scenarios, we believe that our systematic study of solutions to those problems, and the comparison between them, will serve well future researchers and practitioners of secure distributed computing.



    ## 2024/6

    * Title: Towards general-purpose program obfuscation via local mixing
    * Authors: Ran Canetti, Claudio Chamon, Eduardo Mucciolo, Andrei Ruckenstein * [Permalink](https://eprint.iacr.org/2024/006)
    * [Download](https://eprint.iacr.org/2024/006.pdf)

    ### Abstract

    We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided
    by reversible circuits, but no additional algebraic structure.

    We start by formulating a new (and relatively weak) obfuscation task regarding the ability to obfuscate random circuits of bounded length. We call such obfuscators random input & output (RIO) obfuscators. We then show how to construct
    indistinguishability obfuscators for all (unbounded length) circuits given only an RIO obfuscator --- under a new assumption regarding the pseudorandomness of sufficiently long random reversible circuits with known functionality, which in turn builds
    on a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits.
    Furthermore, the constructed obfuscators satisfy a new measure of security - called random output indistinguishability (ROI) obfuscation - which is significantly stronger than IO and may be of independent interest.


    We then investigate the possibility of constructing RIO obfuscators using local, functionality preserving perturbations. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its
    functionality. We provide candidate constructions along with a pathway for analyzing the security of such strategies.

    Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks under hardness assumptions that are very different from standard ones. Furthermore, our specific
    candidate obfuscators are relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter k has n wires and poly(n,k)m gates. We hope that our initial exploration will motivate further study of this
    alternative path to cryptography.



    ## 2024/7

    * Title: Password Protected Universal Thresholdizer
    * Authors: Sabyasachi Dutta, Partha Sarathi Roy, Reihaneh Safavi-Naini, Willy Susilo
    * [Permalink](https://eprint.iacr.org/2024/007)
    * [Download](https://eprint.iacr.org/2024/007.pdf)

    ### Abstract

    Universal thresholdizer (UT) was proposed by Boneh et al. in CRYPTO'18 as a general framework for thresholdizing non-threshold cryptographic primitives where a set of $N$ servers, each gets a share such that any set of $k$ servers, each produces a
    partial result, which can be combined to generate the final result. In many applications of threshold cryptography such as the protection of private keys in a digital wallet, the combining operation of partial results must be protected. In this paper, we
    extend the UT framework to include password authentication for such protection. We formalize the notion of password protected universal thresholdizer (PPUT) that requires the knowledge of a password to execute the protocol, propose a general construction
    of PPUT, and prove its security. Our construction uses threshold password authenticated key exchange (TPAKE) with simulation-based security as one of the main building blocks. We define simulation-based security of TPAKE in stand-alone model and give a
    construction using threshold fully-homomorphic encryption. As an application of PPUT, we propose a new primitive called password protected threshold signature. All the proposed constructions are secure in the standard model, and can be instantiated from
    lattices.



    ## 2024/8

    * Title: SoK: Methods for Sampling Random Permutations in Post-Quantum Cryptography
    * Authors: Alessandro Budroni, Isaac A. Canales-Martínez, Lucas Pandolfo Perin * [Permalink](https://eprint.iacr.org/2024/008)
    * [Download](https://eprint.iacr.org/2024/008.pdf)

    ### Abstract

    In post-quantum cryptography, permutations are frequently employed to construct cryptographic primitives. Careful design and implementation of sampling random unbiased permutations is essential for efficiency and protection against side-channel attacks.
    Nevertheless, there is a lack of systematic research on this topic. Our work seeks to fill this gap by studying the most prominent permutation sampling algorithms and assessing their advantages and limitations. We combine theoretical and experimental
    comparisons and provide a C library with the implementations of the algorithms discussed. Furthermore, we introduce a new sampling algorithm tailored for cryptographic applications.



    ## 2024/9

    * Title: Distributed Protocols for Oblivious Transfer and Polynomial Evaluation * Authors: Aviad Ben Arie, Tamir Tassa
    * [Permalink](https://eprint.iacr.org/2024/009)
    * [Download](https://eprint.iacr.org/2024/009.pdf)

    ### Abstract

    A secure multiparty computation (MPC) allows several parties to
    compute a function over their inputs while keeping their inputs private. In its basic setting, the protocol involves only parties that hold
    inputs. In distributed MPC, there are also external servers who perform
    a distributed protocol that executes the needed computation, without
    learning information on the inputs and outputs. Here we propose distributed protocols for several fundamental MPC functionalities. We
    begin with a Distributed Scalar Product (DSP) protocol for computing
    scalar products of private vectors. We build upon DSP in designing
    various protocols for Oblivious Transfer (OT): k-out-of-N OT, Priced
    OT, and Generalized OT. We also use DSP for Oblivious Polynomial
    Evaluation (OPE) and Oblivious Multivariate Polynomial Evaluation
    (OMPE). All those problems involve a sender and a receiver, both of
    whom hold private vectors; the goal is to let the receiver learn the
    scalar product of those two vectors. However, in each of these problems the receiver must submit a vector of a specified form. Hence, a
    crucial ingredient in our protocols is a sub-protocol for validating that
    the receiver’s vector complies with the relevant restrictions, without learning anything else on that vector. Therefore, while previous studies presented distributed protocols for 1-out-of-N OT and OPE, our
    protocols are the first ones that are secure against malicious receivers.
    Our distributed protocols for the other OT variants and for OMPE
    are the first ones that handle such problems. In addition, while previous art assumed semi-honest servers, we present protocols that are
    secure even when some of the servers are malicious. Our protocols
    offer information-theoretic security and they are very efficient.



    ## 2024/10

    * Title: On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs
    * Authors: Sulaiman Alhussaini, Craig Collett, Serge˘ı Sergeev
    * [Permalink](https://eprint.iacr.org/2024/010)
    * [Download](https://eprint.iacr.org/2024/010.pdf)

    ### Abstract

    Since the existing tropical cryptographic protocols are either susceptible to the Kotov-Ushakov attack and its generalization, or to attacks based on tropical matrix periodicity and predictive behaviour, several attempts have been made to propose
    protocols that resist such attacks. Despite these attempts, many of the proposed protocols remain vulnerable to attacks targeting the underlying hidden problems, one of which we call the tropical two-sided discrete logarithm with shift. An illustrative
    case is the tropical Stickel protocol, which, when formulated with a single monomial instead of a polynomial, becomes susceptible to attacks based on solutions of the above mentioned tropical version of discrete logarithm. In this paper we will formally
    introduce the tropical two-sided discrete logarithm with shift, discuss how it is solved, and subsequently demonstrate an attack on a key exchange protocol based on the tropical semiring of pairs. This particular protocol is compromised due to the
    existence of efficient (albeit heuristic) solution of the tropical two-sided logarithm problem, and this highlights the ongoing challenges in search of a "good" key exchange protocol in tropical cryptography.



    ## 2024/11

    * Title: MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier
    * Authors: Daniel Noble, Brett Hemenway Falk, Rafail Ostrovsky
    * [Permalink](https://eprint.iacr.org/2024/011)
    * [Download](https://eprint.iacr.org/2024/011.pdf)

    ### Abstract

    This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
    That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

    This comes as a surprise, since the Goldreich-Ostrovsky lower bound shows that the related problem of Oblivious RAMs requires logarithmic overhead in the number of memory locations accessed. It was shown that this bound also applies in the multi-server
    ORAM setting, and therefore also applies in the DORAM setting. Achieving sub-logarithmic communication therefore requires accessing and using $\Omega(\log(n) \cdot d)$ bits of memory, without engaging in communication for each bit accessed. Techniques
    such as Fully Homomorphic Encryption and Function Secret Sharing allow secure selection of the relevant memory locations with small communication overhead, but introduce computational assumptions.

    In this paper we show that it is possible to avoid a logarithmic communication overhead even without any computational assumptions.
    Concretely, we present a 3-party honest-majority DORAM that is secure against semi-honest adversaries. The protocol has communication cost $$\Theta\left((\log^2(n) + d) \cdot \frac{\log(n)}{\log(\log(n)}\right)$$ For any $d = \Omega(\log^2(n))$ the
    overhead is therefore $\Theta(\log(n)/\log(\log(n)))$. Additionally, we show a subtle flaw in a common approach for analyzing the security of Oblivious Hash Tables.
    We prove our construction secure using an alternative approach.



    ## 2024/12

    * Title: Two-Round ID-PAKE with strong PFS and single pairing operation
    * Authors: Behnam Zahednejad, Gao Chong-zhi
    * [Permalink](https://eprint.iacr.org/2024/012)
    * [Download](https://eprint.iacr.org/2024/012.pdf)

    ### Abstract

    IDentity-based Password Authentication and Key Establishment (ID-PAKE) is an interesting trade-off between the security and efficiency, specially due to the removal of costly Public Key Infrastructure (PKI). However, we observe that previous PAKE schemes
    such as Beguinet et al. (ACNS 2023), Pan et al. (ASIACRYPT 2023) , Abdallah et al. (CRYPTO 2020) etc.
    fail to achieve important security properties such as weak/strong Perfect Forward Secrecy (s-PFS), user authentication and resistance to replay attack. In addition, to the best of our knowledge, no previous (P)AKE (either ID- based or PKI-based (P)AKEs)
    could achieve s-PFS with two-rounds of communication. In this paper,
    we propose a highly efficient ID-PAKE scheme with s-PFS and KGC-FS using only two rounds of communication, where each party only performs a single pairing operation. We compare our work with previous single pairing-based schemes i.e. Tomida et al. (
    ESORICS 2019) and Lian et al. (ESORICS 2020) and show that they suffer either s-PFS, KGC-FS attack and replay attack.
    In order to achieve a privacy-preserving PAKE scheme, we give a fix to Lian et al. (ESORICS 2020) in terms of KGC-FS and user authentication.

    We prove the security of our scheme under standard assumptions such as Discrete Logarithms (DL) and q-strong Diffie-Hellman(q-sDH) assumption in ID-eCK model. Finally, we conduct a proof-of-concept implementation of our scheme vs. previous single pairing-
    based schemes and show that our scheme imposes the least computation cost and stands in the middle of previous scheme regarding communication cost.



    ## 2024/13

    * Title: A note on ``intelligent drone-assisted robust lightweight multi-factor authentication for military zone surveillance in the 6G era''
    * Authors: Zhengjun Cao, Lihua Liu
    * [Permalink](https://eprint.iacr.org/2024/013)
    * [Download](https://eprint.iacr.org/2024/013.pdf)

    ### Abstract

    We show that the authentication scheme [Comput. Networks, 225 (2023), 109664] is flawed. (1) Some parameters are not specified. (2) Some computations are inconsistent. (3) It falsely require the control gateway to share its private key with the medical
    expert. (4) The scheme fails to keep user anonymity, not as claimed.



    ## 2024/14

    * Title: A Lattice-based Accountable Subgroup Multi-signature Scheme with Verifiable Group Setup
    * Authors: Ahmet Ramazan Ağırtaş, Oğuz YAYLA
    * [Permalink](https://eprint.iacr.org/2024/014)
    * [Download](https://eprint.iacr.org/2024/014.pdf)

    ### Abstract

    An accountable subgroup multi-signature (ASM) is a multi-signature that allows any subgroup of potential signers to jointly sign a message such that the subgroup of co-signers are accountable for the resulting signature and their identities are
    identifiable to any verifier. In this paper, we pro- pose a novel lattice-based accountable subgroup multi-signature scheme, i.e., vMS2, by combining the group setup method of recently proposed vASM scheme and Damgard et al.’s lattice-based MS2 multi-
    signature scheme. Key generation, signature generation and verification phases of our proposed scheme are almost identical to the MS2 scheme. In the group setup phase, we generate membership keys which is used for signing a message on behalf of a group G
    of users. These membership keys are generated via a joint verifiable secret sharing (VSS) scheme in a way that they include a piece of information from the secret keys of all users in G so that any subgroup of users in G having a valid membership key can
    sign in an accountable fashion. We also present a comparison of the underlying MS2 scheme and our accountable subgroup multi-signature scheme vMS2 to show the cost of accountability. We see that lattice-based accountable subgroup multi-signature scheme
    can be achieved by adding a one-time one-round group setup whose cost is slightly higher than signature generation and verification of the underlying MS2 signature scheme.



    ## 2024/15

    * Title: Unconditionally secure MPC for Boolean circuits with constant online communication
    * Authors: Zhenkai Hu, Kang Yang, Yu Yu
    * [Permalink](https://eprint.iacr.org/2024/015)
    * [Download](https://eprint.iacr.org/2024/015.pdf)

    ### Abstract

    Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved.
    In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires $12 \log(5n/4)$ bits of online
    communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known.

    In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number $n$ of parties. We
    first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol.
    In particular, our protocol achieves the amortized communication cost $36$ bits per AND gate in the online phase and $30n+24$ bits per AND gate in the offline phase.



    ## 2024/16


    [continued in next message]

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