程序代写代做代考 scheme Generalized Homomorphic MACs with Efficient Verification

Generalized Homomorphic MACs with Efficient Verification

Foundations of Cryptography
ElGamal Encryption, Oblivious Transfer,
Garbled Circuit

Recap
Public-Key Revolution:
Diffie-Hellman; Merkle; Rivest-Shamir-Adleman; Rabin
Man-in-the-middle Attack:
private-key: one access unlimited access of private + authenticated channel
public-key: authenticated channel private + authenticated channel
Public-Key Encryption:
resolve the issues of key distribution and key storage
significantly slower than private-key
Security:
IND-EAVIND-m-EAVIND-CPAIND-m-CPA
IND-CCAIND-m-CCA

OTP
One-Time Pad:
:
: for , output
: output
Perfect Secrecy: OTP is perfectly secret
for any

Abelian Group: A set together with a binary operation on
closure, associative, identity, inverse, commutative
Example:
is a cyclic group for any prime

Generalizing OTP
The Scheme: , a cyclic group of order (-bit prime)
:
: for , output
: output
Perfect Secrecy: generalized OTP is perfectly secret
for all

Diffie-Hellman Key Exchange:
Alice: ; send to Bob
Bob: ; send to Alice; output
Alice: output
Security: based on DDH assumption- Adversary cannot distinguish and

ElGamal Encryption
Background:
Taher ElGamal: “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, IEEE TIT, 1985
Taher Elgamal (1955- ), PhD student of Hellman at Stanford
basic idea: use as secret key in the generalized OTP
The Scheme:
: ;
:
: output
Correctness:
A Toy Example:

Implementation Issues
Small group? The discrete logarithm is not hard if is too small
And then DDH problem is also easy
Given extract from and then check
How large is used in practice? For example, for
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624225795083
Generate the parameters “once-and-for-all”//NIST
can be an order- subgroup of a group
can be an order- Elliptic curve group
How to encode as an element of
an efficiently computable and reversible map suffices

Security
Theorem: ElGamal encryption is IND-CPA under the DDH assumption.
Let be an adversary in the IND-CPA experiment s.t.
,
for some non-negligible function
Construct a DDH solver
Input:
uses as the public key, picks
Given computes and sends to
Output 1output by is equal to

Security

The difference is non-negligible, DDH problem is solved by

if
if
output

Oblivious Transfer (OT)
1-out-of-2 Oblivious Transfer ()
Alice has two secrets: and
Bob wants to learn for some
Bob’s Security: Alice cannot learn
Alice’s Security: Bob cannot learn
Background:
The notion of OT was introduced by Rabin; (but) Rabin’s OT is not of this form
“How to exchange secrets by oblivious transfer”, 1981
The 1-out-of-2 OT was formalized by Even, Goldreich, and Lempel
“A Randomized Protocol for Signing Contracts”, 1985

OT from Public-Key Encryption
The Scheme:
building block:
Alice’s input:
Bob’s input:
Bob: is randomly chosen; send to Alice
Alice: ; send to Bob
Bob: output
Security:
Alice cannot learn because are both “good” public keys
Bob cannot learn be cause he does not know
A dishonest may send of to Alice
A lot of research has been spent on OT against active Alice or Bob

Millionaires’ Problem
The Problem:
Alice and Bob are two millionaires;
Alice has millions and Bob has millions;
Alice doesn’t know and Bob doesn’t know
They want to decide who is more wealthy: or
They want to keep and hidden from each other
Background:
The problem was introduced by Andrew Chi-Chih Yao (1946-)
“Protocols for secure computations”, 1982
New field in cryptography: secure multi-party computation
numerous research in this field; still hot today
Turing Award 2000

Multi-Party Computation (MPC)
The Problem:
There are players: ……,
There is a function , known to all palyers
Each player has a private input ()
They want to learn
They want to keep the inputs private from each other
Millionaires’ Problem as An Example:
The millionaires’ problem is a secure 2-PC problem
Alice has private input Bob has private input
The function is

Yao’s Garbled Circuit
Represent the function as a Boolean circuit:
Suppose that are 2-bit long, i.e.,
Let and

Construct a Garbled Version of the Circuit:
Tool: private-key encryption
Evaluate the Garbled Circuit:
Tools: OT and private-key encryption

Simple Case:
Truth Table of :

The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table

choose the keys from uniformly and at random

Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob

Bob: learn with
Bob: decrypt PETT with

Alice: decide the output

Alice: notify
= gives
Bob: send the decryption result to Alice
Requirements on the private-key
encryption scheme:
is
IND-CPA secure

Simple Case:
The Truth Table:
The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table

Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob
Bob: learn with
Bob: decrypt PETT with
Alice: Decide the output

Alice: notify
= gives
Bob: send the result to Alice

Simple Case:
The Truth Table:
The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table

Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob
Bob: learn with
Bob: decrypt PETT with
Alice: decide output

Alice: notify
= gives
Bob: send the result to Alice

2-PC of the

The output line of each gate is encrypted by its left input line and then by its right input line.

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the

2-PC of the