TLDR: The "rock" that Christ spoke in Matthew 16 is the personal revelation that Peter had from the "Father which is in Heaven" that Jesus is the Son of God. Those who receive personal revelation cannot fail. Christ gave Peter Preisthood Keys to orchestrate the affairs of the church. These keys were lost during the apostasy and eventually restored again through modern prophets. (See video for explanation!. Read also this, or this).
Long version:
Being a member of The Church of Jesus Christ of Latter-day Saints, and having been a missionary sharing the message of the Great Apostasy and restoration of Christ's Church through modern prophets, this question is vital to my Christianity and knowing where to go for essential ordinances like baptism and the Sacrament. (I speak of my own accord and not on behalf of the Church of Jesus Christ.)
To understand this phrase "upon this rock", we must consider the full context.
- What is the "rock"?
- What are the keys of the Kingdom?
- How were they lost and restored?
With full context, we see that the "rock" is personal revelation.
13 ¶ When Jesus came into the coasts of Cæsarea Philippi, he asked his disciples, saying, Whom do men say that I the Son of man am?
14 And they said, Some say that thou art John the Baptist: some, Elias; and others, Jeremias, or one of the prophets.
15 He saith unto them, But whom say ye that I am?
16 And Simon Peter answered and said, Thou art the Christ, the Son of the living God.
17 And Jesus answered and said unto him, Blessed art thou, Simon Bar-jona: for flesh and blood hath not revealed it unto thee, but my Father which is in heaven.
18 And I say also unto thee, That thou art Peter, and upon this rock I will build my church; and the gates of hell shall not prevail against it.
19 And I will give unto thee the keys of the kingdom of heaven: and whatsoever thou shalt bind on earth shall be bound in heaven: and whatsoever thou shalt loose on earth shall be loosed in heaven.
The context for this quote is vital. First, Christ was challenging his disciples the source for their knowledge. While many rely on intellect or what-someone-else-told-them for knowledge, Peter knew by personal revelation that Christ was the Son of God.
Putting this in today's context, let's imagine Christ was homelessly traveling from town to town with a rag-tag band of followers. How would we be able to know Him as the Christ? The only way is by revelation, by knowledge which comes from "my Father which is in heaven."
The Church of Jesus Christ was, has been, and will be guided by personal revelation and Priesthood Keys.
- Christ gave Peter the Priesthood of God through the laying on of hands (Matthew 10:1)
- Priesthood is the "authority act in His name for the salvation of His children" (True to the Faith). Consider why Christ traveled far to be baptized of John? John was authorized.
- Priesthood Keys "are the rights of presidency, or the power God gives to man to govern and direct the kingdom of God on the earth"
Christ was the one authorized to exercise the Priesthood Keys he held. When he died, the authority to exercise those keys were bestowed upon Peter. It was then through Peter and others authorized that believers were able to be baptized by.
Consider it for a moment - Christ was baptized by John before He built His church. Then he authorized Peter and the twelve apostles to baptize and to lay on hands. This was Christ setting up His church apart from the other baptisms that existed in the time. Baptism is one covenant and ordinance necessary to enter the Kingdom of God. Peter had the authority to determine how baptism would be administered.
Peter led the church by revelation (see Acts 10:15 for how he received by revelation word that it was now okay to eat "four-footed beasts" and other things (Acts 10:12)).
What about "the gates of hell"?
Those who have personal revelation in Him cannot fall. See John 6 when many disciples walked no more with Christ after he preached the sermon on his flesh and blood. Those who walked away lacked the personal revelation to know that Christ had the words of life. The gates of hell prevailed that day against those who were without a testimony similar to Peter's.
How did the apostasy begin?
Christ taught in Matthew 24:9-11:
9 Then shall they deliver you up to be afflicted, and shall kill you: and ye shall be hated of all nations for my name’s sake.
10 And then shall many be offended, and shall betray one another, and shall hate one another.
11 And many false prophets shall rise, and shall deceive many.
Paul prophesied that when he died there'd be a falling away of the church Acts 20:28-30.
28 ¶ Take heed therefore unto yourselves, and to all the flock, over the which the Holy Ghost hath made you overseers, to feed the church of God, which he hath purchased with his own blood.
29 For I know this, that after my departing shall grievous wolves enter in among you, not sparing the flock.
30 Also of your own selves shall men arise, speaking perverse things, to draw away disciples after them.
And in 2 Thessalonians 2:1-12:
3 Let no man deceive you by any means: for that day shall not come, except there come a falling away first, and that man of sin be revealed, the son of perdition;
4 Who opposeth and exalteth himself above all that is called God, or that is worshipped; so that he as God sitteth in the temple of God, shewing himself that he is God.
Clearly, there was a prophesied falling away. It began with the murdering of the apostles, as prophesied. The church would be taken away until the "restitution of all things" (Acts 3:19-21).
How was the Priesthood restored?
Happy to dive into this more, but see "Restoration of the Priesthood" and "The Keys and the Authority of the Priesthood". The keys were restored through a prophet who was chosen by God. Abraham was chosen. Moses was chosen in the bush. Christ chose Peter. Likewise, Christ chose Joseph Smith in 1820. Several years later he was given the Priesthoods of Aaron (by the hand of John the Baptist, see also this history) and of Melchizedek (by the hands of Peter, James, and John and this history).
Other Christian denominations consider Joseph Smith a fraud, or a mastermind, or whatever they want to call him (except a prophet of God). That's fine for them to say, but it doesn't actually make it so. Joseph's church still stands, the Book of Mormon remains an additional Testament of Jesus Christ (in addition to the New and Old Testaments).
How can I be saved from personal apostasy?
The core foundation of being a member of The Church of Jesus Christ of Latter-day saints is 1) a belief in God, 2) a belief in Jesus Christ as God's Son, and 3) knowledge of these things by the power of the Holy Ghost.
The only way you can know which church is Christ's church is by following Joseph Smith's example and praying to God the Father yourself and asking Him which church you should join. I implore any reading this to ask God themselves what Church is true. Don't rely on this text or on anyone you listen to. Because there is strong logic and reason in many religions or pastors. And while strong logic and reason could have led Peter to believe Christ was the Son of God, Peter knew only because of personal revelation. And so, may we all pray to God for His guidance to His church.
More details
Great Apostasy and the Restoration