[go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?




Dates are inconsistent

Dates are inconsistent

234 results sorted by ID

2024/1858 (PDF) Last updated: 2024-11-14
(In)Security of Threshold Fully Homomorphic Encryption based on Shamir Secret Sharing
Wonhee Cho, Jiseung Kim, Changmin Lee
Attacks and cryptanalysis

Boneh et al. (CRYPTO'18) proposed two $t$-out-of-$N$ threshold fully homomorphic encryption ($\sf TFHE$) schemes based on Shamir secret sharing scheme and $\{0,1\}$-linear secret sharing scheme. They demonstrated the simulation security, ensuring no information leakage during partial or final decryption. This breakthrough allows any scheme to be converted into a threshold scheme by using $\sf TFHE$. We propose two polynomial time algorithms to break the simulation security of...

2024/1831 (PDF) Last updated: 2024-11-07
Fast Two-party Threshold ECDSA with Proactive Security
Brian Koziel, S. Dov Gordon, Craig Gentry
Cryptographic protocols

We present a new construction of two-party, threshold ECDSA, building on a 2017 scheme of Lindell and improving his scheme in several ways. ECDSA signing is notoriously hard to distribute securely, due to non-linearities in the signing function. Lindell's scheme uses Paillier encryption to encrypt one party's key share and handle these non-linearities homomorphically, while elegantly avoiding any expensive zero knowledge proofs over the Paillier group during the signing process. However,...

2024/1781 (PDF) Last updated: 2024-10-31
New results in Share Conversion, with applications to evolving access structures
Tamar Ben David, Varun Narayanan, Olga Nissenbaum, Anat Paskin-Cherniavsky
Foundations

We say there is a share conversion from a secret sharing scheme $\Pi$ to another scheme $\Pi'$ implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret sharing under $\Pi$ to a valid (but not necessarily random) secret sharing under $\Pi'$ of the same secret. If such a conversion exists, we say that $\Pi\ge\Pi'$. This notion was introduced by Cramer et al. (TCC'05), where they particularly proved that for...

2024/1599 (PDF) Last updated: 2024-10-08
Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes
Bar Alon, Amos Beimel, Or Lasri
Cryptographic protocols

We consider 3 related cryptographic primitives, private information retrieval (PIR) protocols, conditional disclosure of secrets (CDS) protocols, and secret-sharing schemes; these primitives have many applications in cryptography. We study these primitives requiring information-theoretic security. The complexity of these primitives has been dramatically improved in the last few years are they are closely related, i.e., the the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016) was...

2024/1596 (PDF) Last updated: 2024-10-08
Secret Sharing with Publicly Verifiable Deletion
Jonathan Katz, Ben Sela
Cryptographic protocols

Certified deletion, an inherently quantum capability, allows a party holding a quantum state to prove that they have deleted the information contained in that state. Bartusek and Raizes recently studied certified deletion in the context of secret sharing schemes, and showed constructions with privately verifiable proofs of deletion that can be verified only by the dealer who generated the shares. We give two constructions of secret sharing schemes with publicly verifiable certified deletion....

2024/1477 (PDF) Last updated: 2024-09-21
Signature-based Witness Encryption with Compact Ciphertext
Gennaro Avitabile, Nico Döttling, Bernardo Magri, Christos Sakkas, Stella Wohnig
Public-key cryptography

Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag $T$ and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least $k$ different valid signatures w.r.t. $T$ and $k$ different verification keys out of the $n$ keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign...

2024/1394 (PDF) Last updated: 2024-09-13
SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra
Erki Külaots, Toomas Krips, Hendrik Eerikson, Pille Pullonen-Raudvere
Cryptographic protocols

Multiparty computation (MPC) is an important field of cryptography that deals with protecting the privacy of data, while allowing to do computation on that data. A key part of MPC is the parties involved having correlated randomness that they can use to make the computation or the communication between themselves more efficient, while still preserving the privacy of the data. Examples of these correlations include random oblivious transfer (OT) correlations, oblivious linear-function...

2024/1285 (PDF) Last updated: 2024-10-11
Robust Multiparty Computation from Threshold Encryption Based on RLWE
Antoine Urban, Matthieu Rambaud
Public-key cryptography

We consider protocols for secure multi-party computation (MPC) built from FHE under honest majority, i.e., for $n=2t+1$ players of which $t$ are corrupt, that are robust. Surprisingly there exists no robust threshold FHE scheme based on BFV to design such MPC protocols. Precisely, all existing methods for generating a common relinearization key can abort as soon as one player deviates. We address this issue, with a new relinearization key (adapted from [CDKS19, CCS'19]) which we show how to...

2024/1062 (PDF) Last updated: 2024-06-29
Compact Key Function Secret Sharing with Non-linear Decoder
Chandan Kumar, Sikhar Patranabis, Debdeep Mukhopadhyay
Foundations

We present a variant of Function Secret Sharing (FSS) schemes tailored for point, comparison, and interval functions, featuring compact key sizes at the expense of additional comparison. While existing FSS constructions are primarily geared towards $2$-party scenarios, exceptions such as the work by Boyle et al. (Eurocrypt 2015) and Riposte (S&P 2015) have introduced FSS schemes for $p$-party scenarios ($p \geq 3$). This paper aims to achieve the most compact $p$-party FSS key size to date....

2024/1053 (PDF) Last updated: 2024-06-28
Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC
Benny Applebaum, Eliran Kachlon
Foundations

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known for the case of binary, single-bit secrets. Current approaches often rely on so-called ramp secret sharing that achieves a constant share size at the expense of a slight gap...

2024/1045 (PDF) Last updated: 2024-06-27
Efficient Secret Sharing for Large-Scale Applications
Sarvar Patel, Giuseppe Persiano, Joon Young Seo, Kevin Yeo
Cryptographic protocols

Threshold secret sharing enables distributing a message to $n$ parties such that no subset of fewer than $t$ parties can learn the message, whereas any subset of at least $t$ parties can recover the message. Despite being a fundamental primitive, secret sharing still suffers from one significant drawback, where its message reconstruction algorithm is computationally expensive for large privacy thresholds $t$. In this paper, we aim to address this significant drawback. We study general...

2024/1025 (PDF) Last updated: 2024-06-25
Polynomial sharings on two secrets: Buy one, get one free
Paula Arnold, Sebastian Berndt, Thomas Eisenbarth, Maximilian Orlt
Implementation

While passive side-channel attacks and active fault attacks have been studied intensively in the last few decades, strong attackers combining these attacks have only been studied relatively recently. Due to its simplicity, most countermeasures against passive attacks are based on additive sharing. Unfortunately, extending these countermeasures against faults often leads to quite a significant performance penalty, either due to the use of expensive cryptographic operations or a large number...

2024/999 (PDF) Last updated: 2024-12-12
ProxCode: Efficient Biometric Proximity Searchable Encryption from Error Correcting Codes
Maryam Rezapour, Benjamin Fuller
Applications

This work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and oblivious multimaps. The multimap associates LSH outputs as keywords to biometrics as values. When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode that inserts shares of a linear secret...

2024/912 (PDF) Last updated: 2024-06-07
Quantum Evolving Secret Sharing for General Access Structures
Efrat Cohen, Anat Paskin-Cherniavsky
Foundations

In the useful and well studied model of secret-sharing schemes, there are $n$ parties and a dealer, which holds a secret. The dealer applies some randomized algorithm to the secret, resulting in $n$ strings, called shares; it gives the $i$'th share to the $i$'th party. There are two requirements. (1) correctness: some predefined subsets of the parties can jointly reconstruct the secret from their shares, and (2) security: any other set gets no information on the secret. The collection of...

2024/838 (PDF) Last updated: 2024-11-05
Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity
Ignacio Cascudo, Daniele Cozzo, Emanuele Giunta
Cryptographic protocols

In this paper we propose verifiable secret sharing (VSS) schemes secure for any honest majority in the synchronous model, and that only use symmetric-key cryptographic tools, therefore having plausibly post-quantum security. Compared to the state-of-the-art scheme with these features (Atapoor et al., Asiacrypt `23), our main improvement lies on the complexity of the ``optimistic'' scenario where the dealer and all but a small number of receivers behave honestly in the sharing phase: in this...

2024/837 (PDF) Last updated: 2024-05-28
Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions
Anders Dalskov, Daniel Escudero, Ariel Nof
Cryptographic protocols

We revisit the question of the overhead to achieve full security (i.e., guaranteed output delivery) in secure multiparty computation (MPC). Recent works have closed the gap between full security and semi-honest security, by introducing protocols where the parties first compute the circuit using a semi-honest protocol and then run a verification step with sublinear communication in the circuit size. However, in these works the number of interaction rounds in the verification step is also...

2024/821 (PDF) Last updated: 2024-05-26
A General Framework for Lattice-Based ABE Using Evasive Inner-Product Functional Encryption
Yao-Ching Hsieh, Huijia Lin, Ji Luo
Public-key cryptography

We present a general framework for constructing attribute-based encryption (ABE) schemes for arbitrary function class based on lattices from two ingredients, i) a noisy linear secret sharing scheme for the class and ii) a new type of inner-product functional encryption (IPFE) scheme, termed *evasive* IPFE, which we introduce in this work. We propose lattice-based evasive IPFE schemes and establish their security under simple conditions based on variants of evasive learning with errors (LWE)...

2024/772 (PDF) Last updated: 2024-12-19
Reducing the Share Size of Weighted Threshold Secret Sharing Schemes via Chow Parameters Approximation
Oriol Farràs, Miquel Guiot
Foundations

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In a weighted threshold access structure, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value. For these access structures, the share...

2024/582 (PDF) Last updated: 2024-08-18
Improved Alternating-Moduli PRFs and Post-Quantum Signatures
Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, Peter Rindal
Cryptographic protocols

We revisit the alternating-moduli paradigm for constructing symmetric-key primitives with a focus on constructing efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating-moduli paradigm of Boneh, Ishai, Passelègue, Sahai, and Wu (TCC 2018) enables the construction of various symmetric-key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli. The first contribution focuses on...

2024/470 (PDF) Last updated: 2024-05-29
Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, Damien Vergnaud
Cryptographic protocols

Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or...

2024/391 (PDF) Last updated: 2024-03-03
On Information-Theoretic Secure Multiparty Computation with Local Repairability
Daniel Escudero, Ivan Tjuawinata, Chaoping Xing
Cryptographic protocols

In this work we consider the task of designing information-theoretic MPC protocols for which the state of a given party can be recovered from a small amount of parties, a property we refer to as local repairability. This is useful when considering MPC over dynamic settings where parties leave and join a computation, a scenario that has gained notable attention in recent literature. Thanks to the results of (Cramer et al. EUROCRYPT'00), designing such protocols boils down to...

2024/286 (PDF) Last updated: 2024-02-20
Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head
Jules Maire, Damien Vergnaud
Cryptographic protocols

We present a novel technique within the MPC-in-the-Head framework, aiming to design efficient zero-knowledge protocols and digital signature schemes. The technique allows for the simultaneous use of additive and multiplicative sharings of secret information, enabling efficient proofs of linear and multiplicative relations. The applications of our technique are manifold. It is first applied to construct zero-knowledge arguments of knowledge for Double Discrete Logarithms (DDLP). The...

2024/244 (PDF) Last updated: 2024-11-26
Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Giuseppe D'Alconzo, Antonio J. Di Scala, Mukul Kulkarni
Attacks and cryptanalysis

The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely the Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with...

2024/147 (PDF) Last updated: 2024-07-13
Prime Masking vs. Faults - Exponential Security Amplification against Selected Classes of Attacks
Thorben Moos, Sayandeep Saha, François-Xavier Standaert
Implementation

Fault injection attacks are a serious concern for cryptographic hardware. Adversaries may extract sensitive information from the faulty output that is produced by a cryptographic circuit after actively disturbing its computation. Alternatively, the information whether an output would have been faulty, even if it is withheld from being released, may be exploited. The former class of attacks, which requires the collection of faulty outputs, such as Differential Fault Analysis (DFA), then...

2023/1912 (PDF) Last updated: 2024-09-20
Dishonest Majority Multiparty Computation over Matrix Rings
Hongqing Liu, Chaoping Xing, Chen Yuan, Taoxu Zou
Cryptographic protocols

The privacy-preserving machine learning (PPML) has gained growing importance over the last few years. One of the biggest challenges is to improve the efficiency of PPML so that the communication and computation costs of PPML are affordable for large machine learning models such as deep learning. As we know, linear algebra such as matrix multiplication occupies a significant part of the computation in deep learning such as deep convolutional neural networks (CNN). Thus, it is desirable to...

2023/1740 Last updated: 2024-06-28
Evaluation of Arithmetic Sum-of-Products Expressions in Linear Secret Sharing Schemes with a Non-Interactive Computation Phase
Miguel de Vega, Andrei Lapets, Stanislaw Jarecki, Wicher Malten, Mehmet Ugurbil, Wyatt Howe
Cryptographic protocols

Among secure multi-party computation protocols, linear secret sharing schemes often do not rely on cryptographic assumptions and are among the most straightforward to explain and to implement correctly in software. However, basic versions of such schemes either limit participants to evaluating linear operations involving private values or require those participants to communicate synchronously during a computation phase. A straightforward, information-theoretically secure extension to such...

2023/1652 (PDF) Last updated: 2024-06-11
On Sigma-Protocols and (packed) Black-Box Secret Sharing Schemes
Claudia Bartoli, Ignacio Cascudo
Cryptographic protocols

$\Sigma$-protocols are a widely utilized, relatively simple and well understood type of zero-knowledge proofs. However, the well known Schnorr $\Sigma$-protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups. In particular with hidden order groups, due to the inability of the knowledge extractor to invert elements modulo the order. In this paper,...

2023/1593 (PDF) Last updated: 2023-10-14
Multi-Party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN
Quang Dao, Yuval Ishai, Aayush Jain, Huijia Lin
Cryptographic protocols

Over the past few years, homomorphic secret sharing (HSS) emerged as a compelling alternative to fully homomorphic encryption (FHE), due to its feasibility from an array of standard assumptions and its potential efficiency benefits. However, all known HSS schemes, with the exception of schemes built from FHE or indistinguishability obfuscation (iO), can only support two or four parties. In this work, we give the first construction of a multi-party HSS scheme for a non-trivial function...

2023/1378 (PDF) Last updated: 2023-09-14
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
Benny Applebaum, Oded Nir
Cryptographic protocols

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and fully-decomposable randomized encoding (or garbling schemes). In fact, for all these primitives we do not even...

2023/1369 (PDF) Last updated: 2023-09-16
Ramp hyper-invertible matrices and their applications to MPC protocols
Hongqing Liu, Chaoping Xing, Yanjiang Yang, Chen Yuan
Cryptographic protocols

Beerliová-Trubíniová and Hirt introduced hyper-invertible matrix technique to construct the first perfectly secure MPC protocol in the presence of maximal malicious corruptions $\lfloor \frac{n-1}{3} \rfloor$ with linear communication complexity per multiplication gate [5]. This matrix allows MPC protocol to generate correct shares of uniformly random secrets in the presence of malicious adversary. Moreover, the amortized communication complexity of generating each sharing is linear. Due to...

2023/1307 (PDF) Last updated: 2023-09-01
Constant-Round Private Decision Tree Evaluation for Secret Shared Data
Nan Cheng, Naman Gupta, Aikaterini Mitrokotsa, Hiraku Morita, Kazunari Tozawa
Cryptographic protocols

Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private...

2023/1209 (PDF) Last updated: 2023-08-09
Infinite families of minimal binary codes via Krawtchouk polynomials
Xiaoni Du, René Rodríguez, Hao Wu
Foundations

Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general...

2023/1158 (PDF) Last updated: 2023-11-25
Improved Polynomial Secret-Sharing Schemes
Amos Beimel, Oriol Farràs, Or Lasri
Cryptographic protocols

Despite active research on secret-sharing schemes for arbitrary access structures for more than 35 years, we do not understand their share size $-$ the best known upper bound for an arbitrary n-party access structure is $2^{O(n)}$ while the best known lower bound is $\Omega(n/\log(n))$. Consistent with our knowledge, the share size can be anywhere between these bounds. To better understand this question, one can study specific families of secret-sharing schemes. For example, linear...

2023/1132 (PDF) Last updated: 2023-07-20
Cryptanalysis and Improvement of a Flexible and Lightweight Group Authentication Scheme
Ali Rezapour, Zahra Ahmadian
Attacks and cryptanalysis

Shamir’s secret sharing scheme is one of the substantial threshold primitives, based on which many security protocols are constructed such as group authentication schemes. Notwithstanding the unconditional security of Shamir's secret sharing scheme, protocols that are designed based on this scheme do not necessarily inherit this property. In this work, we evaluate the security of a lightweight group authentication scheme, introduced for IoT networks in IEEE IoT Journal in 2020, and prove its...

2023/1123 (PDF) Last updated: 2023-12-14
On the Cost of Post-Compromise Security in Concurrent Continuous Group-Key Agreement
Benedikt Auerbach, Miguel Cueto Noval, Guillermo Pascual-Perez, Krzysztof Pietrzak
Cryptographic protocols

Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The...

2023/1057 (PDF) Last updated: 2023-09-18
ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs for $\mathbb{Z}_{2^k}$
Lennart Braun, Cyprien Delpech de Saint Guilhem, Robin Jadoul, Emmanuela Orsini, Nigel P. Smart, Titouan Tanguy
Cryptographic protocols

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and...

2023/1033 (PDF) Last updated: 2024-08-19
OWF Candidates Based on: Xors, Error Detection Codes, Permutations, Polynomials, Interaction and Nesting
Paweł Cyprys, Shlomi Dolev, Oded Margalit
Foundations

Our research focuses on designing efficient commitment schemes by drawing inspiration from (perfect) information-theoretical secure primitives, e.g., the one-time pad and secret sharing. We use a random input as a mask for the committed value, outputting a function on the random input. Then, couple the output with the committed value xored with folded random input. First, we explore the potential of leveraging the unique properties of the one-time pad to design effective one-way functions....

2023/1012 (PDF) Last updated: 2023-07-24
Arithmetic Sketching
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai
Cryptographic protocols

This paper introduces arithmetic sketching, an abstraction of a primitive that several previous works use to achieve lightweight, low-communication zero-knowledge verification of secret-shared vectors. An arithmetic sketching scheme for a language $\mathcal{L} \in \mathbb{F}^n$ consists of (1) a randomized linear function compressing a long input x to a short “sketch,” and (2) a small arithmetic circuit that accepts the sketch if and only if $x \in \mathcal{L}$, up to some small error. If...

2023/838 (PDF) Last updated: 2023-08-23
How to Recover a Secret with O(n) Additions
Benny Applebaum, Oded Nir, Benny Pinkas
Foundations

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is being recovered and so the complexity, measured as the number of group multiplications over $G$, is equal to the number of $F$-additions that are needed to reconstruct...

2023/565 (PDF) Last updated: 2023-04-20
Decentralized Multi-Authority Attribute-Based Inner-Product FE: Large Universe and Unbounded
Pratish Datta, Tapas Pal
Public-key cryptography

This paper presents the first decentralized multi-authority attribute-based inner product functional encryption (MA-ABIPFE) schemes supporting vectors of a priori unbounded lengths. The notion of AB-IPFE, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption (ABE) with the possibility of evaluating linear functions on encrypted data. A decentralized MA-ABIPFE defined by Agrawal et al. [TCC 2021] essentially enhances the ABE...

2023/545 (PDF) Last updated: 2024-11-29
Improved Universal Thresholdizer from Iterative Shamir Secret Sharing
Jung Hee Cheon, Wonhee Cho, Jiseung Kim
Public-key cryptography

The universal thresholdizer, introduced at CRYPTO'18, is a cryptographic scheme that transforms any cryptosystem into a threshold variant, thereby enhancing its applicability in threshold cryptography. It enables black-box construction of one-round threshold signature schemes based on the Learning with Errors problem, and similarly, facilitates one-round threshold ciphertext-attack secure public key encryption when integrated with non-threshold schemes. Current constructions of universal...

2023/457 (PDF) Last updated: 2023-10-12
Registered FE beyond Predicates: (Attribute-Based) Linear Functions and more
Pratish Datta, Tapas Pal, Shota Yamada
Public-key cryptography

This paper introduces the first registered functional encryption RFE scheme tailored for linear functions. Distinctly different from classical functional encryption (FE), RFE addresses the key-escrow issue and negates the master key exfiltration attack. Instead of relying on a centralized trusted authority, it introduces a “key curator” - a fully transparent entity that does not retain secrets. In an RFE framework, users independently generate secret keys and subsequently register their...

2023/129 (PDF) Last updated: 2023-02-28
A Lower Bound on the Share Size in Evolving Secret Sharing
Noam Mazor
Foundations

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an online fashion, and there is no a-priory bound on the number of parties. An important complexity measure of a secret sharing scheme is the share size, which is the maximum number of bits that a...

2023/100 (PDF) Last updated: 2023-01-27
Meteor: Improved Secure 3-Party Neural Network Inference with Reducing Online Communication Costs
Ye Dong, Xiaojun Chen, Weizhan Jing, Kaiyun Li, Weiping Wang
Cryptographic protocols

Secure neural network inference has been a promising solution to private Deep-Learning-as-a-Service, which enables the service provider and user to execute neural network inference without revealing their private inputs. However, the expensive overhead of current schemes is still an obstacle when applied in real applications. In this work, we present \textsc{Meteor}, an online communication-efficient and fast secure 3-party computation neural network inference system aginst semi-honest...

2023/073 (PDF) Last updated: 2024-07-26
FssNN: Communication-Efficient Secure Neural Network Training via Function Secret Sharing
Peng Yang, Zoe Lin Jiang, Shiqi Gao, Hongxiao Wang, Jun Zhou, Yangyiye Jin, Siu-Ming Yiu, Junbin Fang
Cryptographic protocols

Privacy-preserving neural network based on secure multi-party computation (MPC) enables multiple parties to jointly train neural network models without revealing sensitive data. In privacy-preserving neural network, the high communication costs of securely computing non-linear functions is the primary performance bottleneck. For commonly used non-linear functions, such as ReLU, existing work adopts an offline-online computation paradigm and utilizes distributed comparison function (DCF) to...

2022/1648 (PDF) Last updated: 2024-12-03
Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs
Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Nitin Singh
Cryptographic protocols

Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some certification authority. We propose a generic...

2022/1632 (PDF) Last updated: 2023-06-27
Cryptography with Weights: MPC, Encryption and Signatures
Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, Yinuo Zhang
Foundations

The security of several cryptosystems rests on the trust assumption that a certain fraction of the parties are honest. This trust assumption has enabled a diverse of cryptographic applications such as secure multiparty computation, threshold encryption, and threshold signatures. However, current and emerging practical use cases suggest that this paradigm of one-person-one-vote is outdated. In this work, we consider {\em weighted} cryptosystems where every party is assigned a certain...

2022/1625 (PDF) Last updated: 2024-07-18
Efficient Threshold FHE for Privacy-Preserving Applications
Siddhartha Chowdhury, Sayani Sinha, Animesh Singh, Shubham Mishra, Chandan Chaudhary, Sikhar Patranabis, Pratyay Mukherjee, Ayantika Chatterjee, Debdeep Mukhopadhyay
Cryptographic protocols

Threshold Fully Homomorphic Encryption (ThFHE) enables arbitrary computation over encrypted data while keeping the decryption key distributed across multiple parties at all times. ThFHE is a key enabler for threshold cryptography and, more generally, secure distributed computing. Existing ThFHE schemes relying on standard hardness assumptions, inherently require highly inefficient parameters and are unsuitable for practical deployment. In this paper, we take a novel approach towards making...

2022/1578 (PDF) Last updated: 2023-02-10
Weighted Secret Sharing from Wiretap Channels
Fabrice Benhamouda, Shai Halevi, Lev Stambler
Foundations

Secret-sharing allows splitting a piece of secret information among a group of shareholders, so that it takes a large enough subset of them to recover it. In \emph{weighted} secret-sharing, each shareholder has an integer weight, and it takes a subset of large-enough weight to recover the secret. Schemes in the literature for weighted threshold secret sharing either have share sizes that grow linearly with the total weight, or ones that depend on huge public information (essentially a...

2022/1500 (PDF) Last updated: 2023-02-07
Registered Attribute-Based Encryption
Susan Hohenberger, George Lu, Brent Waters, David J. Wu
Public-key cryptography

Attribute-based encryption (ABE) generalizes public-key encryption and enables fine-grained control to encrypted data. However, ABE upends the traditional trust model of public-key encryption by requiring a single trusted authority to issue decryption keys. If an adversary compromises the central authority and exfiltrates its secret key, then the adversary can decrypt every ciphertext in the system. This work introduces registered ABE, a primitive that allows users to generate secret keys...

2022/1422 (PDF) Last updated: 2023-02-13
Unlinkable Policy-based Sanitizable Signatures
Ismail Afia, Riham AlTawy
Public-key cryptography

In CT-RSA 2020, P3S was proposed as the first policy-based sanitizable signature scheme which allows the signer to designate future message sanitizers by defining an access policy relative to their attributes rather than their keys. However, since P3S utilizes a policy-based chameleon hash (PCH), it does not achieve unlinkability which is a required notion in privacy-preserving applications. Moreover, P3S requires running a procedure to share the secret trapdoor information for PCH with each...

2022/1407 (PDF) Last updated: 2023-05-26
Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head
Thibauld Feneuil, Matthieu Rivain
Cryptographic protocols

The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations for small circuits proposed so far rely on additive secret sharing. In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general...

2022/1143 (PDF) Last updated: 2022-09-02
Threshold Linearly Homomorphic Encryption on $\mathbf{Z}/2^k\mathbf{Z}$
Guilhem Castagnos, Fabien Laguillaumie, Ida Tucker
Public-key cryptography

A threshold public key encryption protocol is a public key system where the private key is distributed among $n$ different servers. It offers high security since no single server is entrusted to perform the decryption in its entirety. It is the core component of many multiparty computation protocols which involves mutually distrusting parties with common goals. It is even more useful when it is homomorphic, which means that public operations on ciphertexts translate to operations on the...

2022/877 (PDF) Last updated: 2022-09-20
A New Approach to the Constant-Round Re-encryption Mix-Net
Myungsun Kim
Cryptographic protocols

The re-encryption mix-net (RMN) is a basic cryptographic tool that is widely used in the privacy protection domain and requires anonymity support; for example, it is used in electronic voting, web browsing, and location systems. To protect information about the relationship between senders and messages, a number of mix servers in RMNs shuffle and forward a list of input ciphertexts in a cascading manner. The output of the last mix server is decrypted to yield the set of original messages....

2022/862 (PDF) Last updated: 2024-11-08
Scooby: Improved Multi-Party Homomorphic Secret Sharing Based on FHE
Ilaria Chillotti, Emmanuela Orsini, Peter Scholl, Nigel Paul Smart, Barry Van Leeuwen
Cryptographic protocols

We present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first construction, which we call Scooby, is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. Scooby achieves an $n$-party HSS for general circuits with complexity $O(|F| + \log n)$, as opposed to $O(n^2 \cdot |F|)$ for the prior best construction based on multi-key...

2022/831 (PDF) Last updated: 2022-06-23
Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing
Vipul Goyal, Antigoni Polychroniadou, Yifan Song
Cryptographic protocols

In the last few years, the efficiency of secure multi-party computation (MPC) in the dishonest majority setting has increased by several orders of magnitudes starting with the SPDZ protocol family which offers a speedy information-theoretic online phase in the prepossessing model. However, state-of-the-art $n$-party MPC protocols in the dishonest majority setting incur online communication complexity per multiplication gate which is linear in the number of parties, i.e. $O(n)$, per gate...

2022/826 (PDF) Last updated: 2022-07-05
Pika: Secure Computation using Function Secret Sharing over Rings
Sameer Wagh
Cryptographic protocols

Machine learning algorithms crucially depend on non-linear mathematical functions such as division (for normalization), exponentiation (for softmax and sigmoid), tanh (as an activation function), logarithm (for cross-entropy loss), and square root (for back-propagation of normalization layers). However, when machine learning is performed over secure computation, these protocols incur a large communication overhead and high round complexity. In this work, we propose new multi-party...

2022/619 (PDF) Last updated: 2023-04-04
Breaking the $t< n/3$ Consensus Bound: Asynchronous Dynamic Proactive Secret Sharing under Honest Majority
Christophe Levrat, Matthieu Rambaud, Antoine Urban
Cryptographic protocols

A proactive secret sharing scheme (PSS), expressed in the dynamic-membership setting, enables a committee of n holders of secret-shares, dubbed as players, to securely hand-over new shares of the same secret to a new committee. We dub such a sub-protocol as a Refresh. All existing PSS under an honest majority, require the use of a broadcast (BC) in each refresh. BC is costly to implement, and its security relies on timing assumptions on the network. So the privacy of the secret and/or its...

2022/593 Last updated: 2022-05-25
On the Security Proof of CKO+21 Secret Sharing Scheme
Yupu Hu, Shanshan Zhang, Baocang Wang, Siyue Dong
Cryptographic protocols

On CRYPTO2021, Nishanth Chandran, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obattu, and Sruthi Sekar presented a novel secret sharing scheme, called CKO+21 scheme. This scheme makes use of Shamir secret sharing schemes and randomness extractors as its basic components, to generate a multi-layer encapsulation structure. The authors claimed that CKO+21 scheme satisfied “leakage resilience”, that is, the privacy still held under both “not enough revealing” and “appropriate leakage”. More...

2022/497 (PDF) Last updated: 2022-04-28
Protecting Distributed Primitives against Leakage: Equivocal Secret Sharing and More
Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
Applications

Leakage-resilient cryptography aims to protect cryptographic primitives from so-called "side channel attacks" that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO`03) and Micali and Reyzin (TCC`04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage,...

2022/461 (PDF) Last updated: 2022-05-16
Information Leakage in Code-based Masking: A Systematic Evaluation by Higher-Order Attacks
Wei Cheng, Sylvain Guilley, Jean-Luc Danger
Implementation

Code-based masking is a recent line of research on masking schemes aiming at provably counteracting side-channel attacks. It generalizes and unifies many masking schemes within a coding-theoretic formalization. In code-based masking schemes, the tuning parameters are the underlying linear codes, whose choice significantly affects the side-channel resilience. In this paper, we investigate the exploitability of the information leakage in code-based masking and present attack-based evaluation...

2022/427 (PDF) Last updated: 2022-04-06
Constant Size Secret Sharing: with General Thresholds, Towards Standard Assumptions, and Applications
Katarzyna Kapusta, Matthieu Rambaud, Ferdinand Sibleyras

We consider threshold Computational Secret Sharing Schemes, i.e., such that the secret can be recovered from any $t+1$ out of $n$ shares, and such that no computationally bounded adversary can distinguish between $t$ shares of a chosen secret and a uniform string. We say that such a scheme has Constant Size (CSSS) if, in the asymptotic regime of many shares of small size the security parameter, then the total size of shares reaches the minimum, which is the size of an erasures-correction...

2022/380 (PDF) Last updated: 2022-03-28
A Linear-Time 2-Party Secure Merge Protocol
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky
Cryptographic protocols

We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of...

2022/342 (PDF) Last updated: 2023-02-23
From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC Applications
Lorenzo Grassi, Morten Øygarden, Markus Schofnegger, Roman Walch
Secret-key cryptography

The area of multi-party computation (MPC) has recently increased in popularity and number of use cases. At the current state of the art, Ciminion, a Farfalle-like cryptographic function, achieves the best performance in MPC applications involving symmetric primitives. However, it has a critical weakness. Its security highly relies on the independence of its subkeys, which is achieved by using an expensive key schedule. Many MPC use cases involving symmetric pseudo-random functions (PRFs)...

2022/318 (PDF) Last updated: 2022-10-05
Efficient Online-friendly Two-Party ECDSA Signature
Haiyang Xue, Man Ho Au, Xiang Xie, Tsz Hon Yuen, Handong Cui
Cryptographic protocols

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not...

2022/242 (PDF) Last updated: 2022-12-05
YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model
Ignacio Cascudo, Bernardo David, Lydia Garms, Anders Konring
Cryptographic protocols

Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary's power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda et al. in TCC 2020, Gentry et al. in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (e.g. blockchains). In this model, instead of having all parties execute an entire...

2022/215 (PDF) Last updated: 2022-09-18
Multi-Client Functional Encryption with Fine-Grained Access Control
Ky Nguyen, Duong Hieu Phan, David Pointcheval
Public-key cryptography

Multi-Client Functional Encryption ($\mathsf{MCFE}$) and Multi-Input Functional Encryption ($\mathsf{MIFE}$) are very interesting extensions of Functional Encryption for practical purpose. They allow to compute joint function over data from multiple parties. Both primitives are aimed at applications in multi-user settings where decryption can be correctly output for users with appropriate functional decryption keys only. While the definitions for a single user or multiple users were quite...

2021/1642 (PDF) Last updated: 2021-12-17
SecNDP: Secure Near-Data Processing with Untrusted Memory
Wenjie Xiong, Liu Ke, Dimitrije Jankov, Michael Kounavis, Xiaochen Wang, Eric Northup, Jie Amy Yang, Bilge Acun, Carole-Jean Wu, Ping Tak Peter Tang, G. Edward Suh, Xuan Zhang, Hsien-Hsin S. Lee.
Secret-key cryptography

Today's data-intensive applications increasingly suffer from significant performance bottlenecks due to the limited memory bandwidth of the classical von Neumann architecture. Near-Data Processing (NDP) has been proposed to perform computation near memory or data storage to reduce data movement for improving performance and energy consumption. However, the untrusted NDP processing units (PUs) bring in new threats to workloads that are private and sensitive, such as private database queries...

2021/1532 (PDF) Last updated: 2022-05-30
On the Download Rate of Homomorphic Secret Sharing
Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, Mary Wootters
Cryptographic protocols

A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports evaluating functions on shared secrets by means of a local mapping from input shares to output shares. We initiate the study of the download rate of HSS, namely, the achievable ratio between the length of the output shares and the output length when amortized over $\ell$ function evaluations. We obtain the following results. * In the case of linear information-theoretic HSS schemes for degree-$d$...

2021/1115 (PDF) Last updated: 2021-09-03
Evolving Secret Sharing Schemes Based on Polynomial Evaluations and Algebraic Geometry Codes
Chaoping Xing, Chen Yuan
Foundations

A secret sharing scheme enables the dealer to share a secret among $n$ parties. A classic secret sharing scheme takes the number $n$ of parties and the secret as the input. If $n$ is not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev \cite[TCC 2016]{KNY16} first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work \cite[TCC 2016]{KNY16}, \cite[TCC 2017]{KC17} and \cite[Eurocrypt 2020]{BO20}, evolving...

2021/1025 (PDF) Last updated: 2021-08-06
Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings
Daniel Escudero, Eduardo Soria-Vazquez
Cryptographic protocols

We construct the first efficient MPC protocol that only requires black-box access to a non-commutative ring $R$. Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir's secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (IEEE Transactions on Information Theory, 2013)....

2021/885 (PDF) Last updated: 2021-06-29
MPC-Friendly Symmetric Cryptography from Alternating Moduli: Candidates, Protocols, and Applications
Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, Greg Zaverucha

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021). We make the following contributions. (Candidates). We propose new designs of symmetric primitives based on alternating moduli. These...

2021/822 (PDF) Last updated: 2023-12-14
One-out-of-$q$ OT Combiners
Oriol Farràs, Jordi Ribes-González
Foundations

In $1$-out-of-$q$ Oblivious Transfer (OT) protocols, a sender Alice is able to send one of $q\ge 2$ messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take $n$ instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the $n$ original OT instances are secure. We present new $1$-out-of-$q$ OT combiners that are perfectly...

2021/680 Last updated: 2022-02-01
Efficient Attribute Based Encryption for Boolean Circuits
Alexandru Ionita
Public-key cryptography

We provide a new technique for secret sharing and reconstruction for Boolean circuits, applicable in ABE systems. We show that our construction holds for Key-policy ABE and can be adapted also to Ciphertext-policy ABE. This is the most efficient solution for Attribute Based Encryption for circuits access structures using bilinear maps. Our KP-ABE system has decryption key of linear size in the number of attributes, and public parameters linear in the circuit size (Two public values for...

2021/505 (PDF) Last updated: 2021-04-19
Cryptanalysis of Boyen’s Attribute-Based Encryption Scheme in TCC 2013
Shweta Agrawal, Rajarshi Biswas, Ryo Nishimaki, Keita Xagawa, Xiang Xie, Shota Yamada
Public-key cryptography

In TCC 2013, Boyen suggested the first lattice based construction of attribute based encryption (ABE) for the circuit class $NC1$. Unfortunately, soon after, a flaw was found in the security proof of the scheme. However, it remained unclear whether the scheme is actually insecure, and if so, whether it can be repaired. Meanwhile, the construction has been heavily cited and continues to be extensively studied due to its technical novelty. In particular, this is the first lattice based ABE...

2021/503 (PDF) Last updated: 2021-11-08
Almost-Asynchronous MPC under Honest Majority, Revisited
Matthieu Rambaud, Antoine Urban
Cryptographic protocols

Multiparty computation does not tolerate $n/3$ corruptions under a plain asynchronous communication network, whatever the computational assumptions. However, Beerliová-Hirt-Nielsen [BHN, Podc'10] showed that, assuming access to a synchronous broadcast at the beginning of the protocol, enables to tolerate up to $t<n/2$ corruptions. This model is denoted as ``Almost asynchronous'' MPC. Yet, their work [BHN] has limitations: (i) \emph{Setup assumptions:} their protocol is based on an encryption...

2021/470 (PDF) Last updated: 2021-04-12
Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$
Benny Applebaum, Oded Nir

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$. In this paper, we focus on monotone functions that all their min-terms are sets of size $a$, and on their duals -- monotone functions whose max-terms...

2021/416 (PDF) Last updated: 2021-03-30
Cryptocurrencies with Security Policies and Two-Factor Authentication
Florian Breuer, Vipul Goyal, Giulio Malavolta
Applications

Blockchain-based cryptocurrencies offer an appealing alternative to Fiat currencies, due to their decentralized and borderless nature. However the decentralized settings make the authentication process more challenging: Standard cryptographic methods often rely on the ability of users to reliably store a (large) secret information. What happens if one user's key is lost or stolen? Blockchain systems lack of fallback mechanisms that allow one to recover from such an event, whereas the...

2021/371 (PDF) Last updated: 2021-05-02
Construction of minimal linear codes with few weights from weakly regular plateaued functions
Ahmet Sinak
Foundations

The construction of linear (minimal) codes from functions over finite fields has been greatly studied in the literature since determining the parameters of linear codes based on functions is rather easy due to the nice structures of functions. In this paper, we derive 3-weight and 4-weight linear codes from weakly regular plateaued unbalanced functions in the recent construction method of linear codes over the odd characteristic finite fields. The Hamming weights and their weight...

2021/363 (PDF) Last updated: 2021-04-15
Information Leakages in Code-based Masking: A Unified Quantification Approach
Wei Cheng, Sylvain Guilley, Claude Carlet, Jean-Luc Danger, Sihem Mesnager
Implementation

This paper presents a unified approach to quantifying the information leakages in the most general code-based masking schemes. Specifically, by utilizing a uniform representation, we highlight first that all code-based masking schemes' side-channel resistance can be quantified by an all-in-one framework consisting of two easy-to-compute parameters (the dual distance and the number of conditioned codewords) from a coding-theoretic perspective. In particular, we use signal-to-noise ratio (SNR)...

2021/285 (PDF) Last updated: 2022-02-24
Quadratic Secret Sharing and Conditional Disclosure of Secrets
Amos Beimel, Hussien Othman, Naty Peter
Cryptographic protocols

There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for arbitrary $n$-party access structures, and consistent with our current knowledge the optimal share size can be anywhere between polynomial in $n$ and exponential in $n$. For linear secret-sharing schemes, we know that the share size for almost all $n$-party access structures must be exponential in $n$. Furthermore, most constructions of efficient secret-sharing schemes are linear. We would...

2021/260 (PDF) Last updated: 2021-03-03
A Geometric Approach to Homomorphic Secret Sharing
Yuval Ishai, Russell W. F. Lai, Giulio Malavolta
Cryptographic protocols

An (n,m,t)-homomorphic secret sharing (HSS) scheme allows n clients to share their inputs across m servers, such that the inputs are hidden from any t colluding servers, and moreover the servers can evaluate functions over the inputs locally by mapping their input shares to compact output shares. Such compactness makes HSS a useful building block for communication-efficient secure multi-party computation (MPC). In this work, we propose a simple compiler for HSS evaluating multivariate...

2021/253 (PDF) Last updated: 2021-09-20
Improved single-round secure multiplication using regenerating codes
Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damgård, Chaoping Xing
Cryptographic protocols

In 2016, Guruswami and Wootters showed Shamir's secret-sharing scheme defined over an extension field has a regenerating property. Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares. Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been...

2021/195 (PDF) Last updated: 2021-02-24
Compilation of Function Representations for Secure Computing Paradigms
Karim Baghery, Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Nigel P. Smart, Titouan Tanguy
Cryptographic protocols

This paper introduces M-Circuits, a program representation which generalizes arithmetic and binary circuits. This new representation is motivated by the way modern multi-party computation (MPC) systems based on linear secret sharing schemes actually operate. We then show how this representation also allows one to construct zero knowledge proof (ZKP) systems based on the MPC-in-the-head paradigm. The use of the M-Circuit program abstraction then allows for a number of program-specific...

2021/159 (PDF) Last updated: 2022-02-08
hbACSS: How to Robustly Share Many Secrets
Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, Andrew Miller
Cryptographic protocols

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness---meaning guaranteed output delivery, including in the offline phase---in a network that even has intermittent delays. Importantly, several theoretical MPC constructions already ensure robustness in this setting. We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing...

2020/1615 (PDF) Last updated: 2021-01-01
An Ideal Compartmented Secret Sharing Scheme Based on Linear Homogeneous Recurrence Relations
Jiangtao Yuan, Guoai Xu, Guosheng Xu
Secret-key cryptography

Multipartite secret sharing schemes are those that have multipartite access structures. The set of the participants in those schemes is divided into several parts, and all the participants in the same part play the equivalent role. One type of such access structure is the compartmented access structure. We propose an ideal and efficient compartmented multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations. In the construction phase, the shared secrets are...

2020/1612 (PDF) Last updated: 2020-12-30
A New Efficient Hierarchical Multi-secret Sharing Scheme Based on Linear Homogeneous Recurrence Relations
Jiangtao Yuan, Jing Yang, Guoai Xu, Xingxing Jia, Fang-wei Fu, Chenyu Wang
Secret-key cryptography

Hierarchical secret sharing is an important key management technique since it is specially customized for hierarchical organizations with different departments allocated with different privileges, such as the government agencies or companies. Hierarchical access structures have been widely adopted in secret sharing schemes, where efficiency is the primary consideration for various applications. How to design an efficient hierarchical secret sharing scheme is an important issue. In 2007, a...

2020/1517 (PDF) Last updated: 2021-06-28
Constructing Locally Leakage-resilient Linear Secret-sharing Schemes
Hemanta Maji, Anat Paskin-Cherniavsky, Tom Suad, Mingyuan Wang
Foundations

Innovative side-channel attacks have repeatedly falsified the assumption that cryptographic implementations are opaque black-boxes. Therefore, it is essential to ensure cryptographic constructions' security even when information leaks via unforeseen avenues. One such fundamental cryptographic primitive is the secret-sharing schemes, which underlies nearly all threshold cryptography. Our understanding of the leakage-resilience of secret-sharing schemes is still in its preliminary stage. This...

2020/1453 (PDF) Last updated: 2020-11-19
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system
Jing Yang, Fang-Wei Fu
Cryptographic protocols

Secret sharing was proposed primarily in 1979 to solve the problem of key distribution. In recent decades, researchers have proposed many improvement schemes. Among all these schemes, the verifiable multi-secret sharing (VMSS) schemes are studied sufficiently, which share multiple secrets simultaneously and perceive malicious dealer as well as participants. By pointing out that the schemes presented by Dehkordi and Mashhadi in 2008 cannot detect some vicious behaviors of the dealer, we...

2020/1451 (PDF) Last updated: 2021-01-22
Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs
Elette Boyle, Niv Gilboa, Yuval Ishai, Ariel Nof
Cryptographic protocols

Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output. Protocols with {\em full security} (also known as {\em guaranteed output delivery}) in particular protect against denial-of-service attacks, guaranteeing that honest parties receive a correct output. This feature can be realized in the presence of an honest majority, and significant research effort has gone toward attaining full security with...

2020/1429 (PDF) Last updated: 2022-05-30
On Computational Shortcuts for Information-Theoretic PIR
Matthew M. Hong, Yuval Ishai, Victor I. Kolobov, Russell W. F. Lai
Cryptographic protocols

Information-theoretic private information retrieval (PIR) schemes have attractive concrete efficiency features. However, in the standard PIR model, the computational complexity of the servers must scale linearly with the database size. We study the possibility of bypassing this limitation in the case where the database is a truth table of a "simple" function, such as a union of (multi-dimensional) intervals or convex shapes, a decision tree, or a DNF formula. This question is motivated by...

2020/1396 (PDF) Last updated: 2020-11-10
Efficient Privacy Preserving Logistic Regression Inference and Training
Kyoohyung Han, Jinhyuck Jeong, Jung Hoon Sohn, Yongha Son
Public-key cryptography

Recently, privacy-preserving logistic regression techniques on distributed data among several data owners drew attention in terms of their applicability in federated learning environment. Many of them have been built upon cryptographic primitives such as secure multiparty computations(MPC) and homomorphic encryptions(HE) to protect the privacy of data. The secure multiparty computation provides fast and secure unit operations for arithmetic and bit operations but they often does not scale...

2020/1386 (PDF) Last updated: 2021-05-04
Decentralized Multi-Authority ABE for DNFs from LWE
Pratish Datta, Ilan Komargodski, Brent Waters
Public-key cryptography

We construct the first decentralized multi-authority attribute-based encryption (MA-ABE) scheme for a non-trivial class of access policies whose security is based (in the random oracle model) solely on the Learning With Errors (LWE) assumption. The supported access policies are ones described by DNF formulas. All previous constructions of MA-ABE schemes supporting any non-trivial class of access policies were proven secure (in the random oracle model) assuming various assumptions on...

2020/1256 (PDF) Last updated: 2020-10-15
Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z
Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, Matthieu Rambaud, Chaoping Xing, Chen Yuan
Cryptographic protocols

We study information-theoretic multiparty computation (MPC) protocols over rings $\mathbb{Z}/p^k \mathbb{Z}$ that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes $C$, such that $C$, $C^\perp$ and $C^2$ are asymptotically good (strongly...

2020/1179 (PDF) Last updated: 2020-09-30
Optimal Broadcast Encryption from LWE and Pairings in the Standard Model
Shweta Agrawal, Daniel Wichs, Shota Yamada
Public-key cryptography

Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry [BWZ14]. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada [AY20] improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of...

2020/961 (PDF) Last updated: 2020-08-11
Enable Dynamic Parameters Combination to Boost Linear Convolutional Neural Network for Sensitive Data Inference
Qizheng Wang, Wenping Ma, Jie Li, Ge Liu
Applications

As cloud computing matures, Machine Learning as a Service(MLaaS) has received more attention. In many scenarios, sensitive information also has a demand for MLaaS, but it should not be exposed to others, which brings a dilemma. In order to solve this dilemma, many works have proposed some privacy-protected machine learning frameworks. Compared with plain-text tasks, cipher-text inference has higher computation and communication overhead. In addition to the difficulties caused by cipher-text...

2020/691 (PDF) Last updated: 2021-08-10
Improved Threshold Signatures, Proactive Secret Sharing, and Input Certification from LSS Isomorphisms
Diego Aranha, Anders Dalskov, Daniel Escudero, Claudio Orlandi
Cryptographic protocols

In this paper we present a series of applications steming from a formal treatment of linear secret-sharing isomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field $\mathbb{F}$ and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the folklore idea that moving from a secret-sharing scheme over $\mathbb{F}_{p}$ to a secret sharing ``in the exponent'' can be done...

2020/483 (PDF) Last updated: 2020-04-28
On Ideal and Weakly-Ideal Access Structures
Reza Kaboli, Shahram Khazaei, Maghsoud Parviz
Foundations

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. We consider a weaker statement in this paper asking if: every ideal access structure admits an ideal perfect group-characterizable (GC) SSS. Since the class of GC SSSs is known to include the multi-linear ones (as well as several classes of non-linear schemes), it...

2020/448 (PDF) Last updated: 2022-07-24
Partial Secret Sharing Schemes
Amir Jafari, Shahram Khazaei
Foundations

The information ratio of an access structure is an important parameter for quantifying the efficiency of the best secret sharing scheme (SSS) realizing it. The most common security notion is perfect security. The following relaxations, in increasing level of security, have been presented in the literature: quasi-perfect, almost-perfect and statistical. Understanding the power of relaxing the correctness and privacy requirements in the efficiency of SSSs is a long-standing open problem....

2020/167 (PDF) Last updated: 2020-05-24
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
Jinhyun So, Basak Guler, A. Salman Avestimehr
Cryptographic protocols

Federated learning is gaining significant interests as it enables model training over a large volume of data that is distributedly stored over many users, while protecting the privacy of the individual users. However, a major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In fact, the overhead of state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. We propose a...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.