International Association
for Cryptologic Research

Private computation on (labeled) set intersection (PCSI/PCLSI) is a secure computation protocol that allows two parties to compute fine-grained functions on set intersection, including cardinality, cardinality-sum, secret shared intersection and arbitrary functions. Recently, some computationally efficient PCSI protocols have emerged, but a limitation on these protocols is the communication complexity, which scales (super)-linear with the size of the large set. This is of particular concern when performing PCSI in the unbalanced case, where one party is a constrained device with a small set, and the other is a service provider holding a large set.

In this work, we first formalize a new ideal functionality called shared characteristic and its labeled variety called shared characteristic with labels, from which we propose the frameworks of PCSI/PCLSI protocols. By instantiating our frameworks, we obtain a series of efficient PCSI/PCLSI protocols, whose communication complexity is linear in the size of the small set, and logarithmic in the large set.

We demonstrate the practicality of our protocols with implementations. Experiment results show that our protocols outperform previous ones and the larger difference between the sizes of two sets, the better our protocols perform. For input set sizes $2^{10}$ and $2^{22}$ with items of length $128$ bits, our PCSI requires only $4.62$MB of communication to compute the cardinality; $4.71$MB of communication to compute the cardinality-sum. Compared with the state-of-the-art PCSI proposed by Chen et al., there are $ 58 \times$ and $77 \times$ reductions in the communication cost of computing cardinality and cardinality-sum.

We introduce a new data-independent priority queue which supports amortized polylogarithmic-time insertions and constant-time deletions, and crucially, (non-amortized) constant-time \textit{read-front} operations, in contrast with a prior construction of Toft (PODC'11). Moreover, we reduce the number of required comparisons. Data-independent data structures - first identified explicitly by Toft, and further elaborated by Mitchell and Zimmerman (STACS'14) - facilitate computation on encrypted data without branching, which is prohibitively expensive in secure computation. Using our efficient data-independent priority queue, we introduce a new privacy-preserving dark pool application, which significantly improves upon prior constructions which were based on costly sorting operations. Dark pools are securities-trading venues which attain ad-hoc order privacy, by matching orders outside of publicly visible exchanges. In this paper, we describe an efficient and secure dark pool (implementing a full continuous double auction), building upon our priority queue construction. Our dark pool's security guarantees are cryptographic - based on secure multiparty computation (MPC) - and do not require that the dark pool operators be trusted. Our approach improves upon the asymptotic and concrete efficiency attained by previous efforts. Existing cryptographic dark pools process new orders in time which grows linearly in the size of the standing order book; ours does so in polylogarithmic time. We describe a concrete implementation of our protocol, with malicious security in the honest majority setting. We also report benchmarks of our implementation, and compare these to prior works. Our protocol reduces the total running time by several orders of magnitude, compared to prior secure dark pool solutions.

This work introduces the notion of secure multiparty computation: MPC with fall-back security. Fall-back security for an $n$-party protocol is defined with respect to an adversary structure $\mathcal{Z}$ wherein security is guaranteed in the presence of both a computationally unbounded adversary with adversary structure $\mathcal{Z}$, and a computationally bounded adversary corrupting an arbitrarily large subset of the parties. This notion was considered in the work of Chaum (Crypto 89) via the Spymaster's double agent problem where he showed a semi-honest secure protocol for the honest majority adversary structure.

Our first main result is a compiler that can transform any $n$-party protocol that is semi-honestly secure with statistical security tolerating an adversary structure $\mathcal{Z}$ to one that (additionally) provides semi-honest fall-back security w.r.t $\mathcal{Z}$. The resulting protocol has optimal round complexity, up to a constant factor, and is optimal in assumptions and the adversary structure. Our second result fully characterizes when malicious fall-back security is feasible. More precisely, we show that malicious fallback secure protocol w.r.t $\mathcal{Z}$ exists if and only if $\mathcal{Z}$ admits unconditional MPC against a semi-honest adversary (namely, iff $\mathcal{Z} \in \mathcal{Q}^2$).

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 the language $\mathcal{L}$ has an arithmetic sketching scheme with short sketches, then it is possible to test membership in $\mathcal{L}$ using an arithmetic circuit with few multiplication gates. Since multiplications are the dominant cost in protocols for computation on secret-shared, encrypted, and committed data, arithmetic sketching schemes give rise to lightweight protocols in each of these settings.

Beyond the formalization of arithmetic sketching, our contributions are: – A general framework for constructing arithmetic sketching schemes from algebraic varieties. This framework unifies schemes from prior work and gives rise to schemes for useful new languages and with improved soundness error. – The first arithmetic sketching schemes for languages of sparse vectors: vectors with bounded Hamming weight, bounded $L_1$ norm, and vectors whose few non-zero values satisfy a given predicate. – A method for “compiling” any arithmetic sketching scheme for a language $\mathcal{L}$ into a low-communication malicious-secure multi-server protocol for securely testing that a client-provided secret-shared vector is in $\mathcal{L}$.

We also prove the first nontrivial lower bounds showing limits on the sketch size for certain languages (e.g., vectors of Hamming-weight one) and proving the non-existence of arithmetic sketching schemes for others (e.g., the language of all vectors that contain a specific value).

Statistical sender privacy (SSP) is the strongest achievable security notion for two-message oblivious transfer (OT) in the standard model, providing statistical security against malicious receivers and computational security against semi-honest senders. In this work we provide a novel construction of SSP OT from the Decisional Diffie-Hellman (DDH) and the Learning Parity with Noise (LPN) assumptions achieving (asymptotically) optimal amortized communication complexity, i.e. it achieves rate 1. Concretely, the total communication complexity for $k$ OT instances is $2k(1+o(1))$, which (asymptotically) approaches the information-theoretic lower bound. Previously, it was only known how to realize this primitive using heavy rate-1 FHE techniques [Brakerski et al., Gentry and Halevi TCC'19].

At the heart of our construction is a primitive called statistical co-PIR, essentially a a public key encryption scheme which statistically erases bits of the message in a few hidden locations. Our scheme achieves nearly optimal ciphertext size and provides statistical security against malicious receivers. Computational security against semi-honest senders holds under the DDH assumption.

Privacy-preserving machine learning (PPML) promises to train machine learning (ML) models by combining data spread across multiple data silos. Theoretically, secure multiparty computation (MPC) allows multiple data owners to train models on their joint data without revealing the data to each other. However, the prior implementations of this secure training using MPC have three limitations: they have only been evaluated on CNNs, and LSTMs have been ignored; fixed point approximations have affected training accuracies compared to training in floating point; and due to significant latency overheads of secure training via MPC, its relevance for practical tasks with streaming data remains unclear. The motivation of this work is to report our experience of addressing the practical problem of secure training and inference of models for urban sensing problems, e.g., traffic congestion estimation, or air pollution monitoring in large cities, where data can be contributed by rival fleet companies while balancing the privacy-accuracy trade-offs using MPC-based techniques. Our first contribution is to design a custom ML model for this task that can be efficiently trained with MPC within a desirable latency. In particular, we design a GCN-LSTM and securely train it on time-series sensor data for accurate forecasting, within 7 minutes per epoch. As our second contribution, we build an end-toend system of private training and inference that provably matches the training accuracy of cleartext ML training. This work is the first to securely train a model with LSTM cells. Third, this trained model is kept secret-shared between the fleet companies and allows clients to make sensitive queries to this model while carefully handling potentially invalid queries. Our custom protocols allow clients to query predictions from privately trained models in milliseconds, all the while maintaining accuracy and cryptographic security

We are looking for a PhD student with good background in maths and programming and with interest into side-channel attacks. The PhD student will explore the topic of combination of software countermeasures against side-channel attacks.

Closing date for applications:

Contact: PhD Nicolas BELLEVILLE, nicolas.belleville@cea.fr

More information: https://www.hipeac.net/jobs/14099/phd-combination-of-software-countermeasures-against-side-channel-attacks/

The CryptoLux group of the University of Luxembourg has a vacancy for a post-doctoral researcher in the area of security/privacy of blockchains and smart contracts. The successful candidate will contribute to a research project entitled Advanced Cryptography for Finance and Privacy (CryptoFin), which is funded by the Fonds National de la Recherche (FNR). Starting in September 2023, CryptoFin will run over a period of 3 years and be carried out in collaboration with the cryptography teams of Stanford University and Ethereum foundation. The mission of the CryptoFin project is to develop innovative solutions for some of the most pressing research problems in the blockchain domain, especially in the context of layer-2 protocols for off-chain transactions and the design of advanced cryptographic techniques like verifiable delay functions, proof-of-X systems with special features, and new MPC/SNARK-friendly primitives.

Candidates must hold a Ph.D. degree in cryptography, IT security, or a related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR conference/workshop or one of the top-4 security conferences. Experience in blockchains and/or smart contracts is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Applied cryptography (especially design/analysis of symmetric cryptosystems)
• Cryptofinance and cryptoeconomics
• Privacy and anonymity on the Internet

The position is initially offered for 1 year, but an extension by 2 years is possible. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Prof. Alex Biryukov before July 20, 2023 (early submission is encouraged). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), a list of publications, scans of diploma certificates, and contact details of 3 references.

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://cryptolux.org/index.php/Vacancies

The CryptoLux group of the University of Luxembourg has two vacancies for Ph.D. positions in the area of security/privacy of blockchains and smart contracts. The successful candidates will contribute to a research project entitled Advanced Cryptography for Finance and Privacy (CryptoFin), which is funded by the Fonds National de la Recherche (FNR). Starting in September 2023, CryptoFin will run over a period of 3 years and be carried out in collaboration with the cryptography teams of Stanford University and Ethereum foundation. The mission of the CryptoFin project is to develop innovative solutions for some of the most pressing research problems in the blockchain domain, especially in the context of layer-2 protocols for off-chain transactions and the design of advanced cryptographic techniques like verifiable delay functions, proof-of-X systems with special features, and new MPC/SNARK-friendly primitives.

Candidates must hold an M.Sc. degree (or earn an M.Sc. degree before September 2023) in computer science, mathematics, or a related field. Experience in blockchains and/or smart contracts is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

• Applied cryptography (especially design/analysis of symmetric cryptosystems)
• Cryptofinance and cryptoeconomics
• Privacy and anonymity on the Internet

Both positions are fully funded and initially offered for 3 years, but an extension to a 4th year is possible. The University of Luxembourg offers excellent working conditions and a highly competitive salary. Interested candidates are invited to send their application by email to Prof. Alex Biryukov before July 20, 2023 (early submission is encouraged). The application material should contain a cover letter explaining the candidate's research interests, a CV (incl. photo), scans of diploma certificates, and contact details of 3 references.

Closing date for applications:

Contact: Prof. Alex Biryukov (alex.biryukov@uni.lu)

More information: https://cryptolux.org/index.php/Vacancies

The newly stablished Cyber Security group is one of the core groups forming the faculty of Computer Science in the Technische Universität Darmstadt and National Research Center for Applied Cybersecurity (ATHENE). The research focus of the group is on the security of implementations. A large part of our research is dedicated to hardware security, protection against physical attacks (side-channel analysis and fault-injection attacks), security analysis of real-world systems particularly internet of things, and efficient hardware and software implementation of cryptographic primitives. This includes various implementation platforms like ASICs, FPGAs, and micro-processors.

The group is looking for excellent B.Sc. and M.Sc. graduates with outstanding grades and degrees in computer science, electrical engineering, and mathematics. In addition, we are looking for outstanding postdoctoral candidates from these fields. Initially, we offer three-year fully funded positions for B.Sc. and M.Sc. graduates. The expectation is to work towards a doctorate. Postdoctoral positions are initially offered a 2-year contract. Both PhD and Postdoctoral positions are subject to extensions. The salary will be according to the remuneration group E 13 TV-L (full time).

Our offerings:

• Excellent research environment with award-winning scientists,
• Open team culture,
• Programs designed to support parents,
• Support measures for women in IT security,
• Excellent support for doctoral and postdoctoral researchers,
• Opportunities for academic and professional development,
• Budget for courses, conferences, equipment and international exchange

Your application:

Are you interested? Please send your complete application documents in one single pdf file. The required documents are: Curriculum Vitae, transcript of records of BSc., transcript of records of MSc. (if applicable), two reference names (supervisors or other researchers with whom you worked).

Closing date for applications:

Contact: Amir Moradi (amir.moradi@rub.de)

We have a postdoc position available at SandboxAQ[1]. We are looking for people broadly interested in post-quantum cryptography. The position is remote in Europe but we have funds to allow travel to meet other team members. The position is initially for one year, but with the option to extend it to up to 3 years, on mutual agreement.

You can learn more about what we’ve been doing so far by checking out our publications page [2] or the individual DBPL pages of our permanent researchers:

• Carlos Aguilar Melchor (PQC Team) https://dblp.uni-trier.de/pid/71/4606.html
• Martin Albrecht (PQC Team) https://dblp.uni-trier.de/pid/92/7397.html
• Nina Bindel (PQC Team) https://dblp.uni-trier.de/pid/167/3021.html
• Nicolas Gama (Privacy Team) https://dblp.uni-trier.de/pid/49/4575.html
• Sandra Guasch (Privacy Team) https://dblp.uni-trier.de/pid/86/8292.html
• James Howe (PQC Team) https://dblp.uni-trier.de/pid/163/8680.html
• David Joseph (PQC Team) https://dblp.uni-trier.de/pid/27/884.html

We are committed to creating an inclusive culture where we have zero tolerance for discrimination. We invest in our employees' personal and professional growth.

To apply, submit an application at https://www.sandboxaq.com/careers-list?gh_jid=4914493004 Please submit your application by 15 July.

[1] https://www.sandboxaq.com/ [2] https://pub.sandboxaq.com/

Closing date for applications:

Contact:

• Martin Albrecht <martin.albrecht@sandboxquantum.com>
• Nina Bindel <nina.bindel@sandboxquantum.com>

More information: https://www.sandboxaq.com/careers-list?gh_jid=4914493004

Position is limited to 3 years, full time, with possibility for extension.

Tasks:

• Active research in the area of intrusion detection systems (IDS) for critical infrastructures, secure cyber-physical systems, and artificial intelligence / machine learning for traffic analysis
• Implementation and evaluation of new algorithms and methods
• Cooperation and knowledge transfer with industrial partners
• Publication of scientific results
• Assistance with teaching

Requirements:

• Master’s degree (or equivalent) and PhD degree (only for PostDocs) in Computer Science or related disciplines
• Strong interest in IT security and/or networking and distributed systems
• Knowledge of at least one programming language (C++, Java, etc.) and one scripting language (Perl, Python, etc.) or strong willingness to quickly learn new programming languages
• Linux/Unix skills
• Knowledge of data mining, machine learning, statistics and result visualization concepts is of advantage
• Excellent working knowledge of English; German is of advantage
• Excellent communication skills

For more information about the vacant position please contact Prof. A. Panchenko (E-Mail: itsec-jobs.informatik@lists.b-tu.de).

We value diversity and therefore welcome all applications – regardless of gender, nationality, ethnic and social background, religion/belief, disability, age, sexual orientation, and identity. The BTU Cottbus-Senftenberg strives for a balanced gender relation in all employee groups. Applicants with disabilities will be given preferential treatment if they are equally qualified.

Applications containing the following documents:

• A detailed Curriculum Vitae
• Transcript of records from your Master studies
• An electronic version of your Master thesis, if possible
should be sent in a single PDF file as soon as possible, but not later than 09.07.2023 at itsec-jobs.informatik@lists.b-tu.de.

Closing date for applications:

Contact: For more information about the vacant position please contact Prof. A. Panchenko (E-Mail: itsec-jobs.informatik@lists.b-tu.de)

More information: https://www.b-tu.de/en/fg-it-sicherheit

Are you fascinated by security in theory and/or practice? Are you willing to take on the challenge of securing the next generation of computer systems and networks? Do you like to work in a team of young researchers? Join our dynamic team as a Postdoctoral Researcher and contribute to ground-breaking research at the forefront of quantum technology!

Quantum technologies are advancing at an unprecedented pace. On one hand, the progress in developing quantum computers poses a significant threat to our security infrastructure, particularly concerning public-key cryptography. On the other hand, the integration of quantum communication and quantum data into our networks presents novel opportunities that can enhance security functionalities. However, at present, quantum components predominantly exist in experimental stages, and their security requires in-depth study and assessment.

Among the prominent applications of quantum networks is quantum key distribution (QKD), which theoretically offers superior security guarantees compared to classical cryptographic schemes. However, does the utilization of QKD truly provide tangible benefits over post-quantum cryptography? In the realistic context of trusted-node QKD networks, what kind of security guarantees can be proven depending on the deployed key-management system?

At a broader level, this postdoc position aims to investigate the advantages of exploiting quantum effects within the domain of security and explore the integration of quantum and classical security guarantees both in theory and practice.

The fully funded postdoc position will be within the Theory of Computer Science (TCS) group but will be carried out in close collaboration with researchers at QuSoft. The position is a part of the Quantum Delta NL growth fund project CAT-2, which focuses on the development of a national quantum network, and it will likely involve collaboration with the experimental and theoretical partners of the CAT-2 project.

Closing date for applications:

Contact: Christian Schaffner

More information: https://vacatures.uva.nl/UvA/job/PD/773632702/

Circuit-based Private Set Intersection (circuit-PSI) refers to cryptographic protocols that let two parties with input set $X$ and $Y$ compute a function $f$ over the intersection set $X \cap Y$, without revealing any other information. The research efforts for circuit-PSI mainly focus on the case where input set sizes $|X|$ and $|Y|$ are similar so far, and they scale poorly for extremely unbalanced set sizes $|X| \gg |Y|$. Recently, Lepoint \textit{et al.} (ASIACRYPT'21) proposed the first dedicated solutions for this problem, which has online cost only linear in the small set size $|Y|$. However, it requires an expensive setup phase that requires huge storage of about $O(|X|)$ on the small set holder side, which can be problematic in applications where the small set holder is assumed to have restricted equipment.

In this work, we suggest new efficient proposals for circuit-PSI tailored for unbalanced inputs, which feature {\emph{zero}} small set holder side storage, and comparable online phase performance to the previous work. At the technical core, we use homomorphic encryption (HE) based {\emph{plain}} PSI protocols of Cong \textit{et al.} (CCS'21), with several technically non-trivial arguments on algorithm and security.

We demonstrate the superiority of our proposals in several input set sizes by an implementation. As a representative example, for input sets of size $2^{24}$ and $2^{12}$, our proposals require {\emph{zero}} storage on the small set holder whereas Lepoint \textit{et al.} requires over $7$GB. The online phase remains similar; over LAN network setting, ours takes $7.5$ (or $20.9$s) seconds with $45$MB (or $11.7$MB) communication, while Lepoint \textit{et al.} requires $4.2$ seconds with $117$MB communication.

In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches: - The first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes. - The second one is to rewrite it as a bilinear system over Fq. Even if Gröbner basis techniques on this second system seem infeasible, we provide a detailed analysis of the first degree fall polynomials which arise when applying such algorithms.

Incompressibility is a popular security notion for white-box cryptography and captures that a large encryption program cannot be compressed without losing functionality. Fouque, Karpman, Kirchner and Minaud (FKKM) defined strong incompressibility, where a compressed program should not even help to distinguish encryptions of two messages of equal length. Equivalently, the notion can be phrased as indistinguishability under chosen-plaintext attacks and key-leakage (LK-IND-CPA), where the leakage rate is high.

In this paper, we show that LK-IND-CPA security with superlogarithmic-length leakage, and thus strong incompressibility, cannot be proven under standard (i.e. single-stage) assumptions, if the encryption scheme is key-fixing, i.e. a polynomial number of message-ciphertext pairs uniquely determine the key with high probability.

Our impossibility result refutes a claim by FKKM that their big-key generation mechanism achieves strong incompressibility when combined with any PRG or any conventional encryption scheme, since the claim is not true for encryption schemes which are key-fixing (or for PRGs which are injective). In particular, we prove that the cipher block chaining (CBC) block cipher mode is key-fixing when modelling the cipher as a truly random permutation for each key. Subsequent to and inspired by our work, FKKM prove that their original big-key generation mechanism can be combined with a random oracle into an LK-IND-CPA-secure encryption scheme, circumventing the impossibility result by the use of an idealised model.

Along the way, our work also helps clarifying the relations between incompressible white-box cryptography, big-key symmetric encryption, and general leakage resilient cryptography, and their limitations.

Consider the standard setting of two-party computation where the sender has a secret function $f$ and the receiver has a secret input $x$ and the output $f(x)$ is delivered to the receiver at the end of the protocol. Let us consider the unidirectional message model where only one party speaks in each round. In this setting, Katz and Ostrovsky (Crypto 2004) showed that at least four rounds of interaction between the parties are needed in the plain model (i.e., no trusted setup) if the simulator uses the adversary in a black-box way (a.k.a. black-box simulation). Suppose the sender and the receiver would like to run multiple sequential iterations of the secure computation protocol on possibly different inputs. For each of these iterations, do the parties need to start the protocol from scratch and exchange four messages?

In this work, we explore the possibility of \textit{amortizing} the round complexity or in other words, \textit{reusing} a certain number of rounds of the secure computation protocol in the plain model. We obtain the following results.

1. Under standard cryptographic assumptions, we construct a four-round two-party computation protocol where (i) the first three rounds of the protocol could be reused an unbounded number of times if the receiver input remains the same and only the sender input changes, and (ii) the first two rounds of the protocol could be reused an unbounded number of times if the receiver input needs to change as well. In other words, the sender sends a single additional message if only its input changes, and in the other case, we need one message each from the receiver and the sender. The number of additional messages needed in each of the above two modes is optimal and, additionally, our protocol allows arbitrary interleaving of these two modes. 2. We also extend these results to the multiparty setting (in the simultaneous message exchange model) and give round-optimal protocols such that (i) the first two rounds could be reused an unbounded number of times if the inputs of the parties need to change and (ii) the first three rounds could be reused an unbounded number of times if the inputs remain the same but the functionality to be computed changes. As in the two-party setting, we allow arbitrary interleaving of the above two modes of operation.

Vehicular Social Networks (VSNs) rely on data shared by users to provide convenient services. Data is outsourced to the cloud server and the distributed roadside unit in VSNs. However, roadside unit has limited resources, so that data sharing process is inefficient and is vulnerable to security threats, such as illegal access, tampering attack and collusion attack. In this article, to overcome the shortcomings of security, we define a chain tolerance semi-trusted model to describe the credibility of distributed group based on the anti tampering feature of blockchain. We further propose a Blockchain-based Lightweight Access Control scheme in VSNs that resist tampering and collusion attacks, called BLAC. To overcome the shortcomings of efficiency, we design a ciphertext piece storage algorithm and a recovery one to achieve lightweight storage cost. In the decryption operation, we separate a pre-decryption algorithm based on outsourcing to achieve lightweight decryption computation cost on the user side. Finally, we present the formal security analyses and the simulation experiments for BLAC, and compare the results of experiments with existing relevant schemes. The security analyses show that our scheme is secure, and the results of experiments show that our scheme is lightweight and practical.

ECVRF is a verifiable random function (VRF) scheme used in multiple cryptocurrency systems. It has recently been proven to satisfy the notion of non-malleability which is useful in applications to blockchains (Peikert and Xu, CT-RSA 2023); however, the existing proof uses the rewinding technique and has a quadratic security loss. In this work, we re-analyze the non-malleability of ECVRF in the algebraic group model (AGM) and give a tight proof. We also compare our proof with the unforgeability proof for the Schnorr signature scheme in the AGM (Fuchsbauer, Plouviez and Seurin, EUROCRYPT 2020).

It is well known that without randomization, Byzantine agreement (BA) requires a linear number of rounds in the synchronous setting, while it is flat out impossible in the asynchronous setting. The primitive which allows to bypass the above limitation is known as oblivious common coin (OCC). It allows parties to agree with constant probability on a random coin, where agreement is oblivious, i.e., players are not aware whether or not agreement has been achieved.

The starting point of our work is the observation that no known protocol exists for information-theoretic multi-valued OCC---i.e., OCC where the coin might take a value from a domain of cardinality larger than 2---with optimal resiliency in the asynchronous (with eventual message delivery) setting. This apparent hole in the literature is particularly problematic, as multi-valued OCC is implicitly or explicitly used in several constructions. (In fact, it is often falsely attributed to the asynchronous BA result by Canetti and Rabin [STOC ’93], which, however, only achieves binary OCC and does not translate to a multi-valued OCC protocol.)

In this paper, we present the first information-theoretic multi-valued OCC protocol in the asynchronous setting with optimal resiliency, i.e., tolerating $t
We then turn to the problem of round-preserving parallel composition of asynchronous BA. A protocol for this task was proposed by Ben-Or and El-Yaniv [Distributed Computing ’03]. Their construction, however, is flawed in several ways: For starters, it relies on multi-valued OCC instantiated by Canetti and Rabin's result (which, as mentioned above, only provides binary OCC). This shortcoming can be repaired by plugging in our above multi-valued OCC construction. However, as we show, even with this fix it remains unclear whether the protocol of Ben-Or and El-Yaniv achieves its goal of expected-constant-round parallel asynchronous BA, as the proof is incorrect. Thus, as a second contribution, we provide a simpler, more modular protocol for the above task. Finally, and as a contribution of independent interest, we provide proofs in Canetti's Universal Composability framework; this makes our work the first one offering composability guarantees, which are important as BA is a core building block of secure multi-party computation protocols.