Secrecy without one-way functions

DOI10.1515/GCC-2013-0002MaRDI QIDQ2873317zbMATH OpenOpenAlexFDO

Authors Vladimir Shpilrain, Dima Grigoriev

Publication date 23 January 2014

Published in Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5069

zbMATH Keywords

bit commitmentmental pokermultiparty computationsecret sharing

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Abstract: We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious "$PeNP$" conjecture. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal "intermediate results" of a computation. For example, when we compute the sum of $k$ numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of Yao's "millionaires' problem". Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a "dummy" (e.g., a computer) as the third party. We explain how our concept of a "dummy" is different from a well-known concept of a "trusted third party". We also suggest a protocol, without using a one-way function, for "mental poker", i.e., a fair card dealing (and playing) over distance. We also propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.

Recommendations

• Secure multiparty computation without one-way functions
• Non-interactive secure computation from one-way functions
• scientific article; zbMATH DE number 1497862
• Cryptography with One-Way Communication
• One-Way Functions and (Im)perfect Obfuscation
• Cryptography without (Hardly Any) Secrets ?
• Secrecy via Sources and Channels
• Functional encryption without obfuscation
• Constant round non-malleable protocols using one way functions

Cited in

(12)

• Yao's millionaires' problem and decoy-based public key encryption by classical physics
• Secrecy via Sources and Channels
• scientific article; zbMATH DE number 2185759 (Why is no real title available?)
• scientific article; zbMATH DE number 4191077 (Why is no real title available?)
• Cryptography with One-Way Communication
• scientific article; zbMATH DE number 58318 (Why is no real title available?)
• scientific article; zbMATH DE number 549858 (Why is no real title available?)
• scientific article; zbMATH DE number 826071 (Why is no real title available?)
• Secure computation without computers
• Secure multiparty computation without one-way functions
• Yao's millionaires' problem and public-key encryption without computational assumptions
• Secure Multiparty Computations Using a Dial Lock

This page was built for publication: Secrecy without one-way functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2873317)