As database deployments shift toward cloud platforms and edge devices, thin clients need to securely retrieve sensitive records without leaking their query intent or metadata to the proxies that mediate access. Oblivious Transfer (OT) is a core tool for private retrieval, yet existing OTs assume direct client–database interaction and lack support for delegated querying or lightweight clients. We present Oblivis, a modular framework of new OT protocols that enable delegated, privacy-preserving query execution. Oblivis allows clients to retrieve database records without direct access, protects against leakage to both databases and proxies, and is designed with practical efficiency in mind. Its components include: (1) Delegated-Query OT, which permits secure outsourcing of query generation; (2) Multi-Receiver OT for merged, cloud-hosted databases; (3) a compiler producing constant-size responses suitable for thin clients; and (4) Supersonic OT, a proxy-based, information-theoretic, and highly efficient 1-out-of-2 OT. The protocols are formally defined and proven secure in the simulation-based paradigm, under non-colluding assumption. We implement and empirically evaluate Supersonic OT. It achieves at least a 92× speedup over a highly efficient 1-out-of-2 OT, and a 2.6×–106× speedup over a standard OT extension across 200–100,000 invocations. Our implementation further shows that Supersonic OT remains efficient even on constrained hardware, e.g., it completes an end-to-end transfer in 1.36 ms on a Raspberry Pi 4.

Nowadays Communication Security usually refers to digital communication and in particular via the Internet. We explain why the topic should be broadened to include any communication, in particular when done in person, e.g., with co-authors, colleagues, reporters, etc.

Secret sharing, a well-known cryptographic technique, introduced 40 years ago as a private and reliable variant of classical storage, has now become a major cryptographic primitive with numerous real-world applications. In this paper we consider the digital forensics aspects of secret sharing. We investigate the problem of framing which occurs when a coalition is able to calculate the share of a participant who does not belong to it. In the extreme case one authorized coalition can calculate shares of another authorized coalition and use the secret in some way blaming another authorized coalition for their action. In this context seniority plays an important role. We define seniority, which comes natural in the context of hierarchical access structures. Roughly speaking, our work shows that in an ideal secret sharing scheme an authorized coalition cannot frame participants who are less senior than all members of the coalition and is able to frame a participant who is more senior than at least one pivotal member of the coalition. We show that for any monotone access structure there exists a (non-ideal) frameproof secret sharing scheme.

For 35 years, the cryptographic community has created the impression that anonymous communication is always possible. Chaum's dining cryptographer's solution is regarded as achieving unconditional security. Chaum's MIX approach, namely, applying a uniformly random permutation on the plaintexts to be sent, is often given as a definition for anonymity. However, people working in law enforcement know that attempts by whistle-blowers and criminals to remain at large, often fail. The content of the message may reveal the name of the sender or may leak for whom the message is really intended. To understand this issue, we give a definition of perfect anonymity. We contrast our definition with Chaum's approach and discuss the impact on Chaum's dining cryptographer's solution.

In 2002, Wong-Wang-Wing presented a verifiable redistributing secret shares protocol, where the new parties must have been honest. They used Feldman's Verifiable Secret Sharing scheme, which assumed that the discrete logarithm is hard. In 2013, Nojoumian and Stinson presented information-theoretically (unconditionally) secure schemes under assumption that at most t out of 4t+1 parties are actively corrupt, where only the threshold (but not the number of parties) can be changed. We present an unconditionally secure solution assuming that at most t out of 3t+1 parties are actively corrupt. Our protocol uses properties of the parity-check matrix of a Generalized Reed-Solomon code. Moreover, we introduce a new open problem in the area of Reed-Solomon decoding.

One of the important problems in secret sharing schemes is to establish bounds on the size of the shares to be given to participants in secret sharing schemes. The other important problem in secret sharing schemes is to reduce the computational complexity in both secret distribution phase and secret reconstruction phase. In this paper, we design efficient threshold (n, k) secret sharing schemes to achieve both of the above goals. In particular, we show that if the secret size |s| is larger than max{1 + log2n, n(n - k)/(n - 1)}, then ideal secret sharing schemes exist. In the efficient ideal secret sharing schemes that we will construct, only XOR-operations on binary strings are required (which is the best we could achieve). These schemes will have many applications both in practice and in theory. For example, they could be used to design very efficient verifiable secret sharing schemes which will have broad applications in secure multi-party computation and could be used to design efficient privacy preserving data storage in cloud systems.

In the traditional voting manipulation literature, it is assumed that a group of manipulators jointly misrepresent their preferences to get a certain candidate elected, while the remaining voters are truthful. In this paper, we depart from this assumption, and consider the setting where all voters are strategic. In this case, the election can be viewed as a game, and the election outcomes correspond to Nash equilibria of this game. We use this framework to analyze two variants of Plurality voting, namely, simultaneous voting, where all voters submit their ballots at the same time, and sequential voting, where the voters express their preferences one by one. For simultaneous voting, we characterize the preference profiles that admit a pure Nash equilibrium, but show that it is computationally hard to check if a given profile fits our criterion. For sequential voting, we provide a complete analysis of the setting with two candidates, and show that for three or more candidates the equilibria of sequential voting may behave in a counterintuitive manner.

Secure communications guaranteeing reliability and privacy (without unproven assumptions) in networks with active adversaries has been an important research issue. It has been studied for point to point networks by Dolev-Dwork-Waarts-Yung (J. ACM1993), Desmedt–Wang (Eurocrypt 2002), and Srinathan–Narayanan–Rangan (Crypto 2004). Dolev–Dwork–Waarts–Yung gave necessary and sufficient conditions for secure communication in networks with the condition that 1) all the channels are two-way; or 2) all the channels are one-way from the sender to the receiver. In this paper, we study the general case with a network modeled by a directed graph. In this general case, there are communication channels from the sender to the receiver and there are feedback channels from the receiver to the sender. We give necessary and sufficient bounds on the number of channels that are required from sender to receiver given a number of “feedback” channels from receiver to sender. We give these bounds for the case reliability is perfect, as well as for the case it is not perfect.

We propose ring authentication in unconditionally secure setting. In a ring authentication system a sender can choose a set of users and construct an authenticated message for a receiver such that the receiver can verify authenticity of the message with respect to the user group chosen by the real sender. The sender will be unconditionally secure even if the receiver has corrupted up to c users and has access to up to ℓ past messages in the system. This functionality is similar to the one provided by ring signature systems with the difference that protection is against an adversary with unlimited power. (This also implies that the verification is not public and is by group members.) In ring signatures an adversary with unlimited computational power can always forge signed messages attributing them to groups of his choice. In our proposed systems the success chance of the adversary can be reduced to the required security of the system. We define model, propose a generic construction whose security is reduced to the security of its building blocks, and give concrete examples of this construction. The construction can also be used in computational setting resulting in ring authentication systems without public key cryptography.

Kohnfelder realized in 1978 that public key schemes require a Public Key Infrastructure (PKI) . X500/X509 were set up to standardize these ideas. PGP, proposed by Zimmermann is an alternative to the original PKI idea. Variants of the PGP based PKI were discussed independently by Reiter-Stubblebine and Burmester-Desmedt-Kabatianskii. The goal of Shamir’s 1984 idea of “identity-based” cryptography was to avoid a Public Key Infrastructure. Instead of having the users have their own public key, the identity of the user is the “public key,” and a trusted center provides each party with a secret key. Several identitybased cryptosystems have been proposed, in particular recently. We analyze Shamir’s identity-based concept critically. We argue the need for at least a registration infrastructure, which we call a”basic Identity-based Key Infrastructure.” Moreover, if secret keys of users can be stolen or lost, the infrastructure required to deal with this is as complex as the one of PKI. We make further comparisons between public key systems and identity-based ones.

Domain Name System (DNS) is the system for the mapping between easily memorizable host names and their IP addresses. Due to its criticality, security extensions to DNS have been proposed in an Internet Engineering Task Force (IETF) working group to provide authentication. We point out two difficulties in the current DNSSEC (DNS Security Extension) standards in the handling of DNS dynamic updates: the online storage of a zone security key, creating a single point of attack for both inside and outside attackers; and the violation of the role separation principle, which in the context of DNSSEC separates the roles of zone security managers from DNS server administrators. To address these issues, we propose a secure DNS architecture that is based on threshold cryptography. We show that the architecture adheres to the role separation principle without presenting any single point of attack. Our experimental results reveal that, in terms of signature computation times, our architecture incurs negligible performance penalty when using RSA/MD5 signatures but significant overhead when using DSA signatures. It is our belief that the high level of security that can be achieved by the proposed architecture far outweighs its potential overhead, especially in critical DNS zones, such as the .com zone.

Several organizations are setting up Public Key Infrastructures, examples are:the Corporation for Research and Educational Networking (CREN),• the Federal Government plans to fund 7 Public Key Infrastructure Models pilot programs at different federal agencies.However, experts have quite different viewpoints on how to set up such Public Key Infrastructure (PKI).Indeed, X500 and X509 are hierarchically organized (i.e.vertical), but PGP (see also Rivest-Lampson) is horizontally organized.Variants of PGP (see Reiter-Stubblebine (CCCS, ACM) and Burmester-Desmedt-Kabatianski (DIMACS)) require a minimum connectivity, i.e., a minimum number of disjoint paths in order to deal with hackers breaking into certifying entities (authorities).Moreover, Ellison-Schneier have questioned the need for a Public Key Infrastructure (PKI).Before one builds such an expensive infrastructure, experts should debate what method to use and whether a PKI is needed.While a hierarchical PKI may become the next target of computer hackers, a multiple-connected one seems much more expensive to build.

As already pointed out by other researchers, one of the central problems with applicability of visual cryptography is the random nature of its secret shares.It makes secret shares not suited for carrying or for transmission over an open channel.In this paper, we apply concepts of steganography t o create secret sharing schemes whose shares are realistically looking images.Our new technique is based on an idea of employing Moir e patterns for producing images.The advantage of this scheme over others is that it does not require a complicated algorithm, thus a computer, to decrypt the ciphertext.The cleartext can be read simply by putting the ciphertexts one onto the other.We therefore give a solution to the above mentioned problem with a novel type of visual secret sharing schemes, whose secrecy and anonymity are both satis ed.

We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP.

In this work we introduce and study threshold (t-out-of-n) secret sharing schemes for families of functions ${\cal F}$. Such schemes allow any set of at least t parties to compute privately the value f(s) of a (previously distributed) secret s, for any $f\in {\cal F}$. Smaller sets of players get no more information about the secret than what follows from the value f(s). The goal is to make the shares as short as possible. Results are obtained for two different settings: we study the case when the evaluation is done on a broadcast channel without interaction, and we examine what can be gained by allowing evaluations to be done interactively via private channels.

At the VIth Computer Security Foundations Workshop Simmons presented a protocol to make the Digital Signature Standard free of any subliminal channels. As Simmons has pointed out at several occasions the design of protocols is very difficult and one has claimed protocols to have certain properties, they turned out not to have. In this paper we demonstrate that Simmons' protocol is not free of any subliminal channels, by presenting a subliminal channel with a small capacity. We also discuss generalizations which imply that several already presented protocols claimed to be "subliminal-free" are not.

Article Free Access Share on How to share a function securely Authors: Alfredo De Santis Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), Italy Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), ItalyView Profile , Yvo Desmedt Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WI Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WIView Profile , Yair Frankel GTE Laboratories Incorporated, Waltham, MA GTE Laboratories Incorporated, Waltham, MAView Profile , Moti Yung IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 522–533https://doi.org/10.1145/195058.195405Published:23 May 1994Publication History 193citation1,775DownloadsMetricsTotal Citations193Total Downloads1,775Last 12 Months169Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A threshold scheme is an algorithm in which a distributor creates l shares of a secret such that a fixed minimum number $( t )$ of shares are needed to regenerate the secret. A perfect threshold scheme does not reveal anything new from an information theoretical viewpoint to $t - 1$ shareholders about the secret. When the entropy of the secret is zero all sharing schemes are perfect, so perfect sharing loses its intuitive meaning. The concept of zero-knowledge sharing scheme is introduced to prove that the distributor does not reveal anything, even from a computational viewpoint. New homomorphic perfect secret threshold schemes over any finite Abelian group for which the group operation and inverses are computable in polynomial time are developed. One of the new threshold schemes also satisfies the zero-knowledge property. A generalization toward a homomorphic zero-knowledge general sharing scheme over any finite Abelian group is discussed and it is proven that ideal homomorphic threshold schemes do not always exist.

Secure key distribution is a critical component in secure communications. Finding 'proven secure' practical key distribution systems is one of the major goals in cryptography. The Diffie-Hellman variants, a family of key distribution systems, achieve some of the objectives of this goal. In particular, the 'non-paradoxical' system (by Matsumoto-Takashima-Imai and Yacobi) is claimed to be secure against a known-key attack. In this paper we show that the argument used to prove this is flawed, and we explain how it can be fixed.

The security of modern networked computers is very low and must be dramatically improved.Integrity of data and programs is an essential aspect of computers.We propose approaches towards computer security in which the main trust is a cryptographically authenticated "keyboard".The achievability follows from the current trend towards personal computers, workstations and notebooks.We discuss how this could increase computer security and which problems remain to be solved in such an environment.

The authors extend the use of traditional point-to-point message authentication to multireceiver and/or multisender scenarios. They provide efficient cryptographic authentication methods for point-to-multipoint communication, where a single sender can broadcast (multicast) only one unconditionally secure authenticator for a message and which all receivers can verify. They further develop multipoint-to-point communication (incast) in which any subset (of a specified size) of a group of individuals can transmit a single authenticator (or a signature) for a message using the group's key. This method has been called threshold authentication. It is an application layer that is transparent to the receiver which only deals with the group as one entity. The bandwidth, computations, and storage overheads are reduced substantially when compared with the traditional approach. Threshold authentication hides some aspects of the internal structure of the group, which may be important in interenterprise communication.>

Secure identification is an important security issue to avoid computer fraud due to masquerading. This can be achieved with zero-knowledge based smart cards. We present very efficient new zero-knowledge schemes in a general algebraic setting. Particular cases of our scheme improve the performance of the Guillou–Quisquater and the Chaum–Evertse–van de Graaf schemes. Our scheme is formally proven and, overall, is more efficient than currently available schemes including the Fiat–Shamir scheme. As an application we discuss how our scheme can be used for identification, in particular as an electronic passport scheme.

The author describes the use of cryptographic authentication for controlling computer viruses. The objective is to protect against viruses infecting software distributions, updates, and programs stored or executed on a system. The authentication determines the source and integrity of an executable, relying on the source to produce virus-free software. The scheme relies on a trusted (and verifiable, where possible) device, the authenticator, used to authenticate and update programs and convert programs between the various formats. In addition, each user's machine uses a similar device to perform run-time checking.>

The authors claim that the security of the Merkle-Hellman algorithm is greatly exaggerated. First, any enciphering key that is obtained from a superincreasing sequence has infinitely many superincreasing deciphering keys that can decipher all messages. This follows from the fact that the conditions on the transformation^{\ast} w \bmod mrequirew/mto lie in a restricted set of intervals. Second, it is claimed that iterative transformations^{\ast} w \bmod mmay not increase the security. In the example that Merkle and Hellman used for "proving" the benefits of the iterative transformation, the security is completely ruined. Third, techniques are presented to crack one bit of the plaintext. These techniques apply to sets of enciphering keys introduced in this text, which contain all the Merkle-Hellman enciphering keys. Such bit-by-bit techniques also allow the construction of new enciphering keys. Fourth, some knapsacks that allow a one-to-one deciphering cannot be obtained from easy deciphering keys, e.g., superincreasing keys, even with infinitely many transformations^{\ast} w \bmod m!If the worst cases of nondeterministic polynomial complete knapsack problems are always of this kind, the foundation of the security of the Merkle-Hellman algorithm is nonexistent. The cryptanalysis can be reduced to a problem of simultaneous diophantine approximations. A link is made with other recent results.